遺傳算法求解帶權(quán)重的生產(chǎn)調(diào)度問題*

王召陽 高 尚

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212001）

1 引言

車間調(diào)度是現(xiàn)代企業(yè)制造的基礎(chǔ)，優(yōu)化生產(chǎn)調(diào)度是先進(jìn)企業(yè)亟需解決的關(guān)鍵問題。在實(shí)際生產(chǎn)過程中，工件一般都是按批生產(chǎn)的，所以研究批量調(diào)度的優(yōu)化方法對(duì)現(xiàn)代企業(yè)有著重要的實(shí)際意義和理論價(jià)值。生產(chǎn)排程問題又稱生產(chǎn)調(diào)度或生產(chǎn)計(jì)劃，于1954年由S.M.Johnson首先提出，并建立了加工的數(shù)學(xué)模型，同時(shí)提出了優(yōu)化算法。60年代普通的優(yōu)化方法開始用于解決實(shí)際調(diào)度問題。70年代著重于問題復(fù)雜性方面的研究。80年代初，調(diào)度理論結(jié)合實(shí)際生產(chǎn)成為研究的主要問題［1］。國內(nèi)生產(chǎn)調(diào)度研究起步于20世紀(jì)90年代，比國外起步要晚。隨著生產(chǎn)調(diào)度方法的廣泛應(yīng)用，目前國內(nèi)調(diào)度算法的研究已日趨完善，研究的主要方向也不再僅僅局限于調(diào)度理論，而是把理論與實(shí)際相結(jié)合，考慮到了車間問題的復(fù)雜性和多約束性。目前國內(nèi)研究的生產(chǎn)調(diào)度大多把加工時(shí)間混合考慮，只注重生產(chǎn)周期最短，忽略了工件加工的排隊(duì)時(shí)間和運(yùn)輸時(shí)間［2］。

本文針對(duì)目前的研究現(xiàn)狀，將加工時(shí)間、運(yùn)輸時(shí)間和排隊(duì)時(shí)間相分離，結(jié)合不同的時(shí)間權(quán)重，找出適合的生產(chǎn)排程組合，同時(shí)將遺傳算法的選擇算子和變異算子進(jìn)行改進(jìn)，得出針對(duì)實(shí)際問題的可行解。最后通過仿真結(jié)果給出不同時(shí)間權(quán)重對(duì)應(yīng)的收斂圖。

2 批量生產(chǎn)調(diào)度問題描述

結(jié)合車間生產(chǎn)的實(shí)際情況，批量調(diào)度問題可描述為：有N種工件，每種工件有多個(gè)并且包含多道工序，有M臺(tái)機(jī)床，能加工某一種工序的機(jī)床有多臺(tái)，每道工序在不同機(jī)床加工的時(shí)間不同。問如何分配工件的加工順序，使得工件的總加工周期最小［3～4］。同時(shí)該問題還包含以下約束條件：

1）某臺(tái)機(jī)器加工某一工序的時(shí)間是確定的；

2）同一工件加工的工序順序是確定的；

3）同一工件的一道工序可在不同機(jī)器上加工；

4）不同工件的加工工序沒有先后順序約束；

5）生產(chǎn)周期分為加工時(shí)間、排隊(duì)時(shí)間和運(yùn)輸時(shí)間；

6）同種工件即為最小批次，不可分批；

7）每臺(tái)機(jī)床同一時(shí)間只可加工一種工件；

8）加工中的工件不可中斷；

9）在開始時(shí)刻，所有的工件都可被加工。

3 批量生產(chǎn)調(diào)度策略

根據(jù)問題描述，建立以下調(diào)度模型：在調(diào)度系統(tǒng)中，共有13臺(tái)加工機(jī)器，6種工件，每種工件的批次數(shù)量都不相同，每種工件在各個(gè)機(jī)器上的加工時(shí)間也不相同，工序的批次啟動(dòng)時(shí)間即為單個(gè)工件此工序的開始時(shí)間。

3.1 工件加工工序

表1 工件在機(jī)器上的加工時(shí)間

表1為6種工件對(duì)應(yīng)于13個(gè)機(jī)器的加工時(shí)間，為簡(jiǎn)化模型，現(xiàn)假設(shè)每種工件最多只有3種工序，依據(jù)表1，得出每種工件的工序順序如下：

工件1：8種加工順序，對(duì)應(yīng)的機(jī)器號(hào)分別為2-7-11， 1-7-11， 2-6-11， 1-6-11， 2-7-12，1-7-12，2-6-12，1-6-12；

工件2：8種加工順序，對(duì)應(yīng)的機(jī)器號(hào)分別為4-9-0，3-9-0，4-8-0，5-9-0，4-10-0，3-8-0，5-10-0，5-8-0；

工件3：6種加工順序，對(duì)應(yīng)的機(jī)器號(hào)分別為2-3-0，2-4-0，2-5-0，1-3-0，1-4-0，1-5-0；

工件4：4種加工順序，對(duì)應(yīng)的機(jī)器號(hào)分別為2-11-0，1-11-0，2-12-0，1-12-0；

工件5：6種加工順序，對(duì)應(yīng)的機(jī)器號(hào)分別為13-7-9， 13-6-9， 13-7-8， 13-7-10， 13-6-8，13-6-10；

工件6：8種加工順序，對(duì)應(yīng)的機(jī)器號(hào)分別為7-2-11， 6-2-11， 7-2-12， 7-1-11， 6-2-12，6-1-11，7-1-12，6-1-12。

3.2 工件加工時(shí)間

在實(shí)際生產(chǎn)過程中，工件在機(jī)器上的加工是需要裝卸工件和啟動(dòng)機(jī)器的，這些時(shí)間可以算在加工時(shí)間內(nèi)，但機(jī)器和機(jī)器間的運(yùn)輸距離無法忽略，以及同一機(jī)器加工不同工件的等待時(shí)間也需考慮在內(nèi)，機(jī)器間的距離如表2。

3.3 工件加工時(shí)間與等待時(shí)間

一臺(tái)機(jī)器加工兩種零件，后一種零件就需要排隊(duì)等待；不同機(jī)器加工同一零件的不同工序，后一臺(tái)機(jī)器就需要等待零件的前一工序加工完成，同時(shí)機(jī)器和機(jī)器間還存在運(yùn)輸時(shí)間，因此加工時(shí)間和排隊(duì)時(shí)間共分為五種情況。

現(xiàn)說明定義的各個(gè)變量：

tij：工序j在機(jī)器i上的加工完成時(shí)間；

TTdej-1：工序j的緊前工序j-1在機(jī)器de上的批次加工時(shí)間；

TTij：工序j在機(jī)器i上的批次加工時(shí)間；

tranij：加工工序j運(yùn)送到機(jī)器i上的運(yùn)輸時(shí)間；

wij：工序j在機(jī)器i上的排隊(duì)時(shí)間。

情況一：若待加工工件無緊前工序且加工機(jī)器無工件加工，如圖1。

情況二：若待加工工件無緊前工序且加工機(jī)器

表2 機(jī)器間的運(yùn)輸時(shí)間

有工件加工，如圖2。

圖1 加工示意圖

圖2 加工示意圖

情況三：若待加工工件有緊前工序且待加工工件的緊前工序所用時(shí)間大于當(dāng)前機(jī)器加工前一種工件的加工時(shí)間，如圖3。

圖3 加工示意圖

情況四：若待加工工件有緊前工序且待加工工件的緊前工序所用時(shí)間小于當(dāng)前機(jī)器加工前一種工件的加工時(shí)間，待加工工件的運(yùn)輸時(shí)間與工件等待時(shí)間重合，如圖4。

圖4 加工示意圖

情況五：若待加工工件有緊前工序且待加工工件的緊前工序所用時(shí)間小于當(dāng)前機(jī)器加工前一種工件的加工時(shí)間，待加工工件的運(yùn)輸時(shí)間與工件等待時(shí)間部分重合，如圖5。

圖5 加工示意圖

4 批量生產(chǎn)調(diào)度的加權(quán)遺傳算法

4.1 遺傳算法的基本思想

遺傳算法從可能代表問題潛在解集的一個(gè)種群開始，一個(gè)種群由包含基因特征的染色體組成，染色體是經(jīng)過編碼的從性狀到基因的映射。初始種群按照優(yōu)勝劣汰的原則，根據(jù)適應(yīng)度大小挑選若干個(gè)體，通過交叉、變異，產(chǎn)生符合問題解的新的個(gè)體，再從中挑選種群數(shù)量的個(gè)體的一系列遺傳操作。經(jīng)過多次操作，最終得出問題的近優(yōu)解或最優(yōu)解［5］。

交叉運(yùn)算：雙親染色體部分基因相互交換重組，產(chǎn)生新的符合問題解的個(gè)體。

變異運(yùn)算：改變父代染色體的部分基因，產(chǎn)生新的符合問題解的個(gè)體。

選擇運(yùn)算：根據(jù)各個(gè)染色體適應(yīng)度大小，選擇適應(yīng)度高的個(gè)體進(jìn)入下一代。

遺傳算法的步驟［6］如下。

1）根據(jù)問題，隨機(jī)產(chǎn)生符合問題解的初始種群，產(chǎn)生的個(gè)體數(shù)目確定，每個(gè)個(gè)體表現(xiàn)為染色體的基因編碼；

2）根據(jù)每個(gè)個(gè)體的適應(yīng)度判斷是否符合優(yōu)化標(biāo)準(zhǔn)，若符合，輸出最優(yōu)解；若不符合，轉(zhuǎn)第3）；

3）由交叉概率和交叉算子產(chǎn)生新的個(gè)體；

4）由變異概率和變異算子產(chǎn)生新的個(gè)體；

5）通過選擇算子和選擇方法，挑選出種群數(shù)量的優(yōu)化個(gè)體，返回第2）。

遺傳算法的特點(diǎn)［7～8］如下。

1）遺傳算法是將自然選擇和種群遺傳簡(jiǎn)單化后的超啟發(fā)式算法；

2）采用概率化的搜索方法，不需要確定的規(guī)則，只需要設(shè)定正確的適應(yīng)度函數(shù)即可；

3）遺傳算法從問題的串集開始，同時(shí)處理多個(gè)個(gè)體，覆蓋面廣，不容易陷入局部最優(yōu)，可以評(píng)估搜索空間多個(gè)解，實(shí)現(xiàn)并行求解，效率更高；

4）適應(yīng)度函數(shù)不受連續(xù)可微的影響，并且可以任意設(shè)定定義域，使得遺傳算法的應(yīng)用范圍更廣；

5）通過選擇算子、交叉算子和變異算子指導(dǎo)遺傳算法的搜索方向，適當(dāng)?shù)脑O(shè)定交叉概率和變異概率，可以避免算法陷入局部最優(yōu)，利于全局尋優(yōu)；

6）搜索方向并不是無序的，它是有序的搜索，這就決定了遺傳算法比傳統(tǒng)搜索算法有更高的搜索效率；

7）遺傳算法可以方便結(jié)合其他算法或?qū)ζ溥M(jìn)行適當(dāng)改進(jìn)，針對(duì)具體問題可以更快更準(zhǔn)確地求出最優(yōu)解。

基于遺傳算法的諸多特點(diǎn)，多工序的批次生產(chǎn)調(diào)度問題就可以很方便地使用遺傳算法進(jìn)行求解。根據(jù)車間調(diào)度的實(shí)際問題，改進(jìn)傳統(tǒng)遺傳算法的遺傳算子，使其適用于具體問題的最優(yōu)化求解［9］。

4.2 批量調(diào)度遺傳算法

生產(chǎn)調(diào)度實(shí)現(xiàn)算法決定著生產(chǎn)調(diào)度問題的可行性，根據(jù)實(shí)際問題，需要對(duì)遺傳算法進(jìn)行適當(dāng)?shù)母倪M(jìn)，確定初始種群為5，迭代次數(shù)為100，個(gè)體長(zhǎng)度為12。

編碼：這里采用10進(jìn)制編碼，個(gè)體長(zhǎng)度定為12，前6位代表6種工件序號(hào)，每位不可重復(fù)，后6位代表對(duì)應(yīng)的工件的加工順序，每位可重復(fù)。

根據(jù)3.1的加工工序，工件1有8種加工順序，工件2有8種加工順序，工件3有6種加工順序，工件4有4種加工順序，工件5有6種加工順序，工件6有8種加工順序。

染色體為635124354824。

工件對(duì)應(yīng)的加工順序?yàn)?6-3，3-5，5-4，1-8，2-2，4-4。

第一次轉(zhuǎn)換：每個(gè)個(gè)體采用6行3列矩陣表示，根據(jù)初始群體，每行代表對(duì)應(yīng)的工件種類，每列代表加工的順序所用的機(jī)器號(hào)。

第二次轉(zhuǎn)換：每個(gè)個(gè)體采用13行18列矩陣表示，根據(jù)第一次轉(zhuǎn)換結(jié)果，每行代表1-13的機(jī)器號(hào)，每列代表機(jī)器號(hào)加工的工件種類序號(hào)，由此就可詳細(xì)表示出每個(gè)機(jī)器加工各個(gè)工件種類對(duì)應(yīng)的各個(gè)工序排列。

選擇算子：采用錦標(biāo)賽選擇法，隨機(jī)抽取若干染色體，取適應(yīng)度高的個(gè)體進(jìn)入下一代，重復(fù)此方法，直到選到足夠多的個(gè)體為止。

交叉算子：先選擇兩個(gè)染色體作為雙親染色體。

S1：635124354824

S2：452361366178

前6位隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)2和4，后6位也隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)8和10，如果根據(jù)傳統(tǒng)遺傳算法，交叉后結(jié)果為

S11：652324366124

S22：435161354878

產(chǎn)生的后代S11前6位就存在兩個(gè)相同工件2，后6位存在工件不存在的加工順序；S22前6位存在相同工件1，后6位也存在工件不存在的加工順序，都是問題的不可行解。所以需要改進(jìn)傳統(tǒng)遺傳算法的交叉算子，本文采用多點(diǎn)交叉和改進(jìn)的交叉算子相結(jié)合的方法［10］。

每一個(gè)染色體中不可存在相同的工件種類，同時(shí)工件種類的加工順序必須在對(duì)應(yīng)的加工順序中。以上兩個(gè)染色體為例，假設(shè)交叉點(diǎn)為2、4、8、10，則兩個(gè)染色體對(duì)應(yīng)的2-4之間的基因段互相放入對(duì)方染色體之前，同時(shí)檢查前9位，刪除重復(fù)出現(xiàn)的基因位，留下6位。8-10對(duì)應(yīng)的基因段分別互換，檢查后6位對(duì)應(yīng)的加工工件種類，若超出加工的順序序號(hào)，則取序號(hào)的最大值為此工件的加工順序。

S11：523614366124

S22：351426344478

具體操作步驟如下。

1）取種群中兩個(gè)染色體作為雙親染色體；

2）隨機(jī)產(chǎn)生1-6之間的兩個(gè)整數(shù)a和b和7-12之間的兩個(gè)整數(shù)c和d；

3）將兩個(gè)染色體對(duì)應(yīng)的a-b之間的基因段分別放在染色體之前，刪除各個(gè)染色體原本前6位中重復(fù)a-b段的基因；

4）將兩個(gè)染色體對(duì)應(yīng)c-d之間的基因段互換，同時(shí)檢查前6位對(duì)應(yīng)的工件種類的工序順序號(hào)是否超出最大值，若超出，以最大值替換。

按此交叉方法得到的染色體都是可行解，確保了所有個(gè)體都是合法個(gè)體。

變異算子：選擇一個(gè)染色體作為父代染色體。

S1：523614366124

前6位產(chǎn)生一個(gè)變異點(diǎn)3，后6位產(chǎn)生一個(gè)變異點(diǎn)12，根據(jù)傳統(tǒng)遺傳算法，變異結(jié)果為

S11：526614366128

產(chǎn)生的后代S11前6位就存在兩個(gè)相同工件6，后6位就存在工件4沒有的加工順序8，產(chǎn)生的個(gè)體為問題的不可行解。所以需要改進(jìn)傳統(tǒng)遺傳算法的變異算子，本文采用移位變異和交叉基因位相結(jié)合的方法。

每一個(gè)染色體中不可存在相同的工件種類，同時(shí)工件種類的加工順序必須在對(duì)應(yīng)的加工順序中。以此染色體為例，假設(shè)變異點(diǎn)為3和5，則對(duì)應(yīng)的后6位的變異點(diǎn)為9和11，同時(shí)互換3和5、9和11位對(duì)應(yīng)的基因［11～12］。

S11：521634362164

具體操作步驟如下：

1）取種群中的一個(gè)染色體作為父代染色體；

2）隨機(jī)產(chǎn)生1-6之間的兩個(gè)整數(shù)a和b，同時(shí)取后6位對(duì)應(yīng)的整數(shù)a+6，b+6；

3）將染色體a和b對(duì)應(yīng)的基因位以及a+6，b+6對(duì)應(yīng)的基因位互換，得到新的個(gè)體。

按此變異方法得到的染色體都是可行解，確保了所有個(gè)體都是合法個(gè)體［13］。

適應(yīng)度函數(shù)是評(píng)價(jià)種群個(gè)體優(yōu)劣程度的依據(jù)，它給定了解的搜索方向并直接關(guān)系到搜索過程的效率和最終解的質(zhì)量。若適應(yīng)度函數(shù)設(shè)定不當(dāng)，將是搜索過程變得復(fù)雜，解的質(zhì)量也會(huì)大打折扣［14～15］。

本文設(shè)定的適應(yīng)度函數(shù)：總的生產(chǎn)周期等于總最大加工時(shí)間、總的加權(quán)排隊(duì)時(shí)間以及總的加權(quán)運(yùn)輸時(shí)間之和。綜合考慮了所有工件在機(jī)器加工完成的最終時(shí)間最小，同時(shí)所有工件排隊(duì)時(shí)間最小以及所有工件運(yùn)輸時(shí)間最小。

適應(yīng)度函數(shù)：

Cmin為最后一臺(tái)完工機(jī)器的加工時(shí)間；

a1×Wmin為工件總排隊(duì)時(shí)間的加權(quán)值；

a2×Hmin為工件總運(yùn)輸時(shí)間的加權(quán)值。

4.3 批量調(diào)度遺傳算法流程

流程圖6詳細(xì)說明了批次調(diào)度的詳細(xì)步驟，適應(yīng)度函數(shù)采用加權(quán)值，通過改進(jìn)的交叉操作和變異操作，最終得到最優(yōu)個(gè)體。

圖6 批次調(diào)度加權(quán)遺傳算法的流程圖

5 仿真結(jié)果和分析

仿真模型使用實(shí)際數(shù)據(jù)進(jìn)行模擬，設(shè)一共有13臺(tái)機(jī)器，共6種工件，每種工件批次為5、15、12、6、10、3，每種工件最多3道工序，機(jī)器加工時(shí)間為表1，機(jī)器間運(yùn)輸時(shí)間為表2，染色體長(zhǎng)度為12，采用10進(jìn)制編碼。種群規(guī)模為10，同時(shí)對(duì)應(yīng)5種權(quán)值，加快遺傳算法的運(yùn)行速度。迭代次數(shù)為100，交叉概率為0.6，設(shè)置過小會(huì)抑制種群生成新個(gè)體的速度，容易陷入局部最優(yōu)，過大會(huì)破壞種群中的優(yōu)良個(gè)體，使搜索趨于無序化；變異概率為0.001，過小會(huì)抑制產(chǎn)生新個(gè)體的能力，過大會(huì)破壞產(chǎn)生的優(yōu)良個(gè)體。仿真結(jié)果如下。

橫坐標(biāo)表示迭代次數(shù)，縱坐標(biāo)表示每代的最小生產(chǎn)周期。

批量生產(chǎn)調(diào)度加權(quán)算法的各個(gè)權(quán)值優(yōu)化結(jié)果為

排隊(duì)權(quán)值1，運(yùn)輸權(quán)值0：425316416121；

排隊(duì)權(quán)值0.75，運(yùn)輸權(quán)值0.25：425361423334；

排隊(duì)權(quán)值0.5，運(yùn)輸權(quán)值0.5：534261414522；

排隊(duì)權(quán)值0.25，運(yùn)輸權(quán)值0.75：534612514225；

排隊(duì)權(quán)值0，運(yùn)輸權(quán)值1：453261231552。

如圖7所示，總的生產(chǎn)周期在極小概率會(huì)相同，大部分情況如圖8所示。

圖7 批次調(diào)度加權(quán)遺傳算法收斂圖

圖8 批次調(diào)度加權(quán)遺傳算法收斂圖

此時(shí)的批量生產(chǎn)調(diào)度加權(quán)算法的各個(gè)權(quán)值優(yōu)化結(jié)果為

排隊(duì)權(quán)值1，運(yùn)輸權(quán)值0：463215213163；

排隊(duì)權(quán)值0.75，運(yùn)輸權(quán)值0.25：654321142312；

排隊(duì)權(quán)值0.5，運(yùn)輸權(quán)值0.5：543621621316；

排隊(duì)權(quán)值0.25，運(yùn)輸權(quán)值0.75：432561432452；

排隊(duì)權(quán)值0，運(yùn)輸權(quán)值1：543621541158。

通過多次仿真結(jié)果分析和研究表明，當(dāng)機(jī)器間沒有運(yùn)輸距離時(shí)，也即運(yùn)輸權(quán)重為0時(shí)，生產(chǎn)周期為所有周期中最?。划?dāng)運(yùn)輸權(quán)值增大時(shí)，總生產(chǎn)周期也在慢慢變大，當(dāng)排隊(duì)時(shí)間權(quán)重和運(yùn)輸時(shí)間權(quán)重以及工件生產(chǎn)順序達(dá)到一個(gè)平衡時(shí)，可以接近最小生產(chǎn)周期；即使不同的加工次序，當(dāng)機(jī)器的運(yùn)輸權(quán)重和排隊(duì)權(quán)重互相協(xié)調(diào)時(shí)，也可能會(huì)有相同的生產(chǎn)周期，這就需要企業(yè)針對(duì)本廠的工件批次和工件加工順序，合理安排排隊(duì)權(quán)重和運(yùn)輸權(quán)重，以期得到最小的生產(chǎn)周期。

6 結(jié)語

系統(tǒng)研究了多工序的批量生產(chǎn)調(diào)度問題，主要著重于批次生產(chǎn)的時(shí)間總和問題，將總的生產(chǎn)周期分為加工時(shí)間、排隊(duì)時(shí)間和運(yùn)輸時(shí)間，運(yùn)用不同的時(shí)間權(quán)重，結(jié)合改進(jìn)的遺傳算法的編碼方式、改進(jìn)的交叉算子和改進(jìn)的變異算子，通過加權(quán)的適應(yīng)度函數(shù)，給出了各個(gè)不同時(shí)間權(quán)重下的總生產(chǎn)周期。仿真結(jié)果表明，工件的不同順序結(jié)合適當(dāng)?shù)臅r(shí)間權(quán)重可得出更小的生產(chǎn)周期，改進(jìn)的遺傳算法使搜索性能大大提升，確保了解的合理性、準(zhǔn)確性。