遺傳算法求解帶權重的生產調度問題*

王召陽 高 尚

（江蘇科技大學計算機學院 鎮江 212001）

1 引言

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

本文針對目前的研究現狀，將加工時間、運輸時間和排隊時間相分離，結合不同的時間權重，找出適合的生產排程組合，同時將遺傳算法的選擇算子和變異算子進行改進，得出針對實際問題的可行解。最后通過仿真結果給出不同時間權重對應的收斂圖。

2 批量生產調度問題描述

結合車間生產的實際情況，批量調度問題可描述為：有N種工件，每種工件有多個并且包含多道工序，有M臺機床，能加工某一種工序的機床有多臺，每道工序在不同機床加工的時間不同。問如何分配工件的加工順序，使得工件的總加工周期最小［3～4］。同時該問題還包含以下約束條件：

1）某臺機器加工某一工序的時間是確定的；

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

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

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

5）生產周期分為加工時間、排隊時間和運輸時間；

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

7）每臺機床同一時間只可加工一種工件；

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

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

3 批量生產調度策略

根據問題描述，建立以下調度模型：在調度系統中，共有13臺加工機器，6種工件，每種工件的批次數量都不相同，每種工件在各個機器上的加工時間也不相同，工序的批次啟動時間即為單個工件此工序的開始時間。

3.1 工件加工工序

表1 工件在機器上的加工時間

表1為6種工件對應于13個機器的加工時間，為簡化模型，現假設每種工件最多只有3種工序，依據表1，得出每種工件的工序順序如下：

工件1：8種加工順序，對應的機器號分別為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種加工順序，對應的機器號分別為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種加工順序，對應的機器號分別為2-3-0，2-4-0，2-5-0，1-3-0，1-4-0，1-5-0；

工件4：4種加工順序，對應的機器號分別為2-11-0，1-11-0，2-12-0，1-12-0；

工件5：6種加工順序，對應的機器號分別為13-7-9， 13-6-9， 13-7-8， 13-7-10， 13-6-8，13-6-10；

工件6：8種加工順序，對應的機器號分別為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 工件加工時間

在實際生產過程中，工件在機器上的加工是需要裝卸工件和啟動機器的，這些時間可以算在加工時間內，但機器和機器間的運輸距離無法忽略，以及同一機器加工不同工件的等待時間也需考慮在內，機器間的距離如表2。

3.3 工件加工時間與等待時間

一臺機器加工兩種零件，后一種零件就需要排隊等待；不同機器加工同一零件的不同工序，后一臺機器就需要等待零件的前一工序加工完成，同時機器和機器間還存在運輸時間，因此加工時間和排隊時間共分為五種情況。

現說明定義的各個變量：

tij：工序j在機器i上的加工完成時間；

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

TTij：工序j在機器i上的批次加工時間；

tranij：加工工序j運送到機器i上的運輸時間；

wij：工序j在機器i上的排隊時間。

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

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

表2 機器間的運輸時間

有工件加工，如圖2。

圖1 加工示意圖

圖2 加工示意圖

情況三：若待加工工件有緊前工序且待加工工件的緊前工序所用時間大于當前機器加工前一種工件的加工時間，如圖3。

圖3 加工示意圖

情況四：若待加工工件有緊前工序且待加工工件的緊前工序所用時間小于當前機器加工前一種工件的加工時間，待加工工件的運輸時間與工件等待時間重合，如圖4。

圖4 加工示意圖

情況五：若待加工工件有緊前工序且待加工工件的緊前工序所用時間小于當前機器加工前一種工件的加工時間，待加工工件的運輸時間與工件等待時間部分重合，如圖5。

圖5 加工示意圖

4 批量生產調度的加權遺傳算法

4.1 遺傳算法的基本思想

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

交叉運算：雙親染色體部分基因相互交換重組，產生新的符合問題解的個體。

變異運算：改變父代染色體的部分基因，產生新的符合問題解的個體。

選擇運算：根據各個染色體適應度大小，選擇適應度高的個體進入下一代。

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

1）根據問題，隨機產生符合問題解的初始種群，產生的個體數目確定，每個個體表現為染色體的基因編碼；

2）根據每個個體的適應度判斷是否符合優化標準，若符合，輸出最優解；若不符合，轉第3）；

3）由交叉概率和交叉算子產生新的個體；

4）由變異概率和變異算子產生新的個體；

5）通過選擇算子和選擇方法，挑選出種群數量的優化個體，返回第2）。

遺傳算法的特點［7～8］如下。

1）遺傳算法是將自然選擇和種群遺傳簡單化后的超啟發式算法；

2）采用概率化的搜索方法，不需要確定的規則，只需要設定正確的適應度函數即可；

3）遺傳算法從問題的串集開始，同時處理多個個體，覆蓋面廣，不容易陷入局部最優，可以評估搜索空間多個解，實現并行求解，效率更高；

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

5）通過選擇算子、交叉算子和變異算子指導遺傳算法的搜索方向，適當的設定交叉概率和變異概率，可以避免算法陷入局部最優，利于全局尋優；

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

7）遺傳算法可以方便結合其他算法或對其進行適當改進，針對具體問題可以更快更準確地求出最優解。

基于遺傳算法的諸多特點，多工序的批次生產調度問題就可以很方便地使用遺傳算法進行求解。根據車間調度的實際問題，改進傳統遺傳算法的遺傳算子，使其適用于具體問題的最優化求解［9］。

4.2 批量調度遺傳算法

生產調度實現算法決定著生產調度問題的可行性，根據實際問題，需要對遺傳算法進行適當的改進，確定初始種群為5，迭代次數為100，個體長度為12。

編碼：這里采用10進制編碼，個體長度定為12，前6位代表6種工件序號，每位不可重復，后6位代表對應的工件的加工順序，每位可重復。

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

染色體為635124354824。

工件對應的加工順序為 6-3，3-5，5-4，1-8，2-2，4-4。

第一次轉換：每個個體采用6行3列矩陣表示，根據初始群體，每行代表對應的工件種類，每列代表加工的順序所用的機器號。

第二次轉換：每個個體采用13行18列矩陣表示，根據第一次轉換結果，每行代表1-13的機器號，每列代表機器號加工的工件種類序號，由此就可詳細表示出每個機器加工各個工件種類對應的各個工序排列。

選擇算子：采用錦標賽選擇法，隨機抽取若干染色體，取適應度高的個體進入下一代，重復此方法，直到選到足夠多的個體為止。

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

S1：635124354824

S2：452361366178

前6位隨機產生兩個交叉點2和4，后6位也隨機產生兩個交叉點8和10，如果根據傳統遺傳算法，交叉后結果為

S11：652324366124

S22：435161354878

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

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

S11：523614366124

S22：351426344478

具體操作步驟如下。

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

2）隨機產生1-6之間的兩個整數a和b和7-12之間的兩個整數c和d；

3）將兩個染色體對應的a-b之間的基因段分別放在染色體之前，刪除各個染色體原本前6位中重復a-b段的基因；

4）將兩個染色體對應c-d之間的基因段互換，同時檢查前6位對應的工件種類的工序順序號是否超出最大值，若超出，以最大值替換。

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

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

S1：523614366124

前6位產生一個變異點3，后6位產生一個變異點12，根據傳統遺傳算法，變異結果為

S11：526614366128

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

每一個染色體中不可存在相同的工件種類，同時工件種類的加工順序必須在對應的加工順序中。以此染色體為例，假設變異點為3和5，則對應的后6位的變異點為9和11，同時互換3和5、9和11位對應的基因［11～12］。

S11：521634362164

具體操作步驟如下：

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

2）隨機產生1-6之間的兩個整數a和b，同時取后6位對應的整數a+6，b+6；

3）將染色體a和b對應的基因位以及a+6，b+6對應的基因位互換，得到新的個體。

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

適應度函數是評價種群個體優劣程度的依據，它給定了解的搜索方向并直接關系到搜索過程的效率和最終解的質量。若適應度函數設定不當，將是搜索過程變得復雜，解的質量也會大打折扣［14～15］。

本文設定的適應度函數：總的生產周期等于總最大加工時間、總的加權排隊時間以及總的加權運輸時間之和。綜合考慮了所有工件在機器加工完成的最終時間最小，同時所有工件排隊時間最小以及所有工件運輸時間最小。

適應度函數：

Cmin為最后一臺完工機器的加工時間；

a1×Wmin為工件總排隊時間的加權值；

a2×Hmin為工件總運輸時間的加權值。

4.3 批量調度遺傳算法流程

流程圖6詳細說明了批次調度的詳細步驟，適應度函數采用加權值，通過改進的交叉操作和變異操作，最終得到最優個體。

圖6 批次調度加權遺傳算法的流程圖

5 仿真結果和分析

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

橫坐標表示迭代次數，縱坐標表示每代的最小生產周期。

批量生產調度加權算法的各個權值優化結果為

排隊權值1，運輸權值0：425316416121；

排隊權值0.75，運輸權值0.25：425361423334；

排隊權值0.5，運輸權值0.5：534261414522；

排隊權值0.25，運輸權值0.75：534612514225；

排隊權值0，運輸權值1：453261231552。

如圖7所示，總的生產周期在極小概率會相同，大部分情況如圖8所示。

圖7 批次調度加權遺傳算法收斂圖

圖8 批次調度加權遺傳算法收斂圖

此時的批量生產調度加權算法的各個權值優化結果為

排隊權值1，運輸權值0：463215213163；

排隊權值0.75，運輸權值0.25：654321142312；

排隊權值0.5，運輸權值0.5：543621621316；

排隊權值0.25，運輸權值0.75：432561432452；

排隊權值0，運輸權值1：543621541158。

通過多次仿真結果分析和研究表明，當機器間沒有運輸距離時，也即運輸權重為0時，生產周期為所有周期中最小；當運輸權值增大時，總生產周期也在慢慢變大，當排隊時間權重和運輸時間權重以及工件生產順序達到一個平衡時，可以接近最小生產周期；即使不同的加工次序，當機器的運輸權重和排隊權重互相協調時，也可能會有相同的生產周期，這就需要企業針對本廠的工件批次和工件加工順序，合理安排排隊權重和運輸權重，以期得到最小的生產周期。

6 結語

系統研究了多工序的批量生產調度問題，主要著重于批次生產的時間總和問題，將總的生產周期分為加工時間、排隊時間和運輸時間，運用不同的時間權重，結合改進的遺傳算法的編碼方式、改進的交叉算子和改進的變異算子，通過加權的適應度函數，給出了各個不同時間權重下的總生產周期。仿真結果表明，工件的不同順序結合適當的時間權重可得出更小的生產周期，改進的遺傳算法使搜索性能大大提升，確保了解的合理性、準確性。