基于遺傳算法的路徑柔性作業車間調度優化

謝 皓，應保勝，袁 波

（武漢科技大學機械自動化學院，湖北武漢，430081）

傳統的作業車間調度問題中，工件的加工工序是確定的，某道工序的加工機器及加工時間也是確定的，而路徑柔性作業車間調度則存在加工工藝路線中機器可變的情況，即工件的同一工序可以選擇不同的機器進行加工，并且在不同機器上的加工時間也可能不同［1］。因此，路徑柔性作業車間調度優化問題更為復雜。

工件的每道工序可以選擇所有的加工機器來完成的調度稱為完全路徑柔性作業車間調度；每道工序只能在部分機器上進行加工的調度稱為部分路徑柔性作業車間調度［2］。在一般的加工工廠中，機器的數量和功能都有一定的限制，所以部分路徑柔性車間調度問題能更真實地反映實際情況。本文即以部分路徑柔性作業車間調度為研究對象，以最長完工時間最短化為優化目標建立調度模型，采用遺傳算法進行模型求解，針對傳統遺傳算法中編碼方法單一的問題，提出一種基于工序與機器編碼相融合的編碼方法，并通過算例對算法的有效性進行分析。

1 調度模型的建立

路徑柔性作業車間調度問題可描述為：在一個加工車間中，有m臺加工機床和n個待加工的工件，每個工件須經過一道或者多道工序，其加工順序是確定的，同時每一道工序又可以在一臺或多臺不同的機器上進行加工，每道工序的加工時間隨加工機器的不同而改變。調度目標是為每個工件的每道工序安排加工機器以及確定不同加工工件之間的順序，以得到最優的完工時間。

建立這類車間調度問題的數學模型之前，先定義變量如下：i為工件序號，i＝1，2，…，n；k為機器序號，k＝1，2，…，m；j為工件的工序號；hi為工件i總的加工工序數；tijk為在機床k上加工工件i的第j道工序所花的時間；sij為工件i的第j道工序起始時間；eij為工件i的第j道工序結束時間；mij為工件i的第j道工序可選的機器數；ci為工件i最后一道工序完成的時間；R為一個無窮大的正整數；

模型的約束條件有兩類：

（1）加工順序約束，即工件i的第j道工序必須滿足自身的加工時間約束（見式（1）），且工件i的第j＋1道工序必須在第j道工序完成后才能開始（見式（2））。

（2）資源約束，即在一個確定的時刻，同一臺機床只能加工一個工件的一道工序，在該工序完工后才能開始加工下一個（見式（3）），并且同一道工序只能在一臺機床上加工（見式（4））。

以最長完工時間最短化為調度優化目標，其目標函數為：

2 遺傳算法設計

2.1 編碼設計

用遺傳算法求解作業車間調度問題可以采用基于工序順序的編碼方法［3］，但這種方法要求工件每道工序的加工機器是固定的，而在路徑柔性作業車間調度中，機器是可以選擇的，因此本文設計了一種基于工序和機器編碼相融合的編碼方法。

表1 路徑柔性作業車間調度原始數據Table 1 Data of the path flexible job－shop scheduling

從表1中可以看出，工件1的第一道工序可在M1或M2上加工，第二道工序可在M3或M4上加工，第三道工序只能選擇M4進行加工，其余以此類推。隨機選擇一個加工序列（即染色體）（1，2，5，4，1，1，2，3，2，4，3，5，4，3，5），染色體中的1～5為工件號，每個序號在染色體中出現的次數與其加工工序數相等，第一次出現某個序號，表示該序號對應工件的第一道加工工序，第二次出現則對應該工件的第二道工序，以此類推，一個可行的工序序列可以通過這樣一個數字串來表示。

將工序編碼和機器編碼得到的染色體基因相同的位置一一對應起來，形成一個二維矩陣，矩陣的第一行為工序編碼，第二行為機器編碼，從而得到一個融合工序和機器編碼的完整染色體［4］。需要特別說明的是，在產生第二行染色體時按照下面的表述來進行：對應第一行的某道工序Er，如果該工序加工時可以選用的機器數EM＞1，就用0～（EM－1）之間的一個數來表示Er的加工機器號，0表示Er由其可選用的第一臺機器加工，1表示Er由其可選用的第二臺機器加工，等等。如果工序Er可以選用的機器是惟一的，則用符號“－”來表示。通過矩陣兩行之間的對應，就可以找到每道工序的加工機器。

例如，對于一個染色體：

矩陣的第一列表示工件1的第一道工序在其可選用的第一臺機床上加工，根據表1可知該機床為M1；矩陣的第三列表示工件5的第一道工序只能在惟一的一臺機床上加工，根據表1可知該機床為M3；矩陣的第五列表示工件1的第二道工序在其可選用的第二臺機床上加工，根據表1可知該機床為M4。通過類似的解碼，得到一個可行的調度方案為（E111，E214，E513，E415，E124，E134，E222，E311，E233，E422，E325，E522，E431，E333，E534），其中Eijk表示工件i的第j道工序在機床k上加工。

2.2 選擇算子

選擇操作是為了避免有效基因的損失，因此適應度高的個體更容易生存下來。適應度函數一般由目標函數轉換而來，本文的優化目標是最長加工時間最短化，可將目標函數值C的倒數作為個體的適應度f。

采用輪盤賭選擇方法，個體p的選擇概率為：

式中：M為種群大小。

2.3 交叉和變異算子

在進行交叉操作前，通過一種附加的方法產生新個體，以達到擴大搜索范圍的目的。具體方法是：對于某些可以由多臺機器進行加工的工序，隨機變化染色體第二行的值。例如，對于個體矩陣第二行中帶有下劃線的數字被隨機選擇出來，然后將數字在可行范圍內隨機進行變換，就可以得到如下個體：

從而使某些工序的加工機器發生了變化。

交叉操作采用交換串的方法進行，即隨機選擇染色體中的兩個位置，然后對這兩點之間的串信息進行交換。進行交換后有些工件的工序會多出來，有些工件的工序會缺少一部分。找出遺失的工序，用多出來的工序進行替換。例如，有兩個染色體：

染色體中箭頭所示為交叉位置。在交叉過程中，先保留第二行的加工機器信息，只對矩陣的第一行進行操作，得到：

交叉后需要對染色體進行合法性檢測。從產生的第一個子代offp1中可以看到，工件4的序號只在染色體中出現了一次，而工件1和工件2的序號在染色體中都出現了4次，這樣的染色體不是合法的解，需要刪掉多余信息，同時補全遺失的基因。在染色體中可以隨機選擇一個1和2，然后將其換成工號4。在第二個子代offp2中也出現了這種情況，需要進行類似變換。

經過合法性檢測之后，將第二行的機器信息補充上去，同時加工信息在交叉前后必須保持不變，得到：

常用的變異方式有互換、逆序和插入等，本文采用插入方式，即隨機選定一個基因位置，然后將其插入隨機選定的另外一個位置中，其他基因序列不變。需要重點注意的是，在變異前后一定要保證加工機器不能改變。例如，個體

隨機選擇第一行中的13號基因位，然后隨機選擇5號基因位為需要插入的位置。在插入前，先保留第二行的機器信息，插入完成后，再將機器信息填上去。經過變異操作后得到以下個體：

3 算例分析

對一個8×8的路徑柔性作業車間調度問題進行計算，其原始加工數據來源于文獻［5］。優化目標為加工時間最短，初始種群隨機產生，種群個體數為50，迭代次數為300，交叉概率為0.8，變異率為0.04。通過連續10次運行，得到最優調度如圖1所示，圖中方框內數字為工件序號。

圖1 最優調度方案Fig.1 Optimal scheduling solution

圖2為本文遺傳算法和文獻［5］中算法的收斂曲線比較。由圖2可見，本文算法得出的最優解為14，文獻［5］得出的最優解為15。同時，本文算法在150代左右就開始收斂，而文獻［5］中算法在200代以后才達到了最優值，因此相比于文獻［5］的算法，本文算法收斂更迅速，所得調度方案更優。

圖2 收斂曲線Fig.2 Convergence curves

4 結語

本文采用遺傳算法求解部分路徑柔性作業車間調度問題。有別于傳統基于工序的染色體編碼方法，本文將工序編碼和機器編碼相結合，提出一種二維矩陣編碼方法，設計出相應的遺傳算子，并通過算例驗證了本文所給算法的可行性與有效性。

［1］ 張國輝，高亮，李培根.改進遺傳算法求解柔性作業車間調度問題［J］.機械工程學報，2009，45（7）：145－148.

［2］ 張超勇，李培根.柔性作業車間調度問題的兩級遺傳算法［J］.機械工程學報，2007，43（4）：119－124.

［3］ 谷峰，陳華平.病毒遺傳算法在柔性工作車間調度中的應用［J］.系統工程與電子技術，2006，27（11）：139－142.

［4］ 王小平，曹立明.遺傳算法——理論應用與軟件實現［M］.西安：西安交通大學出版社，2002：28－35.

［5］ Hillier F S，Lieberman G J.Introduction to operations research［M］.Peking：Mechanical Industry Press，2008：129－150.