【摘要】：流水車間生產(chǎn)模式廣泛應(yīng)用于現(xiàn)代制造企業(yè)中,因此流水車間調(diào)度成為實際生產(chǎn)制造車間中十分常見且重要的一類排產(chǎn)方式,也是車間調(diào)度研究的一個熱點問題。在實際生產(chǎn)中,一個優(yōu)秀的調(diào)度排序,能夠保證生產(chǎn)活動的穩(wěn)步進行,提高資源利用率,保證交貨完工時間,滿足客戶多樣化的需求。在理論上,該問題代表了一類組合優(yōu)化問題,如能有效的求解對于解決其他優(yōu)化問題有很強的指導(dǎo)意義。本文針對置換流水車間調(diào)度問題(Permutation Flow-shop Scheduling Problem, PFSP),以最小化最大完工時間make span為目標(biāo),提出了一種改進蛙跳算法求解。為了使研究的問題更具有普遍性與代表性,深入系統(tǒng)地研究了多目標(biāo)置換流水車間調(diào)度問題(Multi-objective PFSP,MPFSP),提出了與之適應(yīng)的多目標(biāo)改進蛙跳算法進行求解。 首先,系統(tǒng)闡述了蛙跳算法的優(yōu)化原理與操作流程,以及在各個優(yōu)化領(lǐng)域的應(yīng)用情況。針對蛙跳算法局部搜索能力較弱的問題,通過結(jié)合粒子群算法的個體更新策略,提出了改進蛙跳算法。通過對連續(xù)函數(shù)優(yōu)化問題求解,驗證了算法改進的有效性,新的算法在優(yōu)化結(jié)果與收斂速度上明顯優(yōu)于標(biāo)準(zhǔn)蛙跳算法與粒子群算法。其次,針對以最小化make span為目標(biāo)的PFSP,應(yīng)用改進蛙跳算法進行求解。為使算法適用于離散組合優(yōu)化問題的求解,采用基于隨機鍵表示法的規(guī)則設(shè)計了算法編碼。同時,為提高初始解的質(zhì)量,采用改進的NEH啟發(fā)式算法生成多樣性的初始解。在減少計算時間方面,充分利用該問題的可逆性原理計算make span。采用基準(zhǔn)測試集進行測試,其結(jié)果與其他算法求解該類問題的較好結(jié)果相比較,驗證了算法的有效性。 最后,針對多目標(biāo)PFSP,建立以最小化總流經(jīng)時間、最大完工時間以及最大拖后時間為優(yōu)化目標(biāo)的數(shù)學(xué)模型,設(shè)計了多目標(biāo)蛙跳算法求解。算法采用四種啟發(fā)式算法生成高質(zhì)量的初始解,并建立精英解集儲存Pareto解,通過自適應(yīng)小生境方法對精英解集進行維護。采用基準(zhǔn)測試集進行測試,算法與解決多目標(biāo)問題較優(yōu)的改進強度Pareto進化算法進行比較,驗證了算法的有效性。
[Abstract]:The flow shop production model is widely used in modern manufacturing enterprises, so the flow shop scheduling has become a very common and important scheduling method in the actual production shop, and it is also a hot issue in the research of shop scheduling. In actual production, an excellent scheduling and sorting can ensure the steady progress of production activities, improve the utilization of resources, ensure the delivery completion time, and meet the diversified needs of customers. In theory, the problem represents a class of combinatorial optimization problems, such as effective solution to other optimization problems have a strong guiding significance. In this paper, an improved leapfrog algorithm is proposed to solve the replacement flow shop scheduling problem (Permutation Flow-shop Scheduling Problem, PFSP), which aims at minimizing the maximum completion time (make span). In order to make the studied problem more universal and representative, the multi-objective permutation flow shop scheduling problem (Multi-objective PFSP,MPFSP) is studied systematically, and a multi-objective improved leapfrog algorithm is proposed to solve the problem. Firstly, the optimization principle and operation flow of leapfrog algorithm and its application in various optimization fields are systematically described. In order to solve the problem of weak local search ability of leapfrog algorithm, an improved leapfrog algorithm is proposed by combining the individual updating strategy of particle swarm optimization (PSO). The effectiveness of the improved algorithm is verified by solving the continuous function optimization problem. The new algorithm is superior to the standard leapfrog algorithm and particle swarm optimization algorithm in the optimization results and convergence speed. Secondly, the improved leapfrog algorithm is applied to minimize make span for PFSP,. In order to make the algorithm suitable for solving discrete combinatorial optimization problems, the algorithm coding is designed based on the rules of stochastic key representation. At the same time, to improve the quality of the initial solution, the improved NEH heuristic algorithm is used to generate the diversity of the initial solution. In order to reduce the computation time, the reversible principle of this problem is fully used to calculate make span.. The benchmark set is used to test, and the results are compared with the better results of other algorithms to solve this kind of problem, and the validity of the algorithm is verified. Finally, a multi-objective leapfrog algorithm is designed to solve the mathematical model of multi-objective PFSP, which is to minimize the total flow time, the maximum completion time and the maximum delay time. Four heuristic algorithms are used to generate high quality initial solutions, and an elite solution set is built to store Pareto solutions, and an adaptive niche method is used to maintain the elite solution sets. The benchmark set is used to test, and the algorithm is compared with the improved strength Pareto evolutionary algorithm, which is better for solving multi-objective problems. The validity of the algorithm is verified.
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2011
【分類號】：TH186

【參考文獻】

相關(guān)期刊論文 前8條

1 李英海;周建中;楊俊杰;劉力;;一種基于閾值選擇策略的改進混合蛙跳算法[J];計算機工程與應(yīng)用;2007年35期

2 周鵬;;求解置換流水車間調(diào)度問題的混合蟻群算法[J];計算機工程與應(yīng)用;2009年17期

3 王亞敏;潘全科;冀俊忠;包云;;基于蛙跳算法的零空閑流水線調(diào)度問題優(yōu)化[J];計算機工程與應(yīng)用;2010年17期

4 唐云嵐;趙青松;高妍方;陳英武;;Pareto最優(yōu)概念的多目標(biāo)進化算法綜述[J];計算機科學(xué);2008年10期

5 劉延風(fēng);劉三陽;;改進微粒群優(yōu)化求解置換流水車間調(diào)度問題[J];計算機集成制造系統(tǒng);2009年10期

6 楊建國,丁慧敏,李蓓智;解決多目標(biāo)Flow-shop問題的生物免疫調(diào)度算法[J];機械設(shè)計與研究;2002年04期

7 李寧,鄒彤,孫德寶;帶時間窗車輛路徑問題的粒子群算法[J];系統(tǒng)工程理論與實踐;2004年04期

8 徐寧,李春光,張健,虞厥邦;幾種現(xiàn)代優(yōu)化算法的比較研究[J];系統(tǒng)工程與電子技術(shù);2002年12期

相關(guān)博士學(xué)位論文 前1條

1 胡成玉;面向動態(tài)環(huán)境的粒子群算法研究[D];華中科技大學(xué);2010年

，

本文編號：2378587