【摘要】：制造業(yè)中的調(diào)度就是對加工過程進(jìn)行計劃,有效的調(diào)度方案可以減少加工時間,減小庫存,保證交貨期,增加企業(yè)的效益等。隨著全球市場競爭的激烈和客戶需求日益的個性化和多樣化,調(diào)度問題越來越受到人們的重視。置換流水車間調(diào)度問題(Permutation Flow Shop Scheduling Problem, PFSP)是實際生產(chǎn)制造車間中十分常見且重要的一類排產(chǎn)方式,也是車間調(diào)度的一個熱點。本文基于粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法,在解決單目標(biāo)PFSP的基礎(chǔ)上,深入系統(tǒng)的研究了多目標(biāo)PFSP(Multi-objective PFSP,MPFSP)。 首先,闡述了研究的目的和意義,對流水車間單目標(biāo)、多目標(biāo)調(diào)度問題的算法和研究概況進(jìn)行了綜述。分析了該問題研究存在的不足及未來發(fā)展趨勢。 其次,針對最小化最大完工時間為目標(biāo)的PFSP,提出一種混合PSO,記為NE-HPSO。該算法采用NEH產(chǎn)生部分初始解,提高算法初始解的質(zhì)量,采用基于隨機(jī)鍵表示法的最小位置實數(shù)排序規(guī)則(Smallest Position Value,SPV)進(jìn)行編碼。為增強(qiáng)算法的局部搜索能力,設(shè)計了基于變鄰域搜索算法(Variable neighborhood search, VNS)的局部搜索,鄰域結(jié)構(gòu)基于關(guān)鍵路徑進(jìn)行搭建。為了驗證該算法的有效性,采取Taillard基準(zhǔn)測試集進(jìn)行測試,測試的到的結(jié)果與在該問題取得較好結(jié)果的算法進(jìn)行比較,驗證算法的有效性。 隨后,在單目標(biāo)PFSP問題研究的基礎(chǔ)上,對多目標(biāo)PFSP問題進(jìn)行研究。考慮到MPFSP的各個目標(biāo)的特點,采用四種啟發(fā)式算法NEH,SPT,EDD及CDS產(chǎn)生四個高質(zhì)量的初始解,提高初始解的質(zhì)量。建立外部精英歸檔集儲存Pareto解,并采用聚類的方式維持外部精英歸檔集的規(guī)模。設(shè)計一種基于距離的保持解分散性的方法,保證種群的多樣性。對于外部精英歸檔集中的Pareto解進(jìn)行局部搜索,局部搜索基于改進(jìn)VNS,鄰域結(jié)構(gòu)采用交換,插入,逆序和Or-opt操作。為驗證算法的有效性,測試實例仍采用Taillard基準(zhǔn)測試集。該算法與解決多目標(biāo)問題效果較優(yōu)的改進(jìn)強(qiáng)度Pareto進(jìn)化算法(Strength Pareto Evolutionary Algorithm2,SPEA2)進(jìn)行比較,得到了相當(dāng)或者更優(yōu)的結(jié)果,證明了算法的優(yōu)良性能。 最后,在上述理論研究的基礎(chǔ)上,開發(fā)了基于單目標(biāo)和多目標(biāo)的置換流水車間調(diào)度問題原型系統(tǒng)。對全文進(jìn)行總結(jié),并對PSO算法以及置換流水車間調(diào)度的今后研究工作進(jìn)行了展望。
[Abstract]:The scheduling of manufacturing industry is to plan the processing process. The effective scheduling scheme can reduce the processing time, reduce the inventory, ensure the delivery time, increase the efficiency of the enterprise, and so on. With the fierce competition in the global market and the increasing individuation and diversification of customer demand, people pay more and more attention to the scheduling problem. Replacement flow shop scheduling problem (Permutation Flow Shop Scheduling Problem, PFSP) is a very common and important scheduling method in practical production shop, and it is also a hot spot in job shop scheduling. Based on the particle swarm optimization (Particle Swarm) optimization algorithm and the solution of single objective PFSP, the multiobjective PFSP (Multi-objective PFSPN MPFSP) is studied systematically in this paper. Firstly, the purpose and significance of the research are described, and the algorithms and research situation of single objective and multi-objective scheduling problem in flow shop are summarized. The deficiency of the research and the development trend in the future are analyzed. Secondly, for PFSPs with the goal of minimizing the maximum completion time, a hybrid PSO NE-HPSOs is proposed. The algorithm uses NEH to generate partial initial solution, which improves the quality of initial solution, and uses the minimum position real number sorting rule based on stochastic key representation (Smallest Position value (Smallest Position) to code. In order to enhance the local search ability of the algorithm, the local search based on the variable neighborhood search algorithm (Variable neighborhood search, VNS) is designed, and the neighborhood structure is built based on the critical path. In order to verify the validity of the algorithm, the validity of the algorithm is verified by using the Taillard benchmark set, and the results obtained are compared with those obtained in the problem. Then, based on the study of single objective PFSP problem, the multi-objective PFSP problem is studied. Considering the characteristics of each target of MPFSP, four heuristic algorithms, NEH / SPT / EDD and CDS, are used to produce four high quality initial solutions, which can improve the quality of the initial solution. The Pareto solution is stored in the external elite archive set, and the scale of the external elite archive set is maintained by clustering. A distance-based method is designed to keep the diversity of the population. The local search for the Pareto solution in the external elite archival set is based on the improved VNSs, and the neighborhood structure uses exchange, insert, reverse sequence and Or-opt operations. In order to verify the validity of the algorithm, the Taillard benchmark set is still used in the test example. The algorithm is compared with the improved strength Pareto evolutionary algorithm (Strength Pareto Evolutionary algorithm 2 / SPEA2), which has better effect in solving multi-objective problems. The results are equivalent or better, and the excellent performance of the algorithm is proved. Finally, on the basis of the above theoretical research, a prototype system of permutation shop scheduling problem based on single objective and multi-objective is developed. This paper summarizes the whole paper, and looks forward to the future research work of PSO algorithm and replacement flow shop scheduling.
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2011
【分類號】：TH186

【相似文獻(xiàn)】

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

1 胡凱林;李平;;基于改進(jìn)蟻群算法的煉鐵原料混勻過程調(diào)度優(yōu)化[J];上海交通大學(xué)學(xué)報;2011年08期

2 厲虹;張?zhí)?;基于樣條逼近與曲線擬合的欠驅(qū)動仿生機(jī)器人運(yùn)動規(guī)劃[J];北京信息科技大學(xué)學(xué)報(自然科學(xué)版);2011年04期

3 戴浪;黃守道;黃科元;葉盛;;風(fēng)電場風(fēng)速的神經(jīng)網(wǎng)絡(luò)組合預(yù)測模型[J];電力系統(tǒng)及其自動化學(xué)報;2011年04期

4 彭顯剛;胡松峰;呂大勇;;基于RBF神經(jīng)網(wǎng)絡(luò)的短期負(fù)荷預(yù)測方法綜述[J];電力系統(tǒng)保護(hù)與控制;2011年17期

5 張廣明;袁宇浩;龔松建;;基于改進(jìn)最小二乘支持向量機(jī)方法的短期風(fēng)速預(yù)測[J];上海交通大學(xué)學(xué)報;2011年08期

6 唐明珠;王岳斌;陽春華;;一種改進(jìn)的支持向量數(shù)據(jù)描述故障診斷方法[J];控制與決策;2011年07期

7 孫鋒利;何明一;高全華;;基于自適應(yīng)脊波網(wǎng)絡(luò)的高光譜遙感圖像分類[J];計算機(jī)科學(xué);2011年08期

8 陳世明;聶森;李慧敏;方華京;;移動智能體網(wǎng)絡(luò)的優(yōu)化功率控制及同步[J];華中科技大學(xué)學(xué)報(自然科學(xué)版);2011年07期

9 陳志英;任遠(yuǎn);白廣忱;高陽;;粒子群優(yōu)化的Kriging近似模型及其在可靠性分析中的應(yīng)用[J];航空動力學(xué)報;2011年07期

10 姜秋香;付強(qiáng);王子龍;;三江平原水資源承載力評價及區(qū)域差異[J];農(nóng)業(yè)工程學(xué)報;2011年09期

相關(guān)會議論文 前10條

1 趙建玉;賈磊;陳月輝;張勇;;基于粒子群優(yōu)化的信號交叉口交通流預(yù)測模型[A];第二十六屆中國控制會議論文集[C];2007年

2 王曉燕;王東風(fēng);韓璞;;一種分?jǐn)?shù)階系統(tǒng)的粒子群優(yōu)化辨識方法[A];全國第三屆信號和智能信息處理與應(yīng)用學(xué)術(shù)交流會�？痆C];2009年

3 洪宗友;;No-Wait流水車間調(diào)度問題求解研究[A];科學(xué)發(fā)展與社會責(zé)任（A卷）——第五屆沈陽科學(xué)學(xué)術(shù)年會文集[C];2008年

4 范業(yè)坤;梁新榮;;基于粒子群優(yōu)化的高速公路匝道PI控制器[A];第二十七屆中國控制會議論文集[C];2008年

5 薛艷紅;胡立坤;;基于粒子群優(yōu)化的配電網(wǎng)靜止同步補(bǔ)償器PI控制器整定[A];中南六省（區(qū)）自動化學(xué)會第二十九屆學(xué)術(shù)年會論文集[C];2011年

6 馮yN;李霞;;一種K最近鄰分類的改進(jìn)算法及應(yīng)用[A];2011年全國通信安全學(xué)術(shù)會議論文集[C];2011年

7 徐俊杰;忻展紅;;粒子群優(yōu)化在0/1背包問題中的應(yīng)用[A];中國運(yùn)籌學(xué)會第七屆學(xué)術(shù)交流會論文集（上卷）[C];2004年

8 趙秋玲;周雅莉;張奇志;;基于粒子群優(yōu)化的結(jié)構(gòu)振動分布式反饋控制[A];2005年中國智能自動化會議論文集[C];2005年

9 薛云燦;鄭東亮;岳興漢;楊啟文;;混沌粒子群優(yōu)化算法及其在水庫優(yōu)化調(diào)度中的應(yīng)用[A];PCC2009—第20屆中國過程控制會議論文集[C];2009年

10 徐俊杰;忻展紅;;基于增強(qiáng)型參考位置的粒子群優(yōu)化模型[A];’2004系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)交流會論文集[C];2004年

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

1 竇全勝;求解優(yōu)化問題的演化計算方法研究[D];吉林大學(xué);2005年

2 劉麗;人工免疫網(wǎng)絡(luò)研究及應(yīng)用[D];江南大學(xué);2008年

3 李磊;六自由度并聯(lián)平臺位置正解及控制方法研究[D];哈爾濱工程大學(xué);2008年

4 馬瑞新;基于粒子群的網(wǎng)絡(luò)社區(qū)動態(tài)角色挖掘研究[D];大連理工大學(xué);2012年

5 陳虹;分離流動的電磁力主動控制[D];華中科技大學(xué);2011年

6 林川;粒子群優(yōu)化與差分進(jìn)化算法研究及其應(yīng)用[D];西南交通大學(xué);2009年

7 韓曉霞;混沌與支持向量機(jī)結(jié)合的多相催化建模與優(yōu)化研究[D];太原理工大學(xué);2010年

8 柯晶;強(qiáng)跟蹤狀態(tài)估計與群集辨識[D];浙江大學(xué);2003年

9 時小虎;Elman神經(jīng)網(wǎng)絡(luò)與進(jìn)化算法的若干理論研究及應(yīng)用[D];吉林大學(xué);2006年

10 劉洪波;漢語認(rèn)知腦數(shù)據(jù)挖掘相關(guān)算法及應(yīng)用研究[D];大連理工大學(xué);2006年

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

1 孫藝;基于混合粒子群優(yōu)化的置換流水車調(diào)度方法研究[D];華中科技大學(xué);2011年

2 雷燁;基于粒子群最小二乘支持向量機(jī)的故障診斷算法研究[D];蘭州交通大學(xué);2010年

3 馬培培;基于粒子群的圖像閾值化分割的研究及應(yīng)用[D];合肥工業(yè)大學(xué);2010年

4 姚杰;基于PSO混沌神經(jīng)網(wǎng)絡(luò)電力系統(tǒng)負(fù)荷預(yù)測[D];大慶石油學(xué)院;2009年

5 劉楊;粒子群優(yōu)化算法在電力系統(tǒng)無功優(yōu)化中的應(yīng)用[D];天津大學(xué);2005年

6 任曉娜;DNA計算中的編碼設(shè)計優(yōu)化算法[D];湖南大學(xué);2010年

7 王保震;中壓配電網(wǎng)變電站選址定容方法研究[D];華北電力大學(xué)（河北）;2009年

8 王琳;基于粒子群優(yōu)化的數(shù)據(jù)流挖掘的聚類算法分析[D];長沙理工大學(xué);2010年

9 李濤;基于SVM和PSO的非線性模型預(yù)測控制及應(yīng)用研究[D];上海交通大學(xué);2008年

10 孫巍;供熱管網(wǎng)的建模分析及水力平衡調(diào)節(jié)[D];北京化工大學(xué);2008年

，

本文編號：2185617