王公堂，許化強

（山東師范大學 物理與電子科學學院，山東 濟南 250014）

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

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

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

表1 一個FJSP的實例 2×3Tab.1 An example of the FJSP 2×3

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

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

2.1 編碼設(shè)計

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

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

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

2.2 進化過程中的學習

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

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

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

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

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

2.3 算法設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

Step 6：交叉變異操作。

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

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

3 遺傳算子設(shè)計

3.1 交叉算子

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

3.2 變異算子與學習引導(dǎo)

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

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

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

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

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

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

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

4 實驗仿真及分析

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

表2 仿真實驗結(jié)果Tab.2 Simulation experimental results

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

5 結(jié) 論

根據(jù)柔性作業(yè)調(diào)度問題的特點，將該問題分為兩個子問題，看作是共生遺傳算法中兩個相互影響，共同進化的不同類種群。根據(jù)子問題的特點，設(shè)定兩個不同類種群有不同的進化角色和進化速度。在進化過程中，加入學習策略，使遺傳算法能夠在進化過程中不斷學習，將染色體中的優(yōu)秀特征保留下來指導(dǎo)后代的進化。實驗證明，加入學習策略后對提高解的質(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].計算機集成制造系統(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]許化強，邱洪澤.用屬性導(dǎo)向歸納法發(fā)掘job-shop調(diào)度中的排序規(guī)則[C]//第三屆智能CAD與數(shù)字娛樂學術(shù)會議，濟南:山東大學出版社，2006:231－237.

[6]王小平.遺傳算法—理論、應(yīng)用及軟件實現(xiàn)[M].西安:西安交通大學出版社，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.