一類單機(jī)器成組排序問(wèn)題的算法研究.pdf

1、本文以現(xiàn)代生產(chǎn)制造業(yè)中成組生產(chǎn)為實(shí)際背景，研究了一類以最小化加權(quán)完工時(shí)間總和為目標(biāo)(1|Sfg|∑wjCj)的成組作業(yè)生產(chǎn)排序問(wèn)題。該問(wèn)題在任意組別的情況下是NP-Hard難題，在大規(guī)模排序的情形下，將變得不可解，尋找最優(yōu)解所需的計(jì)算時(shí)間將無(wú)法滿足需求和生產(chǎn)多變的現(xiàn)代生產(chǎn)制造環(huán)境。因此本文將研究中心放在了該問(wèn)題的近似搜索算法的研究上，本文的主要貢獻(xiàn)主要于如下四點(diǎn)： 1.最優(yōu)化模型的總結(jié)和延伸。生產(chǎn)作業(yè)排序的問(wèn)題一直是學(xué)術(shù)界研究的

2、焦點(diǎn)。針對(duì)成組排序問(wèn)題也出現(xiàn)了一些理論成果，本文列舉了現(xiàn)有的針對(duì)1|Sfg|∑wjCj問(wèn)題的前向和后向動(dòng)態(tài)規(guī)劃算法以及該問(wèn)題的一個(gè)重要的最優(yōu)化排序性質(zhì)，并給出了該問(wèn)題的一個(gè)一般化的整數(shù)規(guī)劃模型。 2.傳統(tǒng)旅行商問(wèn)題(TSP)的遺傳算法的應(yīng)用。最優(yōu)化模型雖然從理論上可以求出1|Sfg|∑wjCj的最優(yōu)解，但是其算法的復(fù)雜度為O(NF)，因此在大量組別的情況下，計(jì)算時(shí)間將變得不再可行。本文從TSP問(wèn)題與排序問(wèn)題的相似性出發(fā)，嘗試將傳

3、統(tǒng)的用于解決TSP問(wèn)題的遺傳算法應(yīng)用于1|Sfg|∑wjCj問(wèn)題，給出了兩種基因編碼下具體的遺傳算法的算子操作和算法流程。 3.一種新的遺傳算法的提出。上述用于解決TSP的遺傳算法沒(méi)有考慮1|Sfg|∑wjCj自身的問(wèn)題特征，因此本文嘗試?yán)?|Sfg|∑wjCj的最優(yōu)解集的特性，提出了一種新的基因編碼(順序編碼)方式下的遺傳算法(OGA)，該編碼方式可以將染色體映射到一個(gè)較小的搜索空間，并且針對(duì)該編碼設(shè)計(jì)了新的遺傳算子，大大提