基于遺傳算法的柔性車間作業調度

華北電力大學自動化系 白 康

1.引言

在基本的車間作業調度問題(Job Shop Problem，簡稱JSP)中，所有工件的工序都只能由指定的某一臺機器進行加工。隨著加工技術、自動化技術的發展，特別是柔性制造系統的出現，此傳統限制已被突破，工件具有多個可選擇的加工路線，即路徑柔性已經成為生產的實際需求。生產技術的進步推動著調度理論研究的進深，具有柔性路徑的柔性車間作業調度(Flexible Job Shop Problem，簡稱FJSP)研究也開始進入人們的視野并引起重視[1-3]。

目前，遺傳算法以其優良的計算性能和顯著的應用效果，在求解JSP問題和FJSP問題中獲得了很大的成功[4-11]。本文使用遺傳算法來求解FJSP問題，提出了多維矩陣的編碼方式，以及相應的選擇、交叉、變異操作設計，保證遺傳操作每一步產生的染色體都是合法的，避免了傳統柔性車間作業調度中繁瑣的染色體合法化修復工作。最后用一個調度實例驗證了算法的正確性和有效性。

2.調度問題描述

n種工件J={Ji|i=1，…，n}在一個由m臺不同的加工機器組成的制造系統中進行加工。加工工件Ji需要p(i)道工序，每道工序都有一個可選的機器集合，其加工時間隨機器的選擇不同而變化。調度目標是確定每臺機器上各工件的加工順序及開工時間，使得系統的最大完成時間Cmax最小，同時給出滿足要求的活動調度。假設：

(1)各工件經過準備時間后即可開始加工；

(2)每個工件在某一個時刻只能在一臺機器上加工，中途不能打斷；

(3)每臺機器每次只能加工一個工件；

(4)不考慮工件之間的加工優先權。

3.遺傳算子設計

3.1 適應度函數f(i)

染色體i的適應度值由以下公式給出，其中C是一個大的正整數。

3.2 編碼

定義染色體為矩陣ch[3][op]，該染色體蘊涵工序和機器選擇的雙重信息。

第一行是基于工序的編碼：數字i代表工件Ji。從左到右掃描，數字i的第j次出現代表工件Ji的第j道工序，記為Oij。

第二行是基于機器的編碼：[k11，k12，…，k1p(1)，…，kn1，kn2，…，knp(n)]，其中kij表示工序Oij所選擇的機器號碼。

第三行提供了加工時間的信息：[t11，t12，…，t1p(1)，…，tn1，tn2，…，tnp(n)]，其中tij代表工序Oij在機器kij上進行加工所需要的加工時間。

3.3 交叉與變異

為了避免交叉操作之后產生非法個體(某道工序選擇了不可用的機器)，規定僅僅對染色體的第二行、第三行數據，以概率pc進行兩點交叉操作。

設計兩種變異算子。

對染色體第一行數據，以概率pmop進行互逆變異操作，其目的在于生成新的調度。

對染色體第二行數據，以概率pmch改變某基因的值，注意要保證選擇的機器合法。之后改變染色體第三行相應位置上的值，賦予其新機器上的加工時間。

以上的編碼方式結合交叉、變異操作可使得生成的染色體在工序和機器選擇方面都是合法染色體。

3.4 活動調度的調整

對染色體解碼時，從左到右依次掃描第一行基于工序的編碼串，確定工序信息Oij，之后在第二行的編碼串中找到該工序選擇的機器號碼，掃描完畢即得到了該染色體對應的調度形式。按照這種解碼方式一般只能得到半活動調度，而不是活動調度[12]。因此，將一種插入式算法嵌入到適應度計算過程中，在有必要時調整染色體的基因序列，使其解碼后生成活動調度。

這種插入算法針對所有工件的非首道工序進行處理，將其插入到對應機器上最佳可行的加工時刻安排加工，以這種方式保證所有工序都安排在最佳可行的地方，使得機器利用率最大化。

stij：當前工序Oij的開工時間；

opij：當前工序Oij的加工時間，j＞1；

fti(j-1)：同一工件前道工序Oi(j-1)的完工時間，j＞1；

ftm：工序Oij所選用機器目前的可用時間；

stm：同一機器上前道工序的開工時間；

在基于工序的編碼方式下，各個工件的加工已經按照其工藝順序進行。給定染色體，設系統中所有機器的可用時間為0，所有待加工工件的初始可用時間為0。從左到右掃描染色體第一行數據，確定工序Oij的加工開始時間：

圖1 活動調度的調整

{對每一道工序ch[0][k-1]，判斷其工序信息Oij；

調整過程：代表當前工序Oi的數字為a，代表同一臺機器上前道工序的數字為b。在染色體第一行編碼串中，將a提到b之前。

圖1的甘特圖中，字符串“i–j”表示工序Oij。圖1(a)顯示：工序O11的完工時間ft11=2；工序O21在st2=5時刻開始加工，加工完畢后有ft2=8；工序O12的加工時間op12=2。因滿足條件(ft11+op12)＜st2，圖1(a)是半活動調度。將M2的加工順序調整為O12、O21，即st12=ft11，調整后并不延遲工序O12的加工，如圖1(b)所示成為活動調度。對比圖1(a)和圖1(b)可知，將非活動調度調整成活動調度后，正規性能指標必然有所改善。

表1 6機器、4工件的加工信息表

圖2 4′6柔性車間作業活動調度結果 圖3 4′6柔性車間作業活動調度甘特圖

3.5 選擇

采用適應度比例方法，并執行保優策略。即當進行交叉、變異等操作時，生成的子代種群和父代種群合并成一個新的種群，對新種群應用適應度比例方法，即輪盤賭方法進行選擇，且保存當代最優個體，即適應度最大且所有機器的總完工時間最小的染色體。

4.實例仿真

以表1所示的調度問題為例，表格中的數字代表各工序在相應機器上的加工時間。

遺傳算法的參數設置為：交叉概率Pc=0.85，變異概率Pmop=0.012，Pmch=0.2，種群規模popsize=40，運行次數maxrun=10，每次運行最大進化代數maxgen=100。最終得到的調度結果makespan=17。

觀察表1，令每道工序都選擇最小加工時間的機器，可得到工件J1、J2、J3和J4的完工時間分別為5、9、17和12，所以對于該問題，若不限制工件訪問同一臺機器的次數，且系統緩沖區無限，makespan=17已經是最優的調度結果。

在makespan=17的調度中，得到的最小的總完工時間為63。圖2中，字符串“ij＜a--b＞”表示工序Oij的開始加工時間是a，完工時間是b。調度的甘特圖見圖3，字符串“i-j”表示工序Oij。因任何工序都不可能提前操作而同時保證其他工序不延遲，因此該調度是活動調度。

5.結論

本文使用遺傳算法來求解柔性車間作業活動調度問題。首先將基于工序的編碼和基于機器的編碼方式結合，同時對交叉操作和變異操作的對象作了規定，這些改進方法可以保證遺傳操作每一步產生的染色體都是合法的，避免了傳統柔性車間作業調度中繁瑣的染色體合法化修復工作。為了得到活動調度的形式，在適應度計算的過程中對染色體的基因序列進行調整。用4工件6機器的柔性車間作業調度問題為例進行仿真，得到的調度結果為最優；在所有最小makespan值的調度中，進一步給出了機器總完工時間最小的調度。仿真結果表明，本文設計的遺傳算法在求解柔性車間作業調度問題時是有效的。

[1]Zribi N,Kamel AE,Borne P.Scheduling in a flexible job shop under machine availability constraints[J].APII-JESA Journal Europeen des Systemes Automatises,2007,41(6):651-671.

[2]Guohui Zhang,Liang Gao,Yang Shi.An effective genetic algorithm for the flexible job-shop scheduling problem[J].Expert Systems with Applicatio ns,2011,4(38):3563-3573.

[3]白俊杰,龔毅光,王寧生,唐敦兵.批量生產柔性作業車間作業優化調度研究[J].機械科學與技術,2010,3(29):293-298.

[4]Kacem I.Genetic algorithm for the flexible jobshop scheduling problem[C],IEEE International Conference on Systems,Man and Cybernetics,OCT 05-08,WASHINGTON D.C.2003,1-5:3464-3469.

[5]Kun Y,Zhu JY.Improved genetic algorithm for the flexible job-shop scheduling with multi-object[J].China Mechanical Engineering,2007,18(2):156-160.

[6]光熠,劉心報,程浩.求解車間作業調度問題的一種改進遺傳算法[J].計算機技術與發展,2007,11(17):171-174,178.

[7]陳亮,王世進,周炳海.柔性作業車間調度問題的集成啟發式算法[J].計算機工程,2008,34(1):256-258.

[8]席衛東,喬兵,朱劍英.基于改進遺傳算法的柔性作業車間調度[J].哈爾濱工業大學學報,2007,39(7):1151-1153.

[9]楊紅紅,吳智銘.混合遺傳算法在柔性系統動態調度中的應用研究[J].信息與控制,2001,30(5):392-397.

[10]方紅雨,崔遜學.基于遺傳算法的調度問題研究[J].電腦與信息技術,2001(2):1-5.

[11]Ferrolho A,Crisostomo M.A hybrid and flexible genetic algorithm for the job-shop scheduling problem[C].IEEE International Symposium on Computational Intelligence in Robotics and Automation.IEEE Piscataway.NJ.USA Jacksonville.FI.USA,2007:421-426.

[12]王凌.車間調度及其遺傳算法[M].北京:清華大學出版社,2003.