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

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

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

?

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

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

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

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

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

0引言

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

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

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

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表示完成所有工件加工后的最大完工時間，pij來表示工件j在機器i上的加工時間，tij表示工件j在機器i上的開始加工時間，N表示操作(i,j)的集合，A表示所有所有的工件j在機器k上加工前必須在機器i上加工操作依賴關(guān)系對(i,j)→(k,j)的集合。

2遺傳算法簡介

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

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

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

3.1問題建模

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

3.2編碼

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

3.3解碼

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

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

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

3.4初始化種群

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

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

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

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

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

3.6選擇

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

3.7交叉和變異

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

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

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

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

3.7.2順序交叉算子

對于一個n個工件×m臺機器的車間調(diào)度問題，首先產(chǎn)生范圍在[1,n×m]的兩個隨機數(shù)且第一個隨機數(shù)小于第二個隨機數(shù)，n×m是染色體編碼序列的長度，產(chǎn)生的兩個隨機樹代表父代染色體的要遺傳給子代染色體的染色體序列的起始和結(jié)束位置，在本例中的兩個隨機數(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的第二個工序和工件1的第一個和第二個工序。

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

為了獲得Child 1染色體的其它工序項：

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

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

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

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

圖3　順序交叉算子示例

3.8停止條件

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

4實驗結(jié)果

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

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

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

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

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

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

(1)用一種混合的選擇標準來選擇給定染色體群體中的最好個體。

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

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

[參考文獻]

[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]. 鹽城工學院學報,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]. 西安電子科技大學學報,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

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

DOI:10.13462/j.cnki.mmtamt.2016.05.012

收稿日期：2015-06-09

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

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

中圖分類號：TH165；TG506

文獻標識碼：A