謝 皓，應(yīng)保勝，袁 波

（武漢科技大學(xué)機(jī)械自動化學(xué)院，湖北武漢，430081）

傳統(tǒng)的作業(yè)車間調(diào)度問題中，工件的加工工序是確定的，某道工序的加工機(jī)器及加工時間也是確定的，而路徑柔性作業(yè)車間調(diào)度則存在加工工藝路線中機(jī)器可變的情況，即工件的同一工序可以選擇不同的機(jī)器進(jìn)行加工，并且在不同機(jī)器上的加工時間也可能不同［1］。因此，路徑柔性作業(yè)車間調(diào)度優(yōu)化問題更為復(fù)雜。

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

1 調(diào)度模型的建立

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

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

模型的約束條件有兩類：

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

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

以最長完工時間最短化為調(diào)度優(yōu)化目標(biāo)，其目標(biāo)函數(shù)為：

2 遺傳算法設(shè)計

2.1 編碼設(shè)計

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

表1 路徑柔性作業(yè)車間調(diào)度原始數(shù)據(jù)Table 1 Data of the path flexible job－shop scheduling

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

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

例如，對于一個染色體：

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

2.2 選擇算子

選擇操作是為了避免有效基因的損失，因此適應(yīng)度高的個體更容易生存下來。適應(yīng)度函數(shù)一般由目標(biāo)函數(shù)轉(zhuǎn)換而來，本文的優(yōu)化目標(biāo)是最長加工時間最短化，可將目標(biāo)函數(shù)值C的倒數(shù)作為個體的適應(yīng)度f。

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

式中：M為種群大小。

2.3 交叉和變異算子

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

從而使某些工序的加工機(jī)器發(fā)生了變化。

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

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

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

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

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

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

3 算例分析

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

圖1 最優(yōu)調(diào)度方案Fig.1 Optimal scheduling solution

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

圖2 收斂曲線Fig.2 Convergence curves

4 結(jié)語

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

［1］ 張國輝，高亮，李培根.改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問題［J］.機(jī)械工程學(xué)報，2009，45（7）：145－148.

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

［3］ 谷峰，陳華平.病毒遺傳算法在柔性工作車間調(diào)度中的應(yīng)用［J］.系統(tǒng)工程與電子技術(shù)，2006，27（11）：139－142.

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

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