張騰飛，馬　躍,胡　毅，3，安　濤，王　帥，郭　安

(1.中國(guó)科學(xué)院大學(xué)，北京　100049； 2.中國(guó)科學(xué)院 沈陽計(jì)算技術(shù)研究所,沈陽　110004;3.沈陽高精數(shù)控智能技術(shù)股份有限公司,沈陽　110168)

?

基于遺傳算法的多目標(biāo)車間調(diào)度問題的研究*

張騰飛1,2，馬躍2,胡毅2，3，安濤1,2，王帥1,2，郭安1,2

(1.中國(guó)科學(xué)院大學(xué)，北京100049； 2.中國(guó)科學(xué)院 沈陽計(jì)算技術(shù)研究所,沈陽110004;3.沈陽高精數(shù)控智能技術(shù)股份有限公司,沈陽110168)

摘要：文章討論了一個(gè)多目標(biāo)車間調(diào)度問題(JSP)。在JSP問題中我們考慮一個(gè)具有n個(gè)工件和m臺(tái)機(jī)器的生產(chǎn)線，每道工序在不同的機(jī)器上完成且有各自的持續(xù)時(shí)間。JSP調(diào)度問題的目標(biāo)是在所有工件的工序在m臺(tái)機(jī)器上加工且不沖突的前提下找到一個(gè)最短的總調(diào)度時(shí)間。該文通過使用遺傳算法來找到作業(yè)調(diào)度問題的最優(yōu)方案。文中通過使用11種不同規(guī)格的標(biāo)準(zhǔn)測(cè)試用例來測(cè)試算法的性能。實(shí)驗(yàn)結(jié)果表明，實(shí)驗(yàn)的運(yùn)行結(jié)果滿足了調(diào)度要求，進(jìn)一步證明了遺傳算法的有效性和實(shí)用性。

關(guān)鍵詞：作業(yè)調(diào)度；加工車間；遺傳算法；啟發(fā)式；多目標(biāo)

0引言

在車間生產(chǎn)實(shí)際中，作業(yè)調(diào)度的好壞直接影響著企業(yè)的生產(chǎn)效率。車間作業(yè)調(diào)度問題[9](Job Shop Scheduling Problem，JSP)是組合優(yōu)化問題中的一個(gè)典型的NP-hard問題，在過去的十多年中吸引了許多研究者的注意。文獻(xiàn)[1]中作者研究了機(jī)器數(shù)目固定條件下的多目標(biāo)車間調(diào)度問題，他們提出了一種兩階段的啟發(fā)式方法來解決該問題。首先，基于優(yōu)先級(jí)規(guī)則和禁忌搜索算法來得到一個(gè)可行解；然后，在此基礎(chǔ)上用遺傳算法來解決作業(yè)調(diào)度問題。文獻(xiàn)[2]中作者研究了在有限的機(jī)器數(shù)目條件下求解車間調(diào)度問題的最短的總調(diào)度時(shí)間，他們提出了一種基于塊鄰域函數(shù)的高斯模糊啟發(fā)式算法。遺傳算法比較容易實(shí)現(xiàn)且可根據(jù)不同的調(diào)度問題相對(duì)容易地做出相應(yīng)的調(diào)整，實(shí)驗(yàn)表明，它可以在可以接受的時(shí)間范圍內(nèi)求出理想的調(diào)度方案。有許多文獻(xiàn)推薦使用遺傳算法解決車間調(diào)度問題。文獻(xiàn)[3]中作者實(shí)現(xiàn)了一種基于局部搜索算子的混合遺傳算法。文獻(xiàn)[4]中作者提出一種兩階段的算法實(shí)驗(yàn)方案，該算法分兩階段整合了基于規(guī)則的文化基因算法和轉(zhuǎn)換瓶頸的再優(yōu)化算法，實(shí)驗(yàn)結(jié)果表明該算法對(duì)車間調(diào)度問題正確且有效。

1車間作業(yè)調(diào)度問題描述

JSP問題是一個(gè)包含n個(gè)工件和m臺(tái)機(jī)器的調(diào)度問題，其常用的數(shù)學(xué)描述如下：

Cmax≥ tij+ pijfor all (i,j)∈N

tkj≥tij+ pijforall(i,j)τ(k,j)∈A

tij≥tik+ pikforall(i,j)and(i,k)∈N

tik≥ tij+ pijforall(i,j)and(i,k)∈N

tij≥0forall(i,j)∈N

其中，Cmax表示完成所有工件加工后的最大完工時(shí)間，pij來表示工件j在機(jī)器i上的加工時(shí)間，tij表示工件j在機(jī)器i上的開始加工時(shí)間，N表示操作(i,j)的集合，A表示所有所有的工件j在機(jī)器k上加工前必須在機(jī)器i上加工操作依賴關(guān)系對(duì)(i,j)→(k,j)的集合。

2遺傳算法簡(jiǎn)介

遺傳算法是模擬、解決或優(yōu)化問題的計(jì)算方法，它是受自然界中通過選擇、交叉和變異來實(shí)現(xiàn)生物進(jìn)化的啟發(fā)而提出的。當(dāng)遺傳算法被應(yīng)用到調(diào)度問題中，一個(gè)有效的調(diào)度序列被稱作染色體或個(gè)體，每個(gè)個(gè)體都有自己的適應(yīng)度值。遺傳算法以迭代的方式運(yùn)行，每次迭代代表了種群的一代。每一代種群個(gè)體包括上一代的幸存者和新的經(jīng)過交叉、變異和選擇后而新產(chǎn)生的比較優(yōu)秀的個(gè)體。不同的染色體是否被選擇是由它們的適應(yīng)度值來決定的，適應(yīng)度越值大，被選中的概率越大。在實(shí)驗(yàn)中這種選擇機(jī)制一直被重復(fù)，直至滿足給定的條件為止。

3遺傳算法解決車間調(diào)度問題

本文中將分以下幾個(gè)步驟來介紹遺傳算法。

3.1問題建模

本文將用兩個(gè)二維數(shù)組machineNoMatrix[][]和timeMatrix[][]來分別表示第i個(gè)工件的第j道工序所使用機(jī)器的機(jī)器號(hào)和所耗費(fèi)的時(shí)間，數(shù)組的行號(hào)和列號(hào)分別代表了工件的工件號(hào)和工序號(hào)，當(dāng)?shù)趇個(gè)工件的第j道工序不存在的話，令machineNoMatrix[i-1][j-1]=-1，timeMatrix[i-1][j-1]=0。

3.2編碼

染色體序列的長(zhǎng)度為n×m，n表示工件的數(shù)量，m表示機(jī)器的數(shù)量，染色體序列的每一個(gè)元素是[1,n]之間的一個(gè)隨機(jī)數(shù)，該數(shù)字在序列中第幾次出現(xiàn)表示它所代表工件的第幾道工序，本文采用的是基于間接工序的編碼方法[12]。例如，對(duì)于一個(gè)3個(gè)工件×4臺(tái)機(jī)器的作業(yè)調(diào)度問題,其染色體的大小為12(3×4)。工件1可以用數(shù)字1來表示，它重復(fù)出現(xiàn)3次表示工件1有3道加工工序。

3.3解碼

我們從左到右解碼一個(gè)染色體序列，下面以一個(gè)3個(gè)工件×4臺(tái)機(jī)器的車間調(diào)度問題為例來說明解碼規(guī)則：

圖1一個(gè)3×4車間調(diào)度問題的染色體實(shí)例

如圖1所示，染色體序列的第一個(gè)元素為1，表示工件1，而工件1第一次出現(xiàn)表示是工件1的第一道工序。然后再以第六個(gè)元素1例，它表示工件1的第三道工序。我們可以從如圖1所示的染色體編碼序列中獲得當(dāng)前執(zhí)行到哪個(gè)工件的哪一道工序。

3.4初始化種群

首先隨機(jī)產(chǎn)生一個(gè)300條染色體大小的種群，每條染色體代表一個(gè)個(gè)體，即一個(gè)可行的作業(yè)調(diào)度序列。

3.5適應(yīng)度值計(jì)算

本文的適應(yīng)度值的取值為各個(gè)工件完成所有加工操作的最大完工時(shí)間(Cmax)。根據(jù)帕累托最優(yōu)原則，每個(gè)染色體的適應(yīng)度值代表該染色體的優(yōu)勢(shì)排名。

求解車間調(diào)度的最短的總調(diào)度時(shí)間的難點(diǎn)在于：一方面，各個(gè)工件不同的工序之間有嚴(yán)格的先后順序；另一方面，同一臺(tái)機(jī)器在某個(gè)時(shí)刻只可以加工一種工件。各個(gè)工件不同的工序之間有嚴(yán)格的先后順序這個(gè)問題已經(jīng)在染色體編碼序列中已經(jīng)被解決，因?yàn)槿旧w序列中各個(gè)工件出現(xiàn)的順序就代表著各個(gè)工件的工序序列。而同一臺(tái)機(jī)器某個(gè)時(shí)刻只可以加工一種工件這個(gè)問題可以通過維護(hù)一個(gè)機(jī)器數(shù)目大小的一維數(shù)組來實(shí)現(xiàn)，數(shù)組存儲(chǔ)的值是該機(jī)器處理完當(dāng)前工件后的空閑時(shí)間點(diǎn)。

車間調(diào)度執(zhí)行的順序是按染色體編碼序列的順序從左向右執(zhí)行，由調(diào)度問題的執(zhí)行位置和染色體編碼序列可知要加工工件的工件號(hào)i，然后通過工件號(hào)在染色體序列的當(dāng)前位置獲得該工件所在的工序號(hào)j，由工件號(hào)和工序號(hào)從二維數(shù)組machineNoMatrix[][]和timeMatrix[][]獲得第i個(gè)工件的第j道工序所使用的機(jī)器號(hào)和所耗費(fèi)的時(shí)間，然后更新第i個(gè)工件第j道工序的開始時(shí)間為第i個(gè)工件第(j-1)道工序的結(jié)束時(shí)間或該工序?qū)⒁褂脵C(jī)器的最近空閑時(shí)間點(diǎn)的之中的較大者，更新第i個(gè)工件第j道工序的結(jié)束時(shí)間為該工序的開始時(shí)間與加工時(shí)間之和，更新該工序所使用機(jī)器的最近空閑時(shí)間點(diǎn)為第i個(gè)工件第j道工序的加工完成時(shí)間。如果該工序的完工時(shí)間大于當(dāng)前的最大完工時(shí)間，更新最大完工時(shí)間的值，直至染色體序列中的所有工序至所有工序被加工完畢，最終可以獲得完成車間調(diào)度所需的最大完工時(shí)間，即適應(yīng)度的值。

3.6選擇

在每一個(gè)連續(xù)的父代子代中，父代的一部分被選擇來產(chǎn)生新的一代，然后基于適應(yīng)度值來選擇新產(chǎn)生的個(gè)體，適應(yīng)度越大的個(gè)體越有可能被選中，本文將輪盤賭策略和精英策略相結(jié)合的方式來選擇交叉和變異步驟所需的候選染色體。

3.7交叉和變異

本文測(cè)試了三種交叉算子(順序交叉：OX[5],循環(huán)順序交叉：COX[6],混合順序交叉：MOX[7])和兩種變異算子(逆轉(zhuǎn)變異：OBM[8]和互換的基因突變：SBM[8])，在完成這六種可能的交叉、變異對(duì)的測(cè)試后，本文保留了順序交叉(概率P=0.95)和逆轉(zhuǎn)變異(P=0.02)操作符。下面就分別簡(jiǎn)要介紹下本文所用到的交叉和變異算子。

3.7.1逆轉(zhuǎn)變異算子

染色體中的兩個(gè)值交換它們的位置，如圖2所示。

圖2　逆轉(zhuǎn)變異算子示例

3.7.2順序交叉算子

對(duì)于一個(gè)n個(gè)工件×m臺(tái)機(jī)器的車間調(diào)度問題，首先產(chǎn)生范圍在[1,n×m]的兩個(gè)隨機(jī)數(shù)且第一個(gè)隨機(jī)數(shù)小于第二個(gè)隨機(jī)數(shù)，n×m是染色體編碼序列的長(zhǎng)度，產(chǎn)生的兩個(gè)隨機(jī)樹代表父代染色體的要遺傳給子代染色體的染色體序列的起始和結(jié)束位置，在本例中的兩個(gè)隨機(jī)數(shù)分別為3和5。父代染色體的部分編碼序列被子代繼承：Father 1的編碼序列(3 1 1)被Child 1繼承，F(xiàn)ather 2的編碼序列(3 2 1)被Child 2繼承。

Child 1:[_,_,_,3,1,1,_,_,_]，繼承的工序分別為工件3的第二個(gè)工序和工件1的第一個(gè)和第二個(gè)工序。

Child 2:[_,_,_,3,1,1,_,_,_]，即：繼承的工序分別為工件3第一個(gè)工序，工件2第二個(gè)工序和工件1第三個(gè)工序。

為了獲得Child 1染色體的其它工序項(xiàng)：

(1)先我們以Father 2為模板從第二個(gè)隨機(jī)數(shù)5所在的位置后面開始循環(huán)構(gòu)造一個(gè)新的染色體序列：(2 3 3///2 1 1 3 2 1)。

(2)我們將已經(jīng)從Father 1中繼承的工件序列從新產(chǎn)生的染色體序列中移除(即：工件3的第二個(gè)工序和工件1的第一個(gè)和第二個(gè)工序)：由(2 3 X 2 X X 3 2 1)獲得(2 3 2 3 2 1)。

(3)填充Child 1剩余部分 ：首先從第二個(gè)隨機(jī)數(shù)所代表的位置后面開始填充得到[_, _ , _ , 3, 1, 1, 2, 3 , 2]，然后循環(huán)填充得到最終序列[3, 2, 1, 3, 1, 1, 2, 3, 2]。

同理可求得Child 2的其它工序項(xiàng)。順序交叉算子的具體用法如圖3所示。

圖3　順序交叉算子示例

3.8停止條件

遺傳算法運(yùn)行到最短的總調(diào)度時(shí)間達(dá)到給定下限或者迭代次數(shù)達(dá)到2000次。

4實(shí)驗(yàn)結(jié)果

本文的計(jì)算實(shí)驗(yàn)用MyEclipse 10完成，所用CPU為2.6GHz的Core i5處理器，內(nèi)存大小為4G。為了評(píng)估遺傳算法的性能，筆者使用了Muth & Thomson和Lawrence設(shè)計(jì)共11種不同規(guī)格標(biāo)準(zhǔn)測(cè)試用例來進(jìn)行計(jì)算實(shí)驗(yàn)，工件的數(shù)目為6到30不等，機(jī)器的數(shù)目為5到15不等。如表1所示，本文比較了遺傳算法、模擬退火算法和禁忌搜索算法的性能。本文所使用的遺傳算法的參數(shù)為：交叉率：0.95，變異率：0.02，群體規(guī)模為200，迭代次數(shù)為2000。

表1　遺傳算法與文獻(xiàn)[10-11]中的比較結(jié)果

通過對(duì)比，由表1中的數(shù)據(jù)不難得出結(jié)論：本文的遺傳算法和文獻(xiàn)[10-11]中的算法性能相當(dāng)，幾乎每個(gè)標(biāo)準(zhǔn)測(cè)試用例都能達(dá)到或接近于最優(yōu)解?？紤]到圖片中文字的可讀性，本文以小規(guī)模的作業(yè)調(diào)度問題mt06為例將其最佳調(diào)度以甘特圖的形式展示出來。本文的甘特圖是在mt06調(diào)度數(shù)據(jù)的基礎(chǔ)上繪制的，其具體調(diào)度信息如圖4所示。圖中p(i,j)表示工件j在機(jī)器i上的加工時(shí)間，i表示機(jī)器i，j表示工件j。以機(jī)器M6上加工的第一個(gè)工件為例，比較各個(gè)機(jī)器的加工序列后可知，它屬于工件3的第三道工序，p(6,3)=8表示在機(jī)器號(hào)為6的機(jī)器上加工的工件3所需的時(shí)間為8。

圖4　mt06的一個(gè)最佳調(diào)度(最短的總調(diào)度時(shí)間為55)

5結(jié)論和后期工作

本文針對(duì)流程工業(yè)中的JSP問題，建立了相應(yīng)的數(shù)學(xué)模型，在調(diào)度模型的基礎(chǔ)上應(yīng)用遺傳算法，針對(duì)標(biāo)準(zhǔn)的測(cè)試用例求解車間調(diào)度問題的最優(yōu)調(diào)度方案。大量的計(jì)算實(shí)驗(yàn)表明，在解決車間調(diào)度問題時(shí)本文所采用的遺傳算法所求得的解和文獻(xiàn)[10-11]中的最優(yōu)結(jié)果相比性能優(yōu)異，具有較高的求解質(zhì)量和效率。盡管如此，由于遺傳算法也有其固有的缺點(diǎn)，比如過早收斂和計(jì)算量大等，今后在這些方面仍需改進(jìn)。下一步，我將通過以下三個(gè)方面來研究車間調(diào)度問題：

(1)用一種混合的選擇標(biāo)準(zhǔn)來選擇給定染色體群體中的最好個(gè)體。

(2)選擇關(guān)鍵路徑上的關(guān)鍵機(jī)器加工的工序來對(duì)染色體序列進(jìn)行交叉。

(3)采用混合算法來解決遺傳算法過早收斂和計(jì)算量大的缺陷。

[參考文獻(xiàn)]

[1] N Zribi, A Kamel, P Borne. Minimizing the makespan for the MPM job-shop with availability constraints[J].International Journal of Production Economics, 2008, 112(1):151-160.

[2] Y Mati. Minimizing the makespan in the non-preemptive job-shop scheduling with limited machine availability[J]. Computers & Industrial Engineering, 2010, 59: 537-543.

[3] R Qing-dao-er-ji,Y Wang. A new Hybrid genetic algorithm for job shop scheduling problem[J]. Computer & Operations Research, 2012, 39: 2291-2299.

[4] H C Cheng, T C Chiang, L C Fu. A two-stage hybrid memetic algorithm for multi-objective job shop scheduling[J]. Expert Systems with Applications, 2011, 38: 10983-10998.

[5] Davis L. Adapting operator probabilities in genetic algorithms[C]. Proceedings of the third international conference on Genetic Algorithms, 1989:375-378.

[6] G W Woods. A hybrid genetic algorithm that adapts to binary and real coded operators[J]. 1997.

[7] M Ben Ali, M Sassi, M Gossa, et al.Simultaneous scheduling of production and maintenance tasks in the job shop[J]. International Journal of Production Research, 2011, 49(13): 3891-3918.

[8] Mattfeld D C. Evolutionary search and the job shop[J]. Investigations on genetic algorithms for production scheduling, 1995.

[9] 安晶,秦珂. 一種基于遺傳算法的車間調(diào)度算法求解[J]. 鹽城工學(xué)院學(xué)報(bào),2007,20(1):33-36.

[11]Dell A M,Trubian M. Applying Tabu Search to the Job Shop Scheduling Problems[J]. Annual Operations Research, 1993, 40:231-252.

[12] 姜迪剛,葉尚輝. 基于遺傳算法的車間作業(yè)調(diào)度[J]. 西安電子科技大學(xué)學(xué)報(bào),2001,28(2):207-210.

(編輯趙蓉)

Multiobjective Genetic Algorithm-Based Method for Job Shop Scheduling Problem

ZHANG Teng-fei1,2, MA Yue2,HU Yi2,3, AN Tao1,2, WANG Shuai1,2,GUO An1,2

(1. Chinese Academy of Sciences, Beijing 100049, China;2. Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110004, China)

Abstract：In this paper we consider a multiobjective job shop scheduling problem (JSP). In JSP we consider m machines on a production line with n defined jobs, each job consists of different tasks for different machines and each of them has its own duration. The goal is to find the shortest scheduling in which none of the jobs' tasks collide on all of the m machines. This part uses the Genetic Algorithm to find the optimal solution for the job scheduling problem. Performance of the proposed heuristic is evaluated through computational experiments on 11 different sizes benchmarks. The result of the test shows the efficiency of search is increased and the convergence is improved in shop scheduling with the Genetic Algorithm.

Key words：scheduling; job shop; genetic algorithms; heuristic; multiobjective

文章編號(hào)：1001-2265(2016)05-0043-03

DOI:10.13462/j.cnki.mmtamt.2016.05.012

收稿日期：2015-06-09

*基金項(xiàng)目：“高檔數(shù)控機(jī)床與基礎(chǔ)制造裝備”國(guó)家科技重大專項(xiàng):基于二次開發(fā)平臺(tái)的專用數(shù)控系統(tǒng)開發(fā)與應(yīng)用(2013ZX04007-011)

作者簡(jiǎn)介：張騰飛(1989—)，男，河南商丘人，中國(guó)科學(xué)院大學(xué)、中科院沈陽計(jì)算技術(shù)研究所碩士研究生，研究方向?yàn)閷?shí)時(shí)系統(tǒng)與數(shù)控技術(shù)，(E-mail)mnmlist@163.com；馬躍(1960—)，男，中科院沈陽計(jì)算技術(shù)研究所博士生導(dǎo)師，研究員，研究方向?yàn)閿?shù)據(jù)挖掘、信息系統(tǒng)。

中圖分類號(hào)：TH165；TG506

文獻(xiàn)標(biāo)識(shí)碼：A