基于遺傳算法的Job-Shop調(diào)度問題研究

陶　澤，張海濤

(沈陽理工大學(xué) 機(jī)械工程學(xué)院，沈陽110159)

?

基于遺傳算法的Job-Shop調(diào)度問題研究

陶澤，張海濤

(沈陽理工大學(xué) 機(jī)械工程學(xué)院，沈陽110159)

摘要：研究單目標(biāo)作業(yè)車間調(diào)度問題(JSP)，提出了一種基于遺傳算法以縮短生產(chǎn)周期為目標(biāo)的Job-Shop調(diào)度問題。通過建立數(shù)學(xué)模型，設(shè)置編碼、解碼方案，以及確定選擇、交叉、變異等遺傳算子，充分利用遺傳算法的特點(diǎn)解決加工車間靜態(tài)、動態(tài)問題，并通過Gantt圖給出調(diào)度方案。結(jié)合應(yīng)用實(shí)例進(jìn)行分析，分析結(jié)果表明該方法是有效的、可行的。

關(guān)鍵詞：作業(yè)車間調(diào)度；遺傳算法；Gantt圖

作業(yè)車間調(diào)度(Job-Shop Scheduling)是車間調(diào)度中最常見的調(diào)度類型，是最難的組合優(yōu)化問題之一[1]，對其研究具有重大的現(xiàn)實(shí)意義?？茖W(xué)有效的生產(chǎn)調(diào)度不但可以提高生產(chǎn)加工過程中操作工人、設(shè)備資源的高效利用，而且還可以縮短生產(chǎn)周期，降低生產(chǎn)成本。隨著遺傳算法在組合優(yōu)化問題的廣泛應(yīng)用，許多人開始對遺傳算法進(jìn)行深度研究，并應(yīng)用它求解車間調(diào)度問題。

目前，對作業(yè)車間調(diào)度問題的研究大都集中在靜態(tài)調(diào)度上，對動態(tài)調(diào)度的研究很少。因?yàn)閯討B(tài)調(diào)度要比靜態(tài)調(diào)度復(fù)雜得多，另外因?yàn)樵谘芯縿討B(tài)調(diào)度問題時(shí)，由于在實(shí)際的生產(chǎn)加工過程中不確定以及隨機(jī)因數(shù)太多，任何單一的規(guī)則都較難適用于所有的動態(tài)環(huán)境。

在最近幾年，對動態(tài)調(diào)度問題的研究方法主要有人工智能方法、仿真方法等[2]。這些方法不但開發(fā)成本高，而且開發(fā)周期也很長，不適應(yīng)于企業(yè)的應(yīng)用。相比之下，遺傳算法作為一種新型仿生算法為求解生產(chǎn)調(diào)度問題提供了新的解決思路。

因此，本文提出了一種應(yīng)用遺傳算法求解作業(yè)車間動態(tài)調(diào)度的方法，為了評價(jià)這種方法的有效性，以最優(yōu)完工時(shí)間為目標(biāo)[3]模擬加工車間，通過模擬結(jié)果可以觀察出應(yīng)用遺傳算法求解此類問題是有效的。

1Job-Shop調(diào)度問題的描述

作業(yè)車間調(diào)度是一個經(jīng)典的調(diào)度問題，如今在國內(nèi)外受到研究人員們的高度重視，它是對一個可用的加工機(jī)器集在時(shí)間上進(jìn)行加工任務(wù)集分配，以滿足一個性能指標(biāo)集，問題可以描述為有M臺機(jī)器、N個工件，每個工件由一系列的操作組成。用MC={mk}表示加工機(jī)器集，其中k=1，2，…，M；用JC={jk}表示加工工件集，其中k=1，2，…，N；OP={opik}表示加工工序集，i=1，2，…，N；k=1，2，…，M。每個操作opik必須滿足預(yù)先給定的加工約束條件以及加工時(shí)間，從而使各工件的工序合理地安排到各加工機(jī)器上進(jìn)行操作，并且能夠使所有工件的最終完工時(shí)間達(dá)到較優(yōu)值。

2遺傳算法

遺傳算法(GA)是以種群為基礎(chǔ)的搜索算法，種群中每個個體代表所求問題的一個解，把要解決的問題編碼成字符串染色體，然后從任意的初始群體進(jìn)行搜索，通過種群中染色體基因的選擇、交叉、變異等遺傳操作可使種群進(jìn)化到越來越好的搜索空間，最終收斂“最適應(yīng)環(huán)境的個體”，從而求得問題的最優(yōu)解或滿意解[4]。該算法在解決一些特殊問題上效率不是特別理想，但是應(yīng)用到一般的優(yōu)化問題上效率還是優(yōu)于一些傳統(tǒng)隨機(jī)算法，本文提出的遺傳算法流程見圖1。

圖1　遺傳算法流程圖

3Job-Shop調(diào)度問題的數(shù)學(xué)模型

由于作業(yè)車間調(diào)度問題是考慮N個工件在M臺機(jī)器上加工排序問題，各工件的各工序由Q個操作組成，并且每個操作要求在不同的機(jī)器上加工，每個工件的所有操作特點(diǎn)在于加工機(jī)器和加工時(shí)間是固定的，具體描述如下[5]：

(1)對于工件的加工優(yōu)先約束條件：在這里讓Cik表示工件i在機(jī)器k上的完工時(shí)間，tik表示工件i在機(jī)器k上的加工時(shí)間，假設(shè)機(jī)器h先于機(jī)器k加工工件i，則約束條件可描述如下：

Cik-tik≥Cih

(1)

(2)對于機(jī)器的操作優(yōu)先約束條件：假設(shè)工件i和工件j在某一時(shí)刻都要在機(jī)器k上加工，如果工件i先于工件j到來，則約束條件可描述如下：

Cjk-Cik≥tjk

(2)

由于本文的JSP是以工件的最短完工時(shí)間為目標(biāo),故目標(biāo)函數(shù)為

(3)

約束條件為

Cik-tik≥Cih,(i=1,2,…,N，h,k=1,2,…,M)

Cjk-Cik≥tjk，(i,j=1,2,…,N，k=1,2,…,M)

式中：Cik表示工件i在機(jī)器k上的完工時(shí)間；tik表示工件i在機(jī)器k上的加工時(shí)間；Cih表示工件i在機(jī)器h上的完工時(shí)間；Cjk表示工件j在機(jī)器k上的完工時(shí)間；tjk表示工件j在機(jī)器k上的加工時(shí)間；M為機(jī)器的數(shù)量；N為工件數(shù)。

4Job-Shop調(diào)度的算法實(shí)現(xiàn)

4.1編碼

根據(jù)車間作業(yè)實(shí)際情況，本文采用基于工序的編碼方式[6]，這種編碼方法是把調(diào)度編碼為工序的序列，個體中的每個基因代表一道工序，對于{m1，m2，…，mM}臺機(jī)器和{j1，j2，…，jN}個工件的車間作業(yè)調(diào)度問題的染色體編碼為

[g1，g2，g3，…，gM×N]

式中，gi表示工件的編號，工件編號在染色體出現(xiàn)的次數(shù)表示執(zhí)行工件在該次數(shù)的加工工序，例如，g2在染色體中第二次出現(xiàn)表示執(zhí)行第二類型工件的第一道工序，這樣很容易看出染色體的任意排列總能產(chǎn)生可行調(diào)度，而且這些可行調(diào)度之中一定含有最優(yōu)調(diào)度。例如以3×3調(diào)度問題為例，介紹編碼實(shí)現(xiàn)過程，根據(jù)上述編碼策略，該調(diào)度問題的編碼方案見表1。

表1　編碼方案

4.2解碼

解碼過程是將染色體 [g1，g2，g3，…，gM×N]中的每一個基因(工件號)根據(jù)其在染色體中出現(xiàn)的次序解碼成各工件的工序。例如，對上述3個工件3臺機(jī)器(3×3)的調(diào)度問題的編碼進(jìn)行解碼，根據(jù)表1編碼方案可知其染色體的隨機(jī)初始化為[2 2 1 3 3 1 1 3 2]，故可以解碼為：首先加工工件2的第一道工序，接下來工件2的第二道工序，然后是工件1的第一道個工序，接著是工件3的第一道工序…。根據(jù)工件每個工序所要求的機(jī)器號得出每個基因所對應(yīng)的機(jī)器順序，比如工件2所需機(jī)器號分別為M1、M2、M3，則表示工件2的第一個工序在M1上加工，第二個工序在M2上加工，第三個工序在M3上加工。然后根據(jù)各個工件的加工時(shí)間得到相應(yīng)的加工時(shí)間，就可以完成一個調(diào)度方案。

4.3適應(yīng)度函數(shù)

在遺傳算法中采用適應(yīng)度函數(shù)對染色體的優(yōu)劣進(jìn)行評價(jià)，染色體的適應(yīng)值越高被遺傳到下一代種群的概率越高，反之則相反。另一方面，若適應(yīng)度函數(shù)設(shè)計(jì)不當(dāng)，將難以體現(xiàn)個體的差異，選擇操作的作用就很難體現(xiàn)出來，從而造成早熟收斂等特點(diǎn)。所以適應(yīng)度函數(shù)的合理確定在優(yōu)化過程中起著至關(guān)重要的作用，根據(jù)目標(biāo)函數(shù)要求的是最小化最大完工時(shí)間問題，所以用染色體解碼后的最大完工時(shí)間的倒數(shù)為適應(yīng)值。設(shè)xkmax表示第k個染色體的最大完工時(shí)間，則可以定義適應(yīng)度函數(shù)為

F(xk)=1/xkmax

(4)

當(dāng)xkmax減小時(shí)，則F(xk)增加，即染色體的最大完工時(shí)間越小，適應(yīng)值越大。

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

(1)選擇操作即在計(jì)算出種群中各個體的適應(yīng)值的基礎(chǔ)上對所有個體由優(yōu)到劣進(jìn)行排列，然后以一個具體的方式把一定的選擇概率分配給各個體。設(shè)M為種群大小，F(xiàn)it為個體i的適應(yīng)度，則個體i被選中的概率為

(5)

(2)交叉操作當(dāng)選擇操作執(zhí)行完以后，交叉操作將兩個配對的染色體部分基因交換從而形成兩個新的染色體，該操作不能過多破壞個體中表現(xiàn)優(yōu)良的編碼串。例如，父代1:α[p1]=a、b、c、d、e ;父代2：β[p2]=c、d、e、b、a，從兩父代染色體中隨機(jī)選取基因a、b、e，然后將這兩個基因從中選取出來，并且使它們與原父代中的位置一致，得到的子串基因分別為：f[p3]=a、b、e，h[p4]=e、b、a，此時(shí)兩父代種群出現(xiàn)三個空缺位置，隨之將子串f[p3]→α[p1]、h[p4]→β[p2]，即可得出子代α1[p5]=e、b、c、d、a，β[p6]=c、d、a、b、e。

(3)變異操作 為了增強(qiáng)遺傳算法的局部搜索能力并且能夠提高種群的多樣性，變異操作將染色體編碼串中的某些基因進(jìn)行改變，從而使遺傳算法以良好的搜索性能來完成最優(yōu)化的過程。所以采用如下變異方法：

變異前

父代 ( A, B, C, D, E, F )

變異后

子代 ( A, B, F, E, D, C)

具體的執(zhí)行步驟是：首先從父代中隨機(jī)選擇第3位到第6位的所有基因即得到基因串C、 D、 E、 F，然后按逆序排列就可得到子代。

5算例仿真

5.1靜態(tài)算例仿真

該次測試中以靜態(tài)調(diào)度為例，以工件生產(chǎn)周期最短為目標(biāo)。采用Delphi7.0軟件編程實(shí)現(xiàn)上述算法，采用面向?qū)ο蟮木幊滩呗?。?dāng)工件加工順序、加工時(shí)間確定以后在加工過程中不考慮任何緊急事件的發(fā)生，待加工工件依次進(jìn)入加工系統(tǒng)，工件的加工順序以及各項(xiàng)加工參數(shù)不變即加工環(huán)境為一個靜態(tài)過程。在仿真實(shí)例中，以6×6調(diào)度問題為例，算例相關(guān)參數(shù)為：工件種類JC={j0，j1，j2，j3，j4，j5}，機(jī)器種類MC={m0，m1，m2，m3，m4，m5}，每個工件在相應(yīng)的機(jī)器上的加工順序與加工時(shí)間見表2所示。

表2　工件在機(jī)器上的加工順序及加工時(shí)間

在仿真過程中設(shè)置各個機(jī)器的加工開始時(shí)刻為0，為了驗(yàn)證算法的有效性，取仿真次數(shù)為1、2、3、4、5、6、7、8，種群數(shù)目100、交叉概率pc=0.8、變異概率pm=0.1，由于篇幅有限只給出Delphi7.0軟件一部分操作界面見圖2。

Delphi7.0軟件仿真次數(shù)與相應(yīng)的結(jié)果見表3所示。

圖2　軟件界面

次數(shù)12345678結(jié)果5558545756575353

通過仿真結(jié)果可以清楚地看出，每次運(yùn)行的結(jié)果略有差別，但是上下浮動不大，穩(wěn)定性相對平穩(wěn)。安晶等人提出的算法[7]研究結(jié)果是55個單位時(shí)間(生產(chǎn)周期)，本文提出的算法得到的最佳調(diào)度結(jié)果為53個單位時(shí)間，很明顯得到的結(jié)果優(yōu)于前者2個單位時(shí)間。算法得到最優(yōu)調(diào)度Gantt圖見圖3。

圖3　靜態(tài)調(diào)度Gantt圖

5.2動態(tài)算例仿真

在實(shí)際生產(chǎn)加工車間中，加工環(huán)境是一個動態(tài)的過程有許多不確定因素[8]，例如，緊急訂單、操作工人離崗等都會擾動原調(diào)度計(jì)劃，因此，生產(chǎn)調(diào)度人員必須考慮重新安排調(diào)度，假設(shè)在生產(chǎn)加工進(jìn)行4小時(shí)，緊急訂單即工件6需要進(jìn)行加工，這里要考慮兩個要求：已經(jīng)加工完工的工件工序不予考慮、正在進(jìn)行加工的工件不予考慮，工件6加工時(shí)間矩陣T=[367]，加工機(jī)器矩陣M=[251 ]。由圖3可知，當(dāng)緊急訂單到來時(shí)，已完工工件和正在加工工件信息見表4。

表4　完工工件及正在加工工件

表中mk(i，j)表示第i個工件的第j道工序在機(jī)器k上進(jìn)行加工或已完成加工。通過仿真得到的動態(tài)系統(tǒng)的Gantt圖見圖4，由圖4可以看出，動態(tài)調(diào)度系統(tǒng)的最優(yōu)完工時(shí)間(56)和緊急工件到來之后各工件在各機(jī)器上分配關(guān)系，同時(shí)圖4也明顯地反映出動態(tài)調(diào)度系統(tǒng)要比靜態(tài)調(diào)度系統(tǒng)復(fù)雜得多[9]，由仿真結(jié)果不難看出應(yīng)用遺傳算法求解車間作業(yè)動態(tài)調(diào)度問題是有效和可行的。

圖4　動態(tài)調(diào)度Gantt圖

6結(jié)束語

提出了運(yùn)用遺傳算法優(yōu)化動態(tài)調(diào)度問題，在動態(tài)方面主要考慮了緊急訂單，通過確定算法的編碼、解碼以及遺傳算子的設(shè)計(jì)，在建立調(diào)度模型的基礎(chǔ)上，由模擬仿真先優(yōu)化出靜態(tài)結(jié)果，在此基礎(chǔ)上進(jìn)行重調(diào)度即動態(tài)調(diào)度。仿真結(jié)果表明該方法是可行的并且能夠得到較好的效果。

參考文獻(xiàn)：

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

[2]吳云高,王萬良.基于遺傳算法的混合Flowshop調(diào)度[J].計(jì)算機(jī)工程與應(yīng)用,2002,38(12):82-84.

[3]陳振同.基于改進(jìn)遺傳算法的車間調(diào)度問題研究與應(yīng)用[D].大連:大連理工大學(xué),2007.

[4]劉曉霞,謝里陽,陶澤,等.柔性作業(yè)車間多目標(biāo)調(diào)度優(yōu)化研究[J].東北大學(xué)學(xué)報(bào):自然科學(xué)版,2008,29(3):362-365.

[5]Liu T,Tsai J,Chou J.Improved genetic algorithm for the job-shop scheduling problem[J].International Journal of Advanced Manufacturing Technology,2006,27(9-10):1021-1029.

[6]蔣麗雯.基于遺傳算法車間作業(yè)調(diào)度問題研究[D].上海:上海交通大學(xué),2007.

[7]安晶.一種基于遺傳算法的車間調(diào)度算法求解[D].鹽城:鹽城工學(xué)院,2007.

[8]陳勇,胡婷婷,魯建廈.基于遺傳算法改進(jìn)的動態(tài)車間調(diào)度[J].浙江工業(yè)大學(xué)學(xué)報(bào),2012,40(5):537-543.

[9]徐雯雯.基于遺傳算法的車間動態(tài)粗調(diào)度研究[D]濟(jì)南:山東大學(xué),2010.

(責(zé)任編輯：馬金發(fā))

Studies on Job-Shop Scheduling Problems Based on Genetic Algorithms

TAO Ze，ZHANG Haitao

(Shenyang Ligong University,Shenyang 110159,China)

Abstract：The single target job-shop scheduling problem (JSP is focused on)；First of all，a genetic algorithm is proposed to shorten the production cycle of job shop schedule；Secondly，through mathematical model establishment，genetic algorithm of characteristics is applied to solve the processing plant static and dynamic problems by setting the encoding and decoding scheme and determining the selection，crossover and mutation genetic operators，and genetic algorithm of characteristics is applied to solve the processing plant static and dynamic problems，which is given by the Gantt chart scheduling scheme；Finally，with the analysis of example，the results show that the method is effective and feasible.

Key words：job shop scheduling；genetic algorithm；Gantt chart

中圖分類號：TP311

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

文章編號：1003-1251(2016)02-0060-05

作者簡介：陶澤(1977—)女，副教授，研究方向：微制造與信息處理技術(shù)。

收稿日期：2015-04-09