基于混合粒子群優(yōu)化的置換流水車間調(diào)度方法研究.pdf

1、制造業(yè)中的調(diào)度就是對(duì)加工過(guò)程進(jìn)行計(jì)劃，有效的調(diào)度方案可以減少加工時(shí)間，減小庫(kù)存，保證交貨期，增加企業(yè)的效益等。隨著全球市場(chǎng)競(jìng)爭(zhēng)的激烈和客戶需求日益的個(gè)性化和多樣化，調(diào)度問(wèn)題越來(lái)越受到人們的重視。置換流水車間調(diào)度問(wèn)題(Permutation Flow Shop Scheduling Problem，PFSP)是實(shí)際生產(chǎn)制造車間中十分常見(jiàn)且重要的一類排產(chǎn)方式，也是車間調(diào)度的一個(gè)熱點(diǎn)。本文基于粒子群優(yōu)化(Particle Swarm Opti

2、mization，PSO)算法，在解決單目標(biāo)PFSP的基礎(chǔ)上，深入系統(tǒng)的研究了多目標(biāo)PFSP(Multi-objective PFSP，MPFSP)。
　　 首先，闡述了研究的目的和意義，對(duì)流水車間單目標(biāo)、多目標(biāo)調(diào)度問(wèn)題的算法和研究概況進(jìn)行了綜述。分析了該問(wèn)題研究存在的不足及未來(lái)發(fā)展趨勢(shì)。
　　 其次，針對(duì)最小化最大完工時(shí)間為目標(biāo)的PFSP，提出一種混合PSO，記為NE-HPSO。該算法采用NEH產(chǎn)生部分初始解，提高算法

3、初始解的質(zhì)量，采用基于隨機(jī)鍵表示法的最小位置實(shí)數(shù)排序規(guī)則(Smallest Position Value，SPV)進(jìn)行編碼。為增強(qiáng)算法的局部搜索能力，設(shè)計(jì)了基于變鄰域搜索算法(Variable neighborhood search，VNS)的局部搜索，鄰域結(jié)構(gòu)基于關(guān)鍵路徑進(jìn)行搭建。為了驗(yàn)證該算法的有效性，采取Taillard基準(zhǔn)測(cè)試集進(jìn)行測(cè)試，測(cè)試的到的結(jié)果與在該問(wèn)題取得較好結(jié)果的算法進(jìn)行比較，驗(yàn)證算法的有效性。
　　 隨后，

4、在單目標(biāo)PFSP問(wèn)題研究的基礎(chǔ)上，對(duì)多目標(biāo)PFSP問(wèn)題進(jìn)行研究?？紤]到MPFSP的各個(gè)目標(biāo)的特點(diǎn)，采用四種啟發(fā)式算法NEH，SPT，EDD及CDS產(chǎn)生四個(gè)高質(zhì)量的初始解，提高初始解的質(zhì)量。建立外部精英歸檔集儲(chǔ)存Pareto解，并采用聚類的方式維持外部精英歸檔集的規(guī)模。設(shè)計(jì)一種基于距離的保持解分散性的方法，保證種群的多樣性。對(duì)于外部精英歸檔集中的Pareto解進(jìn)行局部搜索，局部搜索基于改進(jìn)VNS，鄰域結(jié)構(gòu)采用交換，插入，逆序和Or-opt

5、操作。為驗(yàn)證算法的有效性，測(cè)試實(shí)例仍采用Taillard基準(zhǔn)測(cè)試集。該算法與解決多目標(biāo)問(wèn)題效果較優(yōu)的改進(jìn)強(qiáng)度Pareto進(jìn)化算法(Strength Pareto Evolutionary Algorithm2，SPEA2)進(jìn)行比較，得到了相當(dāng)或者更優(yōu)的結(jié)果，證明了算法的優(yōu)良性能。
　　 最后，在上述理論研究的基礎(chǔ)上，開(kāi)發(fā)了基于單目標(biāo)和多目標(biāo)的置換流水車間調(diào)度問(wèn)題原型系統(tǒng)。對(duì)全文進(jìn)行總結(jié)，并對(duì)PSO算法以及置換流水車間調(diào)度的今后研