帶學(xué)習(xí)策略的遺傳算法求解柔性作業(yè)調(diào)度問題

王公堂，許化強(qiáng)

（山東師范大學(xué) 物理與電子科學(xué)學(xué)院，山東 濟(jì)南 250014）

傳統(tǒng)的作業(yè)調(diào)度問題中，作業(yè)的每一道工序都是預(yù)先知道的，而且工序的加工機(jī)器和時(shí)間也是預(yù)先確定好的。而在柔性作業(yè)調(diào)度問題中，工序的加工機(jī)器是不確定的。作業(yè)的每一道工序都可以在多個(gè)加工機(jī)器上加工，而且不同的加工機(jī)器所需要的加工時(shí)間也不相同。在處理此類問題上，不僅要處理作業(yè)之間的調(diào)度問題，而且要考慮每一道工序面臨可選擇機(jī)器的問題，使問題更難以解決。針對柔性車間調(diào)度問題的特點(diǎn)，筆者在Yasuhiro Tsujimura[1]等人提出的主從共生遺傳算法的基礎(chǔ)上進(jìn)行改進(jìn)，加入學(xué)習(xí)策略，在進(jìn)化過程中發(fā)掘并保留種群中的優(yōu)秀特征，并指導(dǎo)后代的進(jìn)化，加快收斂速度，提高搜索效率。

1 帶操作柔性的作業(yè)調(diào)度問題描述

具有操作柔性（OF）的柔性車間調(diào)度問題（Flexible Job-Shop Scheduling Problem，F(xiàn)JSP）是指同一個(gè)操作（或工序）可以在不同的機(jī)器上運(yùn)行。FJSP假定加工系統(tǒng)中有M臺機(jī)器和N個(gè)作業(yè)，每個(gè)作業(yè)包括一道或多道操作，操作順序是預(yù)先確定的，每道操作可以選擇在多臺不同的設(shè)備上加工，操作的加工時(shí)間隨加工設(shè)備的不同而變化。例如，表1是FJSP的一個(gè)例子，共有2個(gè)作業(yè)，3個(gè)加工機(jī)器，每道工序可以選擇在不同機(jī)器上以不同的加工時(shí)間加工。調(diào)度目標(biāo)是為每道工序選擇最合適的加工設(shè)備，以及每臺設(shè)備上各工序的最佳加工順序，使所有作業(yè)的流通時(shí)間最短。該問題所需滿足的約束條件[2]是:1）所有作業(yè)在初始時(shí)刻都可加工；2）工序在可供選擇的若干機(jī)器上加工的時(shí)間已確定；3）每臺加工機(jī)器在固定的時(shí)間段內(nèi)只能加工一個(gè)作業(yè)；4）每個(gè)作業(yè)在固定時(shí)刻只能在一臺機(jī)器上加工。

表1 一個(gè)FJSP的實(shí)例 2×3Tab.1 An example of the FJSP 2×3

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

柔性車間調(diào)度可分成兩個(gè)子問題，一是為操作選擇加工機(jī)器，二是類似經(jīng)典車間調(diào)度問題，給作業(yè)一個(gè)合適的排序，得到最優(yōu)調(diào)度?？蓪⑦@兩個(gè)子問題看作是共生機(jī)制中的兩個(gè)不同的物種，進(jìn)而用不同的種群來表示，一個(gè)種群為控制種群，為工序選定合適的加工機(jī)器；另一個(gè)種群為調(diào)度種群，在控制種群的限制下優(yōu)化調(diào)度。

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

將柔性車間調(diào)度問題分為兩個(gè)子問題，對應(yīng)兩個(gè)不同類的種群，其個(gè)體分別稱為控制染色體和調(diào)度染色體，每個(gè)種群的個(gè)體都應(yīng)該有自己的編碼方式[3]。

控制染色體編碼方法：將所有的操作按照其所屬的作業(yè)號和其在作業(yè)中的加工順序依次排列，并將其選擇的加工機(jī)器放在工序?qū)?yīng)的位置上。即是控制染色體采用基于作業(yè)的編碼方式，將每個(gè)作業(yè)的所有工序選擇的加工機(jī)器的順序排列作為控制染色體的一個(gè)基因塊。例如，對表1中所示例子，可以有控制染色體12321，其中基因塊123為作業(yè)1（J1）的各個(gè)操作選擇的加工機(jī)器：操作 O1，1選擇的加工機(jī)器為 M1，O1，2選擇的加工機(jī)器為M2，O1，3選擇的加工機(jī)器為M3；基因塊21為作業(yè)2（J2）的操作所選擇的加工機(jī)器排序序列。

調(diào)度染色體編碼方法：調(diào)度染色體采用基于操作的編碼方式，并把操作按照加工機(jī)器的不同分為不同的基因塊。因此，如果有m臺加工設(shè)備，則調(diào)度染色體有m個(gè)基因塊。如果某個(gè)設(shè)備基因塊中包含同一個(gè)作業(yè)的多個(gè)操作，則這個(gè)基因塊中的所有操作排序時(shí)，必須注意同一個(gè)作業(yè)的多個(gè)操作之間的先后約束關(guān)系，即先加工的操作必須排列在后加工的操作的前面。 例如作業(yè) 1 有 3 個(gè)操作 O1，1，O1，2，O1，3；作業(yè) 2 有2 個(gè)操作 O2，1，O2，2。 假設(shè)這 5 個(gè)操作選 取 的加工 機(jī)器分別為M1，M2，M3，M2，M1。 則在機(jī)器 M1上加工的操作一個(gè)可能的排列為O1，1O2，2，這個(gè)字符串為調(diào)度染色體編碼的一個(gè)基因塊；同理，在機(jī)器M2上加工的操作可能的排列為O1，2O2，1；在M3上加工的操作可能的排列為O1，3。按照機(jī)器序號，將這些基因塊組合到一塊，則組成了調(diào)度染色體 O1，1O2，2O1，2O2，1O1，3。 這種編碼方式的一個(gè)優(yōu)點(diǎn)就是可以將對染色體的操作提高到基因塊的級別上。

2.2 進(jìn)化過程中的學(xué)習(xí)

進(jìn)化過程是基于隨機(jī)自然選擇和基因重組。如果不考慮保留種群中優(yōu)秀的特性而進(jìn)行種群進(jìn)化，則可能需要很長的時(shí)間才能找到全局最優(yōu)解。針對控制種群和調(diào)度種群，分別設(shè)立學(xué)習(xí)機(jī)制，用于學(xué)習(xí)、記錄以及指導(dǎo)后代種群的進(jìn)化，提高搜索質(zhì)量和效率。設(shè)立兩個(gè)信息存儲(chǔ)空間，即染色體空間和操作空間[4]。

染色體空間：具有最大適應(yīng)度值的不同染色體之間具有很多相似的特征[5]，如果當(dāng)某個(gè)調(diào)度染色體中出現(xiàn)了最優(yōu)解的一些排序特征，就應(yīng)該及時(shí)把它保存下來，希望多個(gè)調(diào)度中的不同的最優(yōu)特征經(jīng)過交叉之后能夠在進(jìn)化機(jī)制的幫助下逐漸集中，就可以使算法很快向最優(yōu)解收斂。染色體空間中存儲(chǔ)的是前幾代中挑選出來的最好的染色體。進(jìn)化到當(dāng)前代時(shí)從當(dāng)前種群中選擇一定數(shù)量的適應(yīng)度最高的染色體，每一個(gè)選出的染色體要與染色體空間中的染色體做比較。染色體空間中k個(gè)具有最高相似度的染色體將被復(fù)制到當(dāng)前代種群中。采用基于染色體中操作的差異來定義兩個(gè)染色體的相似度。相似度可以用下面的公式計(jì)算：

其中M表示調(diào)度染色體中設(shè)備基因塊的個(gè)數(shù)，Qi表示設(shè)備基因塊i中操作的個(gè)數(shù)。Chm1和Chm2表示調(diào)度染色體，Opt1、Opt2 表示 Chm1、Chm2 中的操作，Opt1（i，j）表示染色體Chm1 中設(shè)備基因塊 i中第 j個(gè)操作。 如果 Opt1（i，j）、Opt2（i，j）表示的兩個(gè)操作相同則操作符返回0，否則返回1。S越小，則表示兩個(gè)染色體Chm1、Chm2越相近。染色體空間主要用來保存以前代中的優(yōu)秀染色體，用來提高后代交叉的效果。

操作空間：在進(jìn)化過程中為作業(yè)的工序選擇最合適的加工機(jī)器。如圖1所示，其全部信息是要加工的作業(yè)以及作業(yè)的全部操作和操作對應(yīng)的可選加工機(jī)器集合，作業(yè)對應(yīng)的加工機(jī)器各自都有一個(gè)參考數(shù)據(jù)，該數(shù)據(jù)表示在以往的優(yōu)秀染色體中，該加工機(jī)器被選中加工此操作的情況，重新選擇加工機(jī)器時(shí)可以根據(jù)這個(gè)信息選擇最可能合適的機(jī)器。該空間數(shù)據(jù)在進(jìn)化過程中每隔n代更新一次。圖1中展示的共有N個(gè)作業(yè)，其中作業(yè)3有x個(gè)操作，操作O3，3有3個(gè)機(jī)器可以選擇M1M2M3，其中機(jī)器M1以往較優(yōu)染色體中選中率為30%，M2以往選中率為20%，M3被以往被選中的概率為50%。當(dāng)對控制染色體執(zhí)行變異操作時(shí)，如果為某個(gè)操作重新選擇加工機(jī)器，可以在此空間數(shù)據(jù)的指導(dǎo)下選擇最可能合適的加工機(jī)器。

圖1 操作空間示例Fig.1 Example of operational memory

2.3 算法設(shè)計(jì)

對FJSP問題來說，因?yàn)椴煌淖訂栴}有其本身的特征，因而在進(jìn)化過程中，應(yīng)該考慮到不同的種群的地位和進(jìn)化速度也應(yīng)該不同，適當(dāng)搭配不同物種之間的進(jìn)化速度會(huì)獲得比較好的結(jié)果。因?yàn)檎{(diào)度種群是在控制種群的指導(dǎo)下進(jìn)化的，調(diào)度種群的進(jìn)化結(jié)果影響控制種群中染色體的適應(yīng)度，因而，在進(jìn)化速度方面，調(diào)度種群應(yīng)該比控制種群要快得多。筆者將控制種群作為進(jìn)化主過程，調(diào)度種群作為從過程，改進(jìn)后的共生遺傳算法如下：

1）主進(jìn)化過程：控制染色體的適應(yīng)度取其控制下的調(diào)度種群進(jìn)化后最優(yōu)調(diào)度染色體的適應(yīng)度。

Step 1：生成初始種群，大小為pop_size；

Step 2：種群中的每一個(gè)控制染色體都對應(yīng)一個(gè)調(diào)度種群，使用2）從進(jìn)化過程對調(diào)度種群進(jìn)化，依次得到每個(gè)控制染色體的適應(yīng)度fc。

Step 3：統(tǒng)計(jì)控制染色體的最大適應(yīng)度fcmax和平均適應(yīng)度fcavg。

Step 4：如果連續(xù)m代最大適應(yīng)度沒有變化或者達(dá)到最大進(jìn)化代數(shù)，則算法結(jié)束。否則繼續(xù)執(zhí)行Step 5。

Step 5：選擇：對控制染色體種群執(zhí)行輪盤賭選擇操作[6]。

Step 6：交叉，變異：根據(jù)操作空間的信息指導(dǎo)變異操作：

Step 7：更新：選出一定數(shù)目的最優(yōu)控制染色體，對操作空間進(jìn)行更新。轉(zhuǎn)到Step 2）繼續(xù)。

2）從進(jìn)化過程：調(diào)度染色體的進(jìn)化。

Step 1：初始化調(diào)度種群。根據(jù)控制染色體為操作選定的加工機(jī)器，生成初始種群。

Step 2：計(jì)算調(diào)度種群中每個(gè)染色體p的最早完工時(shí)間MS，同時(shí)計(jì)算適應(yīng)度值=1/MS。

Step 5：對調(diào)度染色體種群進(jìn)行選擇操作。選擇出來的部分染色體還要和染色體空間中的染色體做比較，并將染色體空間中最相似的k個(gè)染色體插入到當(dāng)前種群中。

Step 6：交叉變異操作。

在紅磷及其三鹵化物或氯化亞砜的催化下，脂肪酸的a-H可被氯、溴取代生成a-鹵代酸，此反應(yīng)被稱為Hell-Volhard-Zelin-Sky反應(yīng)，反應(yīng)機(jī)理如下：

Step 7：更新：每隔k代更新染色體空間。轉(zhuǎn)Step 1繼續(xù)。

3 遺傳算子設(shè)計(jì)

3.1 交叉算子

對控制染色體的交叉操作采用染色體中多點(diǎn)交換操作。隨機(jī)決定發(fā)生交換的染色體中基因的個(gè)數(shù)和位置，并將兩個(gè)父個(gè)體中對應(yīng)位置的基因交換，生成新的個(gè)體。對調(diào)度染色體的交叉操作采用基于設(shè)備基因塊交叉法。兩個(gè)調(diào)度染色體可能會(huì)發(fā)生與設(shè)備基因塊數(shù)目M相同多的多點(diǎn)交叉。

3.2 變異算子與學(xué)習(xí)引導(dǎo)

控制染色體變異主要針對某個(gè)作業(yè)的全部操作。因此，首先應(yīng)該選中需要變異的作業(yè)。如果選中某個(gè)作業(yè)變異，則這個(gè)作業(yè)的所有操作都要重新選擇加工機(jī)器。這樣控制染色體會(huì)發(fā)生與作業(yè)數(shù)目N相同的多點(diǎn)變異。有兩種選擇方式，一種是在可選機(jī)器集合中隨機(jī)選擇，一種是在操作空間的指導(dǎo)下選擇，方法如下：

Step 0：對作業(yè)Ji中每個(gè)操作Oi，j重新選擇加工機(jī)器：

找出Mk機(jī)器：Mk機(jī)器目前用來加工Oi，j。找出可以加工操作 Oi，j的機(jī)器集合 P（Oi，j）。

Step 1：產(chǎn)生一個(gè)隨機(jī)數(shù)字 r∈[0，1]：

如果 r＜=0.5，則使用隨機(jī)變異操作：從 P（Oi，j）中隨機(jī)選擇一個(gè)機(jī)器加工操作Oi，j。否則，操作空間中的機(jī)器選擇信息對變異算子施加影響：如果 P（Oi，j）僅包含 Mk，則仍然使用 Mk來加工Oi，j，否則，根據(jù)操作空間中機(jī)器被選擇情況的概率，以輪盤賭方式從 P（Oi，j）中選擇一個(gè)機(jī)器來加工操作 Oi，j。

Step 2：轉(zhuǎn)到 step 0。

調(diào)度染色體的變異操作，主要是對不合理基因塊執(zhí)行變異，對操作排序做一些改動(dòng)。因此首先選中執(zhí)行變異操作的設(shè)備基因塊，然后對基因塊執(zhí)行兩點(diǎn)易位法。這樣，調(diào)度染色體會(huì)發(fā)生與設(shè)備基因塊數(shù)M（設(shè)備數(shù)目）相同的多點(diǎn)變異。

4 實(shí)驗(yàn)仿真及分析

這里采用文獻(xiàn)[7]中的不同規(guī)模的柔性車間調(diào)度問題的數(shù)據(jù)作為測試數(shù)據(jù)。為了更加準(zhǔn)確，對于要測試的每一種規(guī)模的問題數(shù)據(jù)，分別運(yùn)行10次，然后取這10次運(yùn)行結(jié)果的最好值以及平均值。表2給出了實(shí)驗(yàn)結(jié)果，共有6列。第一列給出了問題規(guī)模，第二列是文獻(xiàn)[7]中的方法獲取的最優(yōu)調(diào)度結(jié)果，右邊4列是通過使用本文給出的方法仿真得出的數(shù)據(jù)，分別是只用共生遺傳算法得出的最好值和平均值，加入學(xué)習(xí)策略后得到的最好值和平均值。

表2 仿真實(shí)驗(yàn)結(jié)果Tab.2 Simulation experimental results

由表2可以看出，使用本文提出的方法在其中3種規(guī)模的柔性車間調(diào)度問題中可以取得較好的效果，有明顯改進(jìn)，每次運(yùn)行中都能取得比原來好的調(diào)度值。但在10×10規(guī)模的問題上，結(jié)果不如原來優(yōu)秀。第3列中是同等條件下僅使用基于共生機(jī)制的遺傳算法獲取的結(jié)果。總體來看，加入學(xué)習(xí)策略之后能獲取質(zhì)量更高的結(jié)果。

5 結(jié) 論

根據(jù)柔性作業(yè)調(diào)度問題的特點(diǎn)，將該問題分為兩個(gè)子問題，看作是共生遺傳算法中兩個(gè)相互影響，共同進(jìn)化的不同類種群。根據(jù)子問題的特點(diǎn)，設(shè)定兩個(gè)不同類種群有不同的進(jìn)化角色和進(jìn)化速度。在進(jìn)化過程中，加入學(xué)習(xí)策略，使遺傳算法能夠在進(jìn)化過程中不斷學(xué)習(xí)，將染色體中的優(yōu)秀特征保留下來指導(dǎo)后代的進(jìn)化。實(shí)驗(yàn)證明，加入學(xué)習(xí)策略后對提高解的質(zhì)量有一定的效果。

[1]Tsujimura Y， Mafune Y， Gen M.Effects of symbiotic evolution in genetic algorithms for job-shop scheduling[C]//Proceeding of the 34th Hawaii International Conference on System Sciences.[S.1.]:the IEEE Computer Society，2001:3026－3032.

[2]楊曉梅，曾建潮.遺傳算法求解柔性job shop調(diào)度問題[J].控制與決策，2004，19（10）：1197－1200.

YANG Xiao-mei，ZENG Jian-chao.Solving flexible job shop scheduling problem using genetic algorithm[J].Control and Decision，2004，19（10）:1197－1200.

[3]張維存，鄭丕諤，吳曉丹.基于主－從遺傳算法求解柔性調(diào)度問題[J].計(jì)算機(jī)集成制造系統(tǒng)，2006，12（8）:1241－1245.

ZHANG Wei-cun，ZHENG Pi-e，WU Xiao-dan.Solving flexible job-shop scheduling problems based on master-slave genetic algorithm[J].ComputerIntegrated Manufacturing Systems，2006，12（8）:1241－1245.

[4]Ho N B，Tay J C.LEGA:an architecture for learning and evolving flexible job-shop schedules[C]//The 2005 IEEE Congress on Evolutionary Computation，2005，2（2－5）:1380－1387.

[5]許化強(qiáng)，邱洪澤.用屬性導(dǎo)向歸納法發(fā)掘job-shop調(diào)度中的排序規(guī)則[C]//第三屆智能CAD與數(shù)字娛樂學(xué)術(shù)會(huì)議，濟(jì)南:山東大學(xué)出版社，2006:231－237.

[6]王小平.遺傳算法—理論、應(yīng)用及軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社，2002.

[7]Kacern I， Hammadi S， Borne P.Pareto-optimality approach for flexible job-shop scheduling problems:Hybridization of evolutionary algorithms and fuzzy logic[J].Mathematics and Computers in Simulation， 2002，60（3－5）:245－276.