改進的遺傳算法求解柔性作業車間調度問題

劉月凡，朱 星

(大連交通大學軟件學院，遼寧 大連116028)*

0 引言

作業車間調度問題(Job-shop scheduling problem，JSP)是研究生產線調度問題最常用的模型之一［1］，也是實現先進制造和提高生產效率的基礎和關鍵［2］.柔性作業車間調度問題(Flexible jobshop scheduling problem，FJSP)是傳統作業車間調度問題的擴展，在傳統的作業車間調度問題中，每個工件的加工工序是確定的，每一道工序的加工機器和加工時間也是確定的，而在柔性作業車間調度問題中，每個工件的每一道工序可以在多個可選擇的加工機器上進行加工，并且不同的加工機器所需要的加工時間是不同的，增加了調度的靈活性，比較符合生產的實際情況［3］.

柔性作業車間調度問題已經被證明是更復雜的NP-Hard問題，因而難以取得最優解.目前，求解FJSP的常用方法有禁忌搜索(TS)，模擬退火(SA)和遺傳算法(GA)等［4-6］.其中遺傳算法以其操作簡單、魯棒性強、搜索全局最優解速度快等特點，在生產調度領域得到了廣泛的應用.

遺傳算法是由美國J.Holland教授于1975年提出的，是一種模擬自然進化過程的一種優化算法.由于傳統的遺傳算法存在著較大的缺陷，國內外學者已從不同角度對其進行了改進，本文對傳統遺傳算法的初始種群進行了改進，以提高初始解的質量.

1 柔性作業車間調度模型

設有 n個待加工工件 J(J1，J2，…，Jn)，在 m臺設備上加工 M(M1，M2，…，Mm)，每個工件 Ji有Pi(Pi1，Pi2，…，Pin)道工序，每道工序可在一臺或多臺設備上加工，同一道工序在不同設備上加工的時間可能不等，工序 Pik的可選機器集為Mik(Mik?M)，每臺設備的加工時間從0開始，加工完所有工件的完成時間為ETMi.本文以最小化最大完工時間為性能指標，其目標函數為:

f(x)=min(max(ETMi))，1≤ i≤ m

模型需滿足如下約束條件:

(1)同一工件的工序加工順序確定;

(2)每道工序必須在它的上一道工序加工完成后才能開始加工;

(3)每道工序只能選擇一臺設備進行操作;

(4)每臺設備在同一時間只能加工一個工件的一道工序;

(5)每道工序在設備上操作時都不允許被中斷;

(6)不同工件工序之間沒有先后約束條件.一個包含3個工件、5臺機器的FJSP的問題描述如表1所示.

表1 3×5 FJSP問題加工時間表

2 算法的設計

(1)基因編碼

常用的遺傳算法編碼方案有二進制編碼、格雷碼編碼、矩陣編碼、自然數編碼等，本文采用自然數編碼，每條染色體表示一個可行解，同時采用雙層編碼，第一層編碼為基于工件的工序編碼，編碼長度為所有工件工序之和，基因值代表工件號，基因值出現的次數代表該工件的工序總數，第二層編碼為對應于第一層工件工序的機器編碼，所以編碼長度也為所有工件工序之和.以表1為例，圖1中染色體表示的工序順序為 (O31，O11，O12，O21，O22，O32，O13，O33)，染色體表示的機器序列為(M2，M4，M2，M1，M4，M5，M3，M4).

圖1 基于工序和機器的編碼

(2)產生初始種群

初始種群的優良對生物進化會產生很大的影響，本文對初始種群的機器選擇進行了改進，首先隨機生成初始種群的工序編碼，工序編碼生成后就要對應生成機器編碼，每個工件工序在對應可選機器集中選擇機器時，是以不同的概率的來選擇不同的機器，機器加工時間短的以大概率被選擇，相比之下，機器加工時間長的以小概率被選擇，這樣既保證了機器選擇的隨機性，也優化了初始種群.

(3)適應度函數的確定

本文以最小化最大完工時間為目標函數，故選擇全部工件完工時間作為評價種群優劣的標準，設n個待加工工件在m(M1，M2，…，Mm)臺設備上加工，所有加工工件工序在設備上的最后完工時間為 ETMi(i=1，2，…，m)，T=max(ETMi)，則適應度函數fi=1/T，T越小，則適應度越大，即個體越優.

(4)選擇

選擇操作的目的是為了保留優良個體，使他們可以遺傳到下一代.本文采用精英保留策略和輪盤賭法相結合的方法，對父代個體和子代個體進行選擇時直接將最優個體和次優個體遺傳到下一代，然后對剩余的個體采用輪盤賭法進行選擇，選擇出p-2個個體到下一代進行遺傳操作.若種群規模為p，個體i的適應度為fi，則個體i被選擇的概率pi為

即適應度越高的個體被選擇的概率就越大.

(5)交叉

交叉操作是產生新個體的主要方法，提高全局搜索能力［7］.本文采用單點交叉方式，即隨機產生一個交叉點，交換交叉點后的基因.從種群中隨機選擇兩個個體，交換兩個個體工序編碼的交叉點后面的基因，將交叉后工件多余的工序替換為其他工件缺失的工序;機器部分則按交叉前工件工序所選擇的機器進行相應調整以保證其子代染色體的合法性.

(6)變異

變異操作的目的是改變算法的局部搜索能力，有助于維持進化群體的多樣性，防止過早陷入局部最優［8］.本文采用互換方式，即隨機產生兩個變異點，交換兩點的基因值.從種群中隨機選擇一個個體，對該個體的工序編碼部分隨機產生兩個變異點，交換兩點的基因值，同時將交換的基因位所對應的機器號也進行交換.

3 仿真實例分析

表2給出了6×6(6個工件，6臺機器)FJSP的加工工序，機器選擇和加工時間矩陣表.分別用標準遺傳算法和本文提出的改進遺傳算法對工件最小化最大完工時間進行優化計算，并分析優化計算結果.

遺傳算法采用以下參數:種群規模為100，進化代數為100，交叉概率Pc=0.8，變異概率Pm=0.1.算法運行10次，最優的選擇如圖2、3所示.

表2 6個工件在6臺機器上FJSP實例

從圖2，3中可以看出，標準遺傳算法的最大完工時間為20，收斂代數為75代左右;改進遺傳算法的最大完工時間為16，收斂代數為35代左右.改進遺傳算法既縮短了工件完工時間，也加快了收斂代數.從而驗證了改進遺傳算法的可行性.

4 結論

傳統遺傳算法在進行種群初始化時采用的大多是隨機選擇方式，而本文提出了一種新的種群初始化方法，提高了種群初始解的質量.最后對改進遺傳算法進行了仿真實驗，并將結果與標準遺傳算法進行比較，結果表明了本算法的優越性和可行性.

［1］JAIN A S，MEERAN S.Deterministic job-shop scheduling:Past，present and future［J］.European Journal of Operational Research，1999，113(2):390-434.

［2］彭建剛，劉明周，張銘鑫，等.基于改進非支配排序的云模型進化多目標柔性作業車間調度［J］.機械工程學報，2014，50(12):198-205.

［3］張國輝，石楊.基于改進遺傳算法求解柔性作業車間調度問題［J］.機械科學與技術，2011，30(11):1890-1894.

［4］MASTROLILLI M，GAMBARDELLA L M.Effective neighborhood functions for the flexible job shop problem［J］.Journal of Scheduling，2000，3(1):3-20.

［5］張維存，鄭丕諤，吳曉丹.蟻群遺傳算法求解能力約束的柔性作業車間調度問題［J］.計算機集成制造系統，2007，13(2):333-362.

［6］張超勇，饒運清，李培根，等.柔性作業車間調度問題的兩級遺傳算法［J］.機械工程學報，2007，43(4):119-124.

［7］李運霞，杜娟，孫王路.基于多種群遺傳算法的路徑柔性車間調度問題［J］.組合機床與自動化加工技術，2014(3):152-155.

［8］周俊虎，平傳娟，劉建忠，等.基于遺傳算法的動力配煤模型［J］.煤炭學報，2003，28(5):547-551.