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

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

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

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

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

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

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

模型的約束條件有兩類：

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

（2）資源約束，即在一個(gè)確定的時(shí)刻，同一臺(tái)機(jī)床只能加工一個(gè)工件的一道工序，在該工序完工后才能開(kāi)始加工下一個(gè)（見(jiàn)式（3）），并且同一道工序只能在一臺(tái)機(jī)床上加工（見(jiàn)式（4））。

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

2 遺傳算法設(shè)計(jì)

2.1 編碼設(shè)計(jì)

用遺傳算法求解作業(yè)車間調(diào)度問(wèn)題可以采用基于工序順序的編碼方法［3］，但這種方法要求工件每道工序的加工機(jī)器是固定的，而在路徑柔性作業(yè)車間調(diào)度中，機(jī)器是可以選擇的，因此本文設(shè)計(jì)了一種基于工序和機(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ī)選擇一個(gè)加工序列（即染色體）（1，2，5，4，1，1，2，3，2，4，3，5，4，3，5），染色體中的1～5為工件號(hào)，每個(gè)序號(hào)在染色體中出現(xiàn)的次數(shù)與其加工工序數(shù)相等，第一次出現(xiàn)某個(gè)序號(hào)，表示該序號(hào)對(duì)應(yīng)工件的第一道加工工序，第二次出現(xiàn)則對(duì)應(yīng)該工件的第二道工序，以此類推，一個(gè)可行的工序序列可以通過(guò)這樣一個(gè)數(shù)字串來(lái)表示。

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

例如，對(duì)于一個(gè)染色體：

矩陣的第一列表示工件1的第一道工序在其可選用的第一臺(tái)機(jī)床上加工，根據(jù)表1可知該機(jī)床為M1；矩陣的第三列表示工件5的第一道工序只能在惟一的一臺(tái)機(jī)床上加工，根據(jù)表1可知該機(jī)床為M3；矩陣的第五列表示工件1的第二道工序在其可選用的第二臺(tái)機(jī)床上加工，根據(jù)表1可知該機(jī)床為M4。通過(guò)類似的解碼，得到一個(gè)可行的調(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)度高的個(gè)體更容易生存下來(lái)。適應(yīng)度函數(shù)一般由目標(biāo)函數(shù)轉(zhuǎn)換而來(lái)，本文的優(yōu)化目標(biāo)是最長(zhǎng)加工時(shí)間最短化，可將目標(biāo)函數(shù)值C的倒數(shù)作為個(gè)體的適應(yīng)度f(wàn)。

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

式中：M為種群大小。

2.3 交叉和變異算子

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

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

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

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

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

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

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

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

3 算例分析

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

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

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

圖2 收斂曲線Fig.2 Convergence curves

4 結(jié)語(yǔ)

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

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

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

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

［4］ 王小平，曹立明.遺傳算法——理論應(yīng)用與軟件實(shí)現(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.