基于遺傳算法的作業(yè)車間調(diào)度優(yōu)化求解方法

收稿日期：2007-11-23；修回日期：2008-03-06

作者簡(jiǎn)介：周輝仁（1972-），男，山東高密人，博士，博士后在站，主要研究方向?yàn)楣I(yè)工程、智能優(yōu)化理論與方法(huirenzhou@126.com); 鄭丕諤（1942-），男，福建莆田人，教授，博導(dǎo)，主要研究方向?yàn)橄到y(tǒng)工程理論及應(yīng)用；宗蘊(yùn)(1969-)，男，山東濟(jì)南人，碩士，主要研究方向?yàn)楣I(yè)工程；張揚(yáng)（1975-），男，山東濟(jì)南人，碩士，主要研究方向?yàn)楣I(yè)工程

（1天津大學(xué) 系統(tǒng)工程研究所，天津 300072；2山東大學(xué) 能源與動(dòng)力學(xué)院，濟(jì)南 250100）

摘 要：針對(duì)job shop調(diào)度問(wèn)題，提出了一種遺傳算法編碼方法和解碼方法。該方法根據(jù)問(wèn)題的特點(diǎn)，采用一種按工序用不同編號(hào)進(jìn)行的染色體編碼方案，并采用矩陣解碼方法。此編碼與調(diào)度方案一一對(duì)應(yīng)，并且該編碼方案有多種交叉操作算子可用，無(wú)須專門設(shè)計(jì)算子。算例計(jì)算結(jié)果表明，該算法是有效的，適用于解決job shop調(diào)度問(wèn)題，通過(guò)比較，該遺傳算法優(yōu)化job shop調(diào)度操作簡(jiǎn)單并且收斂速度快。

關(guān)鍵詞：作業(yè)車間調(diào)度；遺傳算法；編碼方法；矩陣解碼；優(yōu)化

中圖分類號(hào)：TP301.6; TP18

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)10-2991-04

Method for GA-based solution to job shop scheduling optimization

ZHOU Hui-ren¹，ZHENG Pi-e¹，ZONG Yun²，ZHANG Yang²

(1. Institute of Systems Engineering， Tianjin University， Tianjin 300072，China; 2. School of Energy Power Engineering， Shandong University， Jinan 250100， China)

Abstract:This paper proposed a new encoding method and decoding method with the matrix form for a solution to genetic algorithm-based job shop scheduling problem. Based on a specific problem， designed a job activities’ number-dependent coding of chromosomes and adopted the matrix decoding. As a result， codes by the new encoding method accord with the job scheduling schemed one-to-one were able to match multiple cross operators without a special design of operators. Result from a case study show that the genetic algorithm with the help of new encoding method presented a powerful ability and was able to effectively solve job shop scheduling problems. To show merits of the new encoding and decoding method， a comparison of different sized job shop scheduling problems in terms of job activity duration， sequence， and scheduling schemes， showed that with the help of the proposed method the genetic algorithm is encouraging， with solutions found through simple operations and fast convergence.

Key words：job shop scheduling; genetic algorithm(GA); encoding method; decoding with the matrix form; optimization

Job shop調(diào)度問(wèn)題(JSP)是一類典型的生產(chǎn)調(diào)度問(wèn)題，是許多實(shí)際生產(chǎn)調(diào)度問(wèn)題的簡(jiǎn)化模型，具有很強(qiáng)的工程背景，許多實(shí)際工程問(wèn)題均可與之相轉(zhuǎn)換。Job shop調(diào)度問(wèn)題是非常難解的NP問(wèn)題[1]，因此開(kāi)發(fā)求解job shop調(diào)度問(wèn)題的有效算法一直是調(diào)度和優(yōu)化領(lǐng)域的重要課題。目前，研究job shop調(diào)度問(wèn)題的方法包括傳統(tǒng)運(yùn)籌學(xué)方法、啟發(fā)式算法、神經(jīng)網(wǎng)絡(luò)、模糊理論、Lagrangian松弛法、禁忌搜索、模擬退火、遺傳算法和混合算法等[2~6]。針對(duì)job shop調(diào)度問(wèn)題用遺傳算法求解已有不少研究[7~9]，其編碼方案采用比較多的是一種基于工序的表達(dá)方法，即將調(diào)度編碼為工序的序列，給所有同一工件的工序指定相同的符號(hào)，然后根據(jù)它們?cè)诮o定染色體中出現(xiàn)的順序加以解釋。為了有效地解決job shop調(diào)度問(wèn)題，本文提出了一種按工序用不同編號(hào)進(jìn)行的染色體編碼方法，每一個(gè)編號(hào)表示一個(gè)工件的工序，將這些互不相等的編號(hào)編碼成染色體進(jìn)行進(jìn)化計(jì)算，并提出矩陣的解碼方法，即找到一個(gè)最優(yōu)調(diào)度，使完工時(shí)間最小。

1 問(wèn)題描述

典型的job shop調(diào)度問(wèn)題可描述為n個(gè)工件在m臺(tái)機(jī)器上加工，事先規(guī)定各工件在各臺(tái)設(shè)備上的加工順序，各工件在各設(shè)備上的操作時(shí)間已知，要求確定各設(shè)備上所有工件的加工次序，使某些加工性能指標(biāo)最優(yōu)。已知：a)工件pi（i=1，2，…，n）；b)機(jī)器mj（i=1，2，…，m）；c)工序opi，j（i=1，2，…，n；j=1，2，…，m）表示第i個(gè)工件的第j道工序使用的機(jī)器號(hào)，opi，j=0表示工件pi在第j道工序不加工；d)時(shí)間ti，j為第i個(gè)工件pi使用第j臺(tái)機(jī)器的時(shí)間，ti，j=0表示工件pi不使用機(jī)器j。Job shop調(diào)度滿足下列約束條件：a)每個(gè)工序利用每臺(tái)機(jī)器不多于一次；b)每個(gè)工件利用每臺(tái)機(jī)器的順序可以不同；c)每個(gè)工件的工序必須依次加工，后工序不能先于前工序；d)任何工件沒(méi)有搶先加工的優(yōu)先權(quán)，應(yīng)服從生產(chǎn)順序；e)工件加工過(guò)程中沒(méi)有新工件加入，也不臨時(shí)取消工件的加工。

調(diào)度目標(biāo)通常是最小化最大完成時(shí)間，即T=min{max(Ci)}。其中：Ci為工件i的完工時(shí)間;i=1，2，…，n。

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

將遺傳算法應(yīng)用于job shop 調(diào)度問(wèn)題中的關(guān)鍵是采用有效的編碼和解碼方式以及適當(dāng)?shù)慕徊妗⒆儺惒僮鳌＿z傳算法對(duì)種群重復(fù)地進(jìn)行選擇、交叉、變異等基本遺傳操作，不斷產(chǎn)生出比父代更適應(yīng)環(huán)境的新一代種群，直到滿足要求條件為止。

21 個(gè)體編碼

用遺傳算法求解job shop 調(diào)度問(wèn)題時(shí)，實(shí)際上是將job shop調(diào)度問(wèn)題用遺傳算法編碼加以表示并對(duì)各工序的優(yōu)化排序進(jìn)行研究，編碼問(wèn)題是設(shè)計(jì)遺傳算法的首要和關(guān)鍵問(wèn)題。Job shop 調(diào)度的遺傳算法編碼可歸納為兩種[1]：a)直接編碼。將各調(diào)度作為狀態(tài)，通過(guò)狀態(tài)演化達(dá)到尋優(yōu)目的，主要包括基于操作(工序)的編碼、基于工件的編碼、基于工件對(duì)關(guān)系的編碼、基于完成時(shí)間的編碼、隨機(jī)鍵編碼等。b)間接編碼。將一組工件的分配處理規(guī)則作為狀態(tài)，算法優(yōu)化的結(jié)果是一組最佳的分配規(guī)則序列，再由分配規(guī)則的序列構(gòu)造調(diào)度，主要包括基于優(yōu)先權(quán)規(guī)則的編碼、基于先后表的編碼、基于析圖的編碼和基于機(jī)器的編碼等。這些編碼方法各有特點(diǎn)，有些表征解空間可能存在非法解，有些不能保證全局最優(yōu)解的存在，有些難以用遺傳算法操作實(shí)行進(jìn)化。

在用遺傳算法求解job shop調(diào)度問(wèn)題時(shí)，應(yīng)用比較多的編碼方法是基于操作(工序)的編碼。例如文獻(xiàn)[7~9]采用基于工序的編碼方式，個(gè)體由所有工序的排序組成，每個(gè)基因代表一個(gè)工序，同一工件的所有工序采用同一工件序號(hào)表示，然后根據(jù)它們?cè)趥€(gè)體排序中的順序決定它們?cè)诓煌瑱C(jī)器上的加工順序。用這種編碼方式進(jìn)行遺傳算法設(shè)計(jì)對(duì)于解決job shop調(diào)度問(wèn)題是有效的，但為保證后代的可行性，遺傳操作需特別設(shè)計(jì)。

針對(duì)job shop調(diào)度問(wèn)題的特點(diǎn)，本文提出一種改進(jìn)的編碼方案，對(duì)所有工件的工序用自1開(kāi)始的連續(xù)互不相等的整數(shù)進(jìn)行編號(hào)，每一個(gè)編號(hào)代表工件的工序，將這些編號(hào)編碼成染色體。在同一機(jī)器上加工的工序，其編號(hào)在同一條染色體中的先后順序?yàn)樵谠摍C(jī)器上加工的先后順序；為了避免同一工件的不同工序在操作運(yùn)算中產(chǎn)生死鎖現(xiàn)象，對(duì)染色體中的基因在初始種群和操作運(yùn)算后，對(duì)同一工件的不同工序?qū)?yīng)的編號(hào)采用按整數(shù)從小到大重排序進(jìn)行修正其在染色體中的位置，這樣保證了自遺傳算法產(chǎn)生的初始種群至交叉、變異后的新種群都為合法解。采用此種編碼方案，有效地處理了job shop調(diào)度問(wèn)題的約束條件。對(duì)于3×3 job shop 調(diào)度問(wèn)題的編碼信息和方案如表1、2所示。

將以上3×3 job shop 調(diào)度問(wèn)題根據(jù)加工順序進(jìn)行編號(hào)如表3所示。

表1 加工時(shí)間JM1M2M3J1332J2153J3323表2 加工順序JM1M2M3J1123J2132J3213表3 工序編號(hào)JM1M2M3J1(1)(2)(3)J2(4)(6)(5)J3(8)(7)(9)

按編號(hào)生成染色體編碼，如

124357689

為了避免在操作運(yùn)算后出現(xiàn)非法編碼，采用局部排序(sort 函數(shù))修正的方法來(lái)重排序，若所得的一條染色體為

214637589

編號(hào)1、2、3分別代表的是工件1的第1、2、3道工序，從以上染色體看到對(duì)于工件1，先加工第2道工序，再加工第1道工序，最后加工第3道工序，這與工藝約束是不允許的，可對(duì)[2 1 3]基因按從小到大重新排序?yàn)閇1 2 3]；同理，對(duì)于工件2的工序[4 6 5]重新排序?yàn)閇4 5 6]。通過(guò)重排序處理后所得如下染色體：

124537689即為合法的染色體，從而避免了非法染色體的出現(xiàn)。

22 群體規(guī)模選擇

合適的群體規(guī)模對(duì)遺傳算法的收斂具有重要意義。群體太小難以求得滿意的結(jié)果，群體太大則計(jì)算復(fù)雜。根據(jù)經(jīng)驗(yàn)，群體規(guī)模一般取10～160。

23 適值函數(shù)

遺傳算法在進(jìn)行選擇操作時(shí)會(huì)出現(xiàn)欺騙問(wèn)題[9]：在遺傳進(jìn)化初期，通常會(huì)產(chǎn)生一些超常個(gè)體，若按照比例選擇法，這些異常個(gè)體因競(jìng)爭(zhēng)力太突出而控制了選擇過(guò)程，影響算法的全局優(yōu)化性能；在遺傳進(jìn)化后期，即算法接近收斂時(shí)，由于種群中個(gè)體適應(yīng)度差異較小時(shí)，繼續(xù)優(yōu)化的潛能降低，可能獲得某個(gè)局部最優(yōu)解。適值函數(shù)設(shè)計(jì)不當(dāng)有可能造成這種問(wèn)題的出現(xiàn)。由于優(yōu)化目標(biāo)為最小化最大完成時(shí)間，令目標(biāo)函數(shù)作指數(shù)變換得到適值函數(shù)：f=α exp(-β×max(Ci))(1)其中：α、β為正實(shí)數(shù)。

24 選擇

選擇是用來(lái)確定重組或交叉?zhèn)€體，以及備選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體。選擇的第一步是計(jì)算適值，采用按比例的適應(yīng)度分配，是利用比例于各個(gè)個(gè)體適應(yīng)度的概率決定其子孫的遺留可能性。若有M個(gè)個(gè)體，其中某個(gè)個(gè)體i，其適值為fi，則其被選擇的概率表示為Pi=fi/∑Mk=1fk(2)然后對(duì)各個(gè)染色體計(jì)算其累積概率，如第k個(gè)個(gè)體的累積概率為：qk=∑ki=1pi(3)

第二步用輪盤賭選擇法進(jìn)行選擇。為了選擇交配個(gè)體，需要進(jìn)行多輪選擇，每一輪產(chǎn)生一個(gè)[0，1]均勻隨機(jī)數(shù)，將該隨機(jī)數(shù)作為選擇指針來(lái)確定備選個(gè)體。

25 交叉與變異

交叉在遺傳操作中起核心作用，交叉概率較大可增強(qiáng)遺傳算法開(kāi)辟新搜索空間的能力，但性能好的基因串遭到破壞的可能性較大，算法收斂速度降低且不穩(wěn)定；若交叉概率較小，則遺傳算法搜索可能陷入遲鈍狀態(tài)。對(duì)于基因串交叉可以采用基于路徑表示部分匹配(PMX)交叉操作、順序交叉(ordered crossover，OX)、循環(huán)交叉(cycle crossover，CX)等[10，11]。

部分匹配交叉是Goldberg等人于1985年針對(duì)TSP提出的基于路徑表示的交叉操作，部分匹配交叉操作要求隨機(jī)選取兩個(gè)交叉點(diǎn)，以便確定一個(gè)匹配段，根據(jù)兩個(gè)父?jìng)€(gè)體中兩個(gè)交叉點(diǎn)之間的中間段給出的影射關(guān)系生成兩個(gè)子個(gè)體。

順序交叉是Davis等人于1985年針對(duì)TSP提出的基于路徑表示的交叉操作，該操作能保留排列并融合不同排列的有序結(jié)構(gòu)單元。兩個(gè)父體交叉時(shí)，通過(guò)選擇父?jìng)€(gè)體1的一部分，保存父體2中代碼的相對(duì)順序生成子個(gè)體。

循環(huán)交叉是Oliver等人針對(duì)TSP提出的交叉操作，循環(huán)交叉操作中子個(gè)體中的代碼順序根據(jù)任一父?jìng)€(gè)體產(chǎn)生。

變異在遺傳操作中屬于輔助性的搜索操作，主要目的是維持群體的多樣性。較低的變異概率可以防止群體中重要的單一基因丟失，但降低了遺傳算法開(kāi)辟新搜索空間的能力；較高的變異概率將使遺傳操作趨于純粹的隨機(jī)搜索，降低了算法的收斂速度和穩(wěn)定性。這里對(duì)于基因串采用交換變異，即交換兩個(gè)隨機(jī)位置上的基因。

26 解碼

在job shop調(diào)度問(wèn)題中，解碼是一項(xiàng)非常重要的工作。在車間調(diào)度中，針對(duì)解碼方法研究得相對(duì)較少，現(xiàn)大都采用AOV、AOE網(wǎng)絡(luò)圖進(jìn)行解碼，相對(duì)較繁瑣。這里提出一種矩陣形式的解碼方法。根據(jù)以上3×3 job shop調(diào)度問(wèn)題所生成的一條染色體如下:

124537689

根據(jù)表1、2生成一個(gè)矩陣如下：

TMJ=3 0 0 1 0 0 0 3 0

0 3 0 0 0 5 2 0 0

0 0 2 0 3 0 0 0 3

其中：第1~3行分別表示機(jī)器1~2~3；第1~9列分別表示表3中編號(hào)1~9對(duì)應(yīng)的工序；矩陣中不為0的元素表示對(duì)應(yīng)的工序在對(duì)應(yīng)機(jī)器上的加工時(shí)間，元素為0表示對(duì)應(yīng)的工序不在對(duì)應(yīng)的機(jī)器上加工。

在矩陣TMJ中，只體現(xiàn)出工序的機(jī)器約束，體現(xiàn)不出同一工件的工序加工的先后順序約束，這要結(jié)合染色體中的基因來(lái)完成。由于對(duì)染色體基因的修正處理不會(huì)出現(xiàn)非法調(diào)度，第一個(gè)加工的工序肯定是其中一個(gè)工件的第一個(gè)工序，那個(gè)工序?qū)?yīng)矩陣中TMJ的數(shù)值即為該工序的最早完成時(shí)間，將其映射到一個(gè)行數(shù)和列數(shù)與矩陣TMJ相等的矩陣TT中，映射的位置相同。矩陣TT中元素不為0表示對(duì)應(yīng)的工序在其對(duì)應(yīng)機(jī)器上的最早完成時(shí)間。具體步驟如下：

a)建立一個(gè)與矩陣TMJ行數(shù)和列數(shù)相等的0矩陣；

b)將染色體中第一個(gè)加工的工序編號(hào)在矩陣TMJ中對(duì)應(yīng)的加工時(shí)間以相同位置影射到矩陣TT中，本例為編號(hào)1，所得矩陣TT如下所示：

TT=3 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

c)染色體中第二個(gè)加工的工序編號(hào)本例為2，因編號(hào)2為工件1的第二個(gè)工序，有緊前工藝約束(編號(hào)1)，編號(hào)2在矩陣TMJ對(duì)應(yīng)不為0的元素在第2行(即在機(jī)器2上加工)，編號(hào)1位于編號(hào)2的前一列，由上式所示的矩陣TT中可以看出J11的最早完成時(shí)間為3，矩陣TT第2行的最大數(shù)值為0，考慮工藝約束和機(jī)器加工順序，將矩陣TMJ第2行第2列的數(shù)值加上max(0， 3)即為編號(hào)2的最早完成時(shí)間，將其映射到矩陣TT第2行第2列，便得到新的矩陣TT：

TT=

3 0 0 0 0 0 0 0 0 0

0 6 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

d) 染色體中第三個(gè)加工的工序本例為編號(hào)4，由于編號(hào)4為工件2的第1個(gè)工序，沒(méi)有緊前工藝約束，只考慮機(jī)器加工順序，編號(hào)4在矩陣TMJ對(duì)應(yīng)不為0的元素在第1行(即在機(jī)器1上加工)，上式矩陣TT第1行的最大數(shù)值為3，考慮機(jī)器加工順序，將矩陣TMJ第1行第4列的數(shù)值加上3即為編號(hào)4的最早完成時(shí)間，將其映射到矩陣TT第1行第4列，便得到新的矩陣TT：

TT=

3 0 0 4 0 0 0 0 0

0 6 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

其余的依此類推，直到進(jìn)行到第9個(gè)加工的工序，求得最終得矩陣TT：

TT=3004000110

0600013800

0090700014

針對(duì)此調(diào)度和此條染色體，求矩陣TT的MATLAB程序如下：

TT=zeros(3，9);

O=[1，2 ，4， 5 ，3 ，7 ，6 ，8， 9]; %染色體中基因

TT (:， O(1))=TMJ (:， O(1));%第一個(gè)被加工的工序

for i=2:9;

[a ， b]=find (TMJ (: ， O(i))~=0);

if O(i) == (1|4|6); %每個(gè)工件的第一個(gè)工序編號(hào)

TT (a， O(i)) = TMJ(a， O(i))+max(TT(a，:));

else

TT(a， O(i))=TMJ(a， O(i))+max([max(TT(a，:))， … sum(TT(:，O(i)-1))] );

end

end

由于矩陣中不為0的數(shù)值表示的是每個(gè)工序的最早完成時(shí)間，矩陣中最大的數(shù)即為該條染色體所表示的job shop調(diào)度問(wèn)題的最大完成時(shí)間：max(Ci)=14。

由于job shop調(diào)度問(wèn)題是求解最小化最大完成時(shí)間，將所有染色體按上述步驟解碼后所求得數(shù)值的最小數(shù)值為該次迭代的最小化的最大完成時(shí)間，染色體通過(guò)不斷選擇、交叉和變異操作，最終求得最優(yōu)調(diào)度。

3 實(shí)例仿真和比較

31實(shí)例1

為了便于比較采用文獻(xiàn)[8]中的實(shí)例，設(shè)有8個(gè)工件(J1，J2，…，J8)，5臺(tái)機(jī)器(M1，M2，…，M5)的生產(chǎn)線作業(yè)調(diào)度問(wèn)題，加工時(shí)間及加工順序分別如表4、5所示。

表4 8×5 job shop調(diào)度問(wèn)題加工時(shí)間表MJ1J2J3J4J5J6J7J8M110187.61713.6096M29.8151.915105.49.49M311.218.5135.6812340M4132420.516.414.914.813.619M520.82211300242057表5 8×5 job shop調(diào)度問(wèn)題加工順序表MJ1J2J3J4J5J6J7J8M112131534M221342111M333254225M444523452M555415343表6 Job shop調(diào)度方案MTJ1J2J3J4J5J6J7J8M1開(kāi)始13.663.823.681.80173.252.498.8結(jié)束23.681.831.298.813.6173.261.4104.8M2開(kāi)始23.648.877.498.833.443.490結(jié)束33.463.879.3113.843.448.818.49M2開(kāi)始52.481.864.4113.8100.352.418.4104.8結(jié)束63.6100.377.4119.4108.364.452.4104.8M2開(kāi)始63.6100.3137.92945.4158.4124.39結(jié)束76.6124.3158.445.460.3173.2137.929M2開(kāi)始1641421070108.31188730結(jié)束184.816411830108.314210787

根據(jù)本文提出的編碼用遺傳算法在計(jì)算機(jī)上進(jìn)行仿真實(shí)驗(yàn)。這里交叉概率取0.9，并分別采用部分匹配(PMX)交叉操作、循環(huán)交叉(CX)操作，變異概率取0.5，種群規(guī)模均取50，最大迭代次數(shù)均為20，得出的調(diào)度方案如表6所示，進(jìn)化值曲線如圖1所示，10次隨機(jī)仿真的最終結(jié)果如表7所示。

表7 調(diào)度計(jì)算結(jié)果與比較指標(biāo)（最小完成時(shí)間）最優(yōu)指標(biāo)平均指標(biāo)種群規(guī)模最大進(jìn)化次數(shù)直接用工序編號(hào)編碼并用拒絕策略241.5242.2100100文獻(xiàn)[8]的編碼方案241.5241.7100100本文算法(PMX)184.8184.85020本文算法（CX）184.8184.8502032 實(shí)例2

在文獻(xiàn)[9]分別用優(yōu)先列表編碼方式的遺傳算法和基于工序編碼方式的遺傳算法，并采用自適應(yīng)遺傳算子對(duì)一標(biāo)準(zhǔn)的job shop調(diào)度問(wèn)題進(jìn)行了仿真，具體數(shù)據(jù)參見(jiàn)該文獻(xiàn)。

文獻(xiàn)[9]種群規(guī)模取100，迭代次數(shù)取1 000，所求得最優(yōu)解為55。本文算法交叉概率取0.9，采用部分匹配(PMX)交叉操作、交換變異概率取0.5，種群規(guī)模取50，迭代次數(shù)為30，得出的最優(yōu)解為55，進(jìn)化值曲線如圖2所示。

33 比較

在實(shí)例1中，本文方法以較小的種群規(guī)模和較少的迭代次數(shù)求得的最優(yōu)調(diào)度明顯優(yōu)于文獻(xiàn)[8]中所求得的結(jié)果；在實(shí)例2中，本文方法比文獻(xiàn)[9]用較小的種群規(guī)模和較少的迭代次數(shù)求得最優(yōu)解。通過(guò)比較，本文中的遺傳算法在收斂速度和穩(wěn)定性方面的效果是比較好的，明顯優(yōu)于文獻(xiàn)[8，9]的算法。

4 結(jié)束語(yǔ)

從實(shí)例仿真可以看出，本文提出的遺傳算法基因編碼和解碼方法簡(jiǎn)潔，能清楚地反映出調(diào)度方案關(guān)系，能應(yīng)用多種交叉算子進(jìn)行操作；收斂速度快，能有效地解決大規(guī)模job shop調(diào)度問(wèn)題。通過(guò)比較，解的質(zhì)量是比較滿意的，有廣泛實(shí)際應(yīng)用的良好前景。

參考文獻(xiàn)：

[1]王凌.車間調(diào)度及其遺傳算法[M]. 北京:清華大學(xué)出版社，2003:56-101.

[2]王凌，鄭大鐘.基于遺傳算法的job shop調(diào)度問(wèn)題研究進(jìn)展[J]. 控制與決策，2001，16(增):641-645.

[3]FOO S Y， TAKEFUJI Y. Inter-linear programming neural networks for job shop scheduling[C]//Proc of IEEE IJCNN. San Diago: [s.n.]， 1988:341-348.

[4]WU C G， LI X P， ZHOU P. A job shop oriented virus genetic algorithm[C]// Proc of the 1st World Congress on Intelligent Control and Automation. 2004:2132-2136.

[5]趙良輝，鄧飛其.解決job shop調(diào)度問(wèn)題的模擬退火算法改進(jìn)[J]. 計(jì)算機(jī)工程，2006，32(21):38-40.

[6]曹承煜，李人厚，樊健.車間調(diào)度算法的研究和開(kāi)發(fā)[J].控制理論與應(yīng)用，2000，17(1):31-34.

[7]王萬(wàn)良，吳啟迪，宋毅.求解作業(yè)車間調(diào)度問(wèn)題的改進(jìn)自適應(yīng)遺傳算法[J].系統(tǒng)工程理論與實(shí)踐，2004，30(2):58-62.

[8]柳林. 基于遺傳算法的job shop調(diào)度問(wèn)題求解[J]. 計(jì)算機(jī)應(yīng)用， 2006，26(7):1694-1696.

[9]莊新村，盧宇灝，李從心. 基于遺傳算法的車間調(diào)度問(wèn)題[J]. 計(jì)算機(jī)工程，2006，32(1):193-194.

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

[11]周明，孫樹(shù)棟.遺傳算法原理及應(yīng)用[M]. 北京:國(guó)防工業(yè)出版社，1999:146-254.