基于遺傳算法的車間生產(chǎn)調(diào)度問(wèn)題研究.pdf

1、隨著客戶需求日趨多樣化，產(chǎn)品的生產(chǎn)技術(shù)在不斷更新，各行業(yè)間的競(jìng)爭(zhēng)逐漸加劇，每一個(gè)企業(yè)都面臨著生存危機(jī)，為了占領(lǐng)市場(chǎng)，他們必須以低成本、快速度開發(fā)出高質(zhì)量的新產(chǎn)品。因此企業(yè)都迫切需要尋求一種新的生產(chǎn)方式來(lái)縮短產(chǎn)品開發(fā)周期，降低生產(chǎn)成本，最終實(shí)現(xiàn)效益最大化。作為企業(yè)生產(chǎn)管理中一個(gè)必不可少的環(huán)節(jié)，車間生產(chǎn)調(diào)度管理是生產(chǎn)管理任務(wù)順利實(shí)施和完成的重要保障。目前對(duì)于車間生產(chǎn)調(diào)度問(wèn)題的研究主要集中在如何合理的配置加工過(guò)程的各種資源，減少工件加工準(zhǔn)備、

2、等待時(shí)間。因此對(duì)這一問(wèn)題的研究具有廣闊的應(yīng)用前景。
　　作業(yè)車間調(diào)度問(wèn)題是車間生產(chǎn)調(diào)度中的一個(gè)典型問(wèn)題，它是在滿足一定約束條件下，研究對(duì)各道工序加工順序的排列以使相應(yīng)的性能指標(biāo)達(dá)到最優(yōu)。根據(jù)約束條件的不同，作業(yè)車間調(diào)度問(wèn)題可分為經(jīng)典作業(yè)車間調(diào)度問(wèn)題和柔性作業(yè)車間調(diào)度問(wèn)題兩類。研究表明，隨著問(wèn)題規(guī)模的擴(kuò)大，求解作業(yè)車間調(diào)度問(wèn)題的復(fù)雜度會(huì)呈指數(shù)增長(zhǎng)。由于遺傳算法具有隱含并行性和全局優(yōu)化的特點(diǎn)，它已經(jīng)成為目前求解作業(yè)車間調(diào)度問(wèn)題的有效方

3、法之一。但該算法所存在的早熟收斂和局部搜索能力較差的缺點(diǎn)卻制約了它在這一領(lǐng)域的深入研究。為了提高遺傳算法求解作業(yè)車間調(diào)度問(wèn)題的效率，本文結(jié)合逆序數(shù)、信息熵和協(xié)同進(jìn)化等理論，提出了一系列遺傳調(diào)度算法，主要取得了如下的研究成果:
　　(1)基于隨機(jī)性指導(dǎo)策略的作業(yè)車間遺傳調(diào)度算法由于遺傳算法在操作中具有隨機(jī)性操作，這些操作使算法的執(zhí)行結(jié)果具有不確定性，為了提高算法求解結(jié)果的穩(wěn)定性，有效指導(dǎo)算法的進(jìn)化方向，針對(duì)經(jīng)典作業(yè)車間調(diào)度問(wèn)題，提出

4、了一類基于隨機(jī)性指導(dǎo)策略的遺傳調(diào)度算法。這類算法包括基于信息熵的遺傳調(diào)度算法和基于逆序數(shù)的遺傳調(diào)度算法。其中，基于信息熵的遺傳調(diào)度算法是借助生態(tài)學(xué)的多樣性指數(shù)和決策樹算法的屬性選擇準(zhǔn)則所提出的。該算法利用信息熵值的差異確定參與復(fù)制的個(gè)體，在交叉和變異算子的設(shè)計(jì)中引入信息熵衡量工序、機(jī)器的重要度，并利用交叉父代表示的調(diào)度方案所隱含的信息獲取優(yōu)良基因排列。其次，通過(guò)分析求解作業(yè)車間調(diào)度問(wèn)題和旅行商問(wèn)題所采用的遺傳算子，提出了基于逆序數(shù)的遺傳

5、調(diào)度算法。該算法在遺傳過(guò)程中利用相對(duì)逆序數(shù)檢驗(yàn)群體的一致性，并根據(jù)排列奇偶性的改變進(jìn)行交叉（或變異）操作，從而產(chǎn)生后代群體。實(shí)驗(yàn)結(jié)果驗(yàn)證了所提出的遺傳調(diào)度算法的有效性。
　　(2)基于協(xié)同進(jìn)化的作業(yè)車間遺傳調(diào)度算法為了增強(qiáng)遺傳算法的并行處理能力，針對(duì)經(jīng)典作業(yè)車間調(diào)度問(wèn)題，提出了一類基于協(xié)同進(jìn)化的遺傳調(diào)度算法。該算法包括基于群體間協(xié)同進(jìn)化的遺傳調(diào)度算法和基于個(gè)體間協(xié)同進(jìn)化的遺傳調(diào)度算法。其中，基于群體間協(xié)同進(jìn)化的遺傳調(diào)度算法借鑒標(biāo)準(zhǔn)

6、協(xié)同進(jìn)化遺傳算法的性質(zhì)，在操作中結(jié)合子種群共同進(jìn)化的原則，并利用基于排名的選擇方法，從多種遺傳算子中選擇出相應(yīng)的交叉（或變異）方法而產(chǎn)生遺傳后代?；趥€(gè)體間協(xié)同進(jìn)化的遺傳調(diào)度算法則是利用多個(gè)個(gè)體參與遺傳算子的操作，借助個(gè)體間調(diào)度解和染色體結(jié)構(gòu)的區(qū)別指導(dǎo)交叉（或變異）父代的產(chǎn)生。這類算法從群體和個(gè)體間的進(jìn)化過(guò)程、遺傳操作中的選擇策略（父代的選擇、算子的選擇）等方面真正體現(xiàn)出了算法并行處理的特征。實(shí)驗(yàn)結(jié)果表明，基于協(xié)同進(jìn)化的遺傳算法能夠有效

7、求解經(jīng)典作業(yè)車間調(diào)度問(wèn)題。
　　(3)改進(jìn)的柔性作業(yè)車間遺傳調(diào)度算法通過(guò)對(duì)目前柔性作業(yè)車間調(diào)度算法的分析，針對(duì)具有不同目標(biāo)的柔性作業(yè)車間調(diào)度問(wèn)題，提出了兩種改進(jìn)的遺傳調(diào)度算法。首先，針對(duì)單目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題，提出了一種分部遺傳調(diào)度算法。該算法將分部編碼方法和分部遺傳算子操作有效地加以結(jié)合，由此能夠直接產(chǎn)生可行的調(diào)度方案;其次，針對(duì)多目標(biāo)柔性作業(yè)車間調(diào)度問(wèn)題提出了一種改進(jìn)的遺傳算法。該算法首先利用矩陣編碼方法縮小了求解空間，并

8、從符合各項(xiàng)約束條件出發(fā)，對(duì)解碼步驟進(jìn)行詳細(xì)闡述，從而保證算法能夠產(chǎn)生可行的調(diào)度方案。然后借助根據(jù)選擇機(jī)制和木桶原理設(shè)計(jì)的遺傳調(diào)度算子的操作產(chǎn)生可行的遺傳后代。實(shí)驗(yàn)結(jié)果驗(yàn)證了所提出算法求解柔性作業(yè)車間調(diào)度問(wèn)題的有效性和可行性。
　　(4)基于基尼指數(shù)的遺傳調(diào)度算法通過(guò)對(duì)不同類型作業(yè)車間調(diào)度問(wèn)題的分析，提取各問(wèn)題間的共性部分，并借鑒進(jìn)化生態(tài)學(xué)原理和決策樹算法的屬性分裂準(zhǔn)則，提出了一種基于基尼指數(shù)的遺傳調(diào)度算法。該算法針對(duì)經(jīng)典作業(yè)車間調(diào)

9、度問(wèn)題和柔性作業(yè)車間調(diào)度問(wèn)題，挖掘出各問(wèn)題間的共性特征，對(duì)其相同的特性采用基于基尼指數(shù)的遺傳算子操作，同時(shí)采用基尼指數(shù)作為個(gè)體多樣性和優(yōu)劣性的衡量指標(biāo)，通過(guò)和目前其它調(diào)度算法的實(shí)驗(yàn)結(jié)果的比較，證實(shí)了所提出的算法對(duì)于具有共性特征的作業(yè)車間調(diào)度問(wèn)題的求解是非常有效的。
　　總之，本文針對(duì)經(jīng)典作業(yè)車間調(diào)度問(wèn)題、柔性作業(yè)車間調(diào)度問(wèn)題及具有共性特征的車間調(diào)度問(wèn)題提出了一系列遺傳調(diào)度算法，這些算法的提出不僅適用于求解制造業(yè)的各類車間調(diào)度問(wèn)題，