余鵬飛，袁逸萍，李曉娟

(新疆大學 機械工程學院，烏魯木齊 830047)

基于混合遺傳算法的多目標柔性作業(yè)車間調度問題研究*

余鵬飛，袁逸萍，李曉娟

(新疆大學 機械工程學院，烏魯木齊 830047)

針對柔性作業(yè)車間調度問題，提出一種改進的遺傳算法，該算法考慮車間生產實際，使交貨期短、成本降低、生產效率提高、資源利用率提高等建立多目標優(yōu)化模型。對傳統(tǒng)遺傳算法進行一系列改進，在遺傳算法的基礎上，改進編碼方式和遺傳算子，結合精英保留策略和小生境技術，使算法的收斂性和多樣性進一步優(yōu)化，采用權重系數變化法計算染色體的適應度。仿真分析表明， 提出改進后的混合遺傳算法能有效解決柔性作業(yè)車間多目標調度優(yōu)化問題。

柔性作業(yè)車間；多目標調度；遺傳算法

0 引言

近十年以來，流水車間調度和作業(yè)車間調度得到了較充分的研究，然而對于求解柔性作業(yè)車間fJSSP并設計相應的調度算法的卻不多。一般來說，柔性調度問題本身比那些沒有柔性加工路徑的問題更加復雜；隨著目標的增多，問題的復雜性也會進一步增加。多目標柔性調度是一種具有挑戰(zhàn)性的研究方向，而解決問題的關鍵是如何提高調度方法的效率。

針對柔性作業(yè)車間的調度問題，文獻[1-2]提出了基于模糊邏輯和混合算法混合的基礎上的Pareto方法以解決fJSSP，該算法利用了模糊邏輯的的知識表達能力和混合算法的自適應能力；文獻[3-4]給出了基于GA和移動瓶頸法的混合算法，該算法使用雙向量表示方法、先進交叉算子和變異算子以適應染色體的特殊結構和問題的特征；文獻[5]開發(fā)了一種仿真模型，并使用ACO和局部搜索對模型進行改進；文獻[6]采用集成免疫算法和GA的多目標免疫遺傳算法求解柔性調度問題，并分析了算法的收斂性。文獻[7]利用GA逼近目標函數為最大加工完成時間和最大延遲時間的問題Pareto最優(yōu)前端。文獻[8]利用GP優(yōu)化復合調度規(guī)則的參數和算子空間。以上方法多為單目標柔性作業(yè)車間優(yōu)化問題，而多目標優(yōu)化的相關文獻卻不是很多，筆者提出多目標柔性作業(yè)車間優(yōu)化模型，基于混合遺傳算法提出一種新的多目標優(yōu)化方法。

1 問題描述

有n個工件在m臺機器上加工，工件集合為J{Ji|i=1,2,…,N}，工件Ji包含hi道工序，一道工序可由多臺機器加工，MSij為Ji工件在工序hi的可用機器集合，MSij?{1,2,…,m},oijk為i工件的j道工序在機器Mk上進行加工，pijk為i工件的j道工序的加工所需時間，1≤i≤n,1≤j≤hi,1≤k≤m。

fJSSP包含以下兩個問題：確定各工序所對應的機器使得總的加工時間最合理；在給定的約束條件下， 完成加工任務使目標函數最優(yōu)。通過表格實例來描述fJSSP，pijk為表格中的數字，“-”代表oij不能在Mk上進行加工。表1描述了一個3×4 fJSSP。

表1 3×4 fJSSP描述

為了簡化問題，作如下假設：①所有機器在t=0時刻都在用；②所有工件在t=0時刻都可被加工；③所有工件的工藝計劃都是固定不變的；④在每一臺機器上加工的每一道工序的時間是確定的；⑤同一時間，每臺機器只能加工一道工序；⑥加工是非搶占式的。

分析fJSSP模型，將該種問題分為兩類：

(1)完全fJSSP：對于oij，若|MSij|=m，即任意工件Ji的工序可在所有的機器上加工。

(2)部分fJSSP：對于oij，若|MSij|

多目標優(yōu)化模型建立應該符合企業(yè)生產實際，使交貨期短、成本降低、生產效率提高、資源利用率提高等，為此從上面四個方面建立優(yōu)化目標。

(1)

(2)

(3)

(4)

(5)

(6)

約束條件：

(7)

(8)

pjik≥0,pjok=0

(9)

STijk≥0,STiok=0

(10)

STij≥0,STio=0

(11)

(12)

(13)

2 基于改進混合遺傳算法的多目標優(yōu)化方法

柔性作業(yè)車間多目標優(yōu)化方法通常有三類，即Pareto優(yōu)化方法、加權優(yōu)化法和交互優(yōu)化方法。本文采用Pareto最優(yōu)解的思想，基于遺傳算法提出多目標柔性作業(yè)車間的優(yōu)化算法?；旌纤惴ǖ乃悸肥?，在遺傳算法的基礎上，結合精英保留策略和小生境技術，對遺傳算法進行改進，使算法的收斂性和多樣性在理想值。具體的流程圖如圖1所示。

圖1 多目標柔性作業(yè)車間的優(yōu)化算法流程圖

(1)編碼和解碼

fJSSP優(yōu)化采用基于工序的編碼方式，每個染色體用n×max{hj}個自然數組成，其中各工件均出現max{hj}次。如上述3×4 fJSSP例子，染色體的實例為2 1 1 1 1 1 3 3 3。

對此本文采用間隙擠壓法產生活動調度。首先給出兩個定義。

定義1：機器順序JM。JM(i,j)表示加工工件Ji的第j道工序的機器號，JM(i,.)表示工件Ji的所有工序按優(yōu)先順序加工的各機器號的排列。在fJSSP中，任意工件Ji的第j道工序的可用機器不止一個，所以該排列的長度等于(maxhj)×m(j=1,2,…,n)，每道工序的可用機器集用m個機器號表示，稱為一個子片段。部分fJSSP中部分機器不可用時，用0補齊m個子片段(機器編號從1開始)。當各個工件的總的工序的數值不相等時，將該工件的最大工序數作為片段數，而對于那些工件的工序數值比最大工序值小的工件，按照以上規(guī)則排列出機器序號，接著補齊數全為0的(maxhj)-hj個片段，從而構成(maxhj)×m×n的二維矩陣。對于前面描述的3×4 fJSSP例子：

(14)

定義2：加工時間矩陣T。T(i,j)為工件Ji在機器Mi上的加工時間。對于fJSSP，T(i,j)與JM(i,j)一一對應，當JM(i,j)為0時，T(i,j)也為0。描述的3×4fJSSP例子的加工時間矩陣為：

(15)

間隙擠壓法的解碼算法如下：

令k[i]=1,2,…,n；

Fori=1 ton×max{hi}

得到加工工件Ji的機器號JM(i,k[i])；

令k[i]=k[i]+1；

把Ji工件在機器JM(i,k[i]-1)的工序以最早允許時間加工。從剛開始加工到當前時刻，對各個機器有加工空閑的進行判斷，看是否能將該工件插入加工。判斷能夠插入，在對應的加工空閑的機器中將工件插入加工，并且將機器上的加工隊列重寫。若不能插入加工，則將此工件排在該機器的隊尾進行加工。

End for

算法中，工件Ji能在機器空閑時間段[t1,t2]插入加工的條件為：

max(t(i),t1)+pti≤t2

(16)

其中，時間t(i)為Ji工件能夠加工的最早時間；pti是該工件在機器上加工當前工序的時間。按照這種解碼方法，使得那些在某些時間段空閑的的機器繼續(xù)工作，各個機器上的加工任務安排的緊湊，總的加工時間也得到縮短。

(2)適應度計算

適應度計算其實就是目標函數的不斷優(yōu)化問題。對目標函數的優(yōu)化，本文權重系數變化法計算個體的適應度：對于每代個體，在該個體的各個目標按照一定的比例給予不同的權值，將各個目標相加得到該個體的適應度。計算公式如下：

(17)

(3)遺傳操作

采用輪盤賭的選擇方法。在遺傳操作中，因為交叉操作和變異操作致使優(yōu)秀個體丟失，所以我們使適應度高的優(yōu)秀個體不參與交叉操作和變異操作，直接跳過這些操作在下一步代替那些較劣的個體。

在Pareto最優(yōu)解的多樣性方面，在遺傳操作過程當中，用小生鏡技術解決適應度很接近的個體。在Hyun[9]基礎上對小生鏡技術進行改進，提高解的多樣性。某個個體所在的小生境域的定義為：把個體作為中心，個體邊界的計算公式見式(18)，遺傳的概率與小生鏡閾的概率有關，密度越大遺傳下去的概率越小。

(18)

式中，maxflt和minflt分別是混合到第t代時第l個目標的最大值和最小值，M為目標個數，N為種群規(guī)模，l=1,2,…,M。

仿真分析表明，發(fā)現邊界條件不精確，可能造成最優(yōu)解的丟失，因此不斷進行仿真實驗，對邊界條件不斷修正，最終的公式如下：

(19)

采用線性次序交叉方式。采用互換操作變異方法，隨機交換染色體中兩個不同的基因的位置。

3 仿真分析

運行環(huán)境：在處理器為Intel(R)Gore(TM) 2.3GHz、內存為2G的WIN7操作系統(tǒng)下，利用Matlab2012b進行編程。通過與文獻[9]的對比分析得出本文方法的優(yōu)劣。具體比較數據如表2所示。

表2 8*8問題不同調度方法的比較

從表2可以看出，本文方法的最小制造周期比表中其它方法降低了，總的負荷優(yōu)化不是很大，但是最大負荷相比其它方法降低了，總體來說算法的性能得到了提高。因此，本文的算法對解決多目標柔性作業(yè)車間的調度問題有所改進。下面通過一個具體的例子來分析本文方法的可行性和合理性。

采集某作業(yè)車間的生產數據并進行處理，已知有該車間有6臺機器加工6個工件，每個工件具有10道工序的fJSSP，并對其進行仿真實驗?；旌螱A的參數：種群大小N=100，交叉概率pc=0.6，變異概率pm=0.1，最大代次數為3000。調度問題的原始數據和已知參數見文獻[9]，已知參數如表2，為了簡化，所有ηij均取0.001。對這6個目標同時進行優(yōu)化，Pareto方法得出的解在空間形成一個超曲面，解集通常不能用表直接表示，因此，我們近似Pareto解集，得到20個Pareto最優(yōu)解，如表3所示。

表3 近似Pareto解集

續(xù)表

從表3可以看出，近似Pareto解集包含多組最優(yōu)解，決策者可以結合車間具體的生產實際選擇最優(yōu)解。

4 結束語

基于混合遺傳算法的多目標柔性作業(yè)車間調度相對于傳統(tǒng)作業(yè)車間調度問題更符合車間生產實際，具有更大優(yōu)勢，為柔性作業(yè)車間的調度提供了理論指導和依據。本文對遺傳算法進行了一系列的改進，包括遺傳操作以及用小生鏡技術提高解的多樣性等。通過與其它方法進行對比分析，證明本文提出基于混合遺傳算法的多目標柔性作業(yè)車間調度方法對柔性作業(yè)車間調度問題進行優(yōu)化求解時的合理性與正確性，最后仿真實例驗證了算法的有效性。

[1] Kacem I,Hammadi S, Borne P. Approach by localization and multi-objective evolutionary optimization for flexible job shop scheduling problems. IEEE Transactions on Systems, Man and Cybernetics, PART C,2002, 32(1): 1-13.

[2] Kacem I,Hammadi S, Borne P. Pareto-Optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic. Mathematics and Computers in Simulation,2002,60:245-276.

[3] 吳秀麗,孫樹棟,余建軍,等. 多目標柔性作業(yè)車間調度優(yōu)化研究[J]. 計算機集成制造系統(tǒng),2006,12(5):731-736.

[4] Gao J, Gen M, Sun L,et al. A hybrid of genetic algorithm and bottleneck shifting for multi-objective flexible job shop scheduling problems[J]. Computers and Industrial Engineering, 2007,53:149-162.

[5] Xing L N, Chen Y W, Wang K W. Multi-objective flexible job shop schedule: Design and evolution by simulation modeling[J].Applied Soft computation,2009,9:362-367.

[6] Wu X L, Sun S D, Niu G G,et al. The performance analysis of multi-objective immune algorithm for flexible job shop scheduling[J].International Federation for Information Processing,2006,25(12):1480-1483.

[7] Vicot G, Billaut J C, Esswein C. A genetic algorithm for a bicriteria flexible job shop scheduling problem[C]. 2006 International Conference on Service Systems&Service Manage-ment,2006:1240-1244.

[8] Tay J C, Ho N B. Evolution dispatching rules using genetic programming for solving multi-objective flexible job shop problems[J].Computers and Industrial Engineering, 2008,54(3):453-473.

[9] HYUN CJ，KIM Y，K1M Y K．A genetic algorithm for multiple objective sequencing problems in mixed model assembly Lines[J]．computers & operations Research，1998，25(7):675-690.

(編輯李秀敏)

ResearchofMulti-objectiveFlexibleJobShopSchedulingProblemBasedonHybridGeneticAlgorithm

YU Peng-fei, YUAN Yi-ping, LI Xiao-juan

(School of Mechanical Engineering ,Xinjiang University, Urumqi 830047,China)

Aiming at flexible job-shop scheduling problem, an improved genetic algorithm was proposed and the algorithm considering actual production in workshop and make delivery time short, reduce cost, improve efficiency and optimizing resource utilization multi-objective optimization model is established. A series of improvements on traditional genetic algorithm on the basis of genetic algorithm, improve the methods of coding and genetic operators, combined with elite reserved strategy and niche technology, make the algorithm convergence and the diversity of further optimization, the variation weight coefficient method to calculate the fitness of chromosomes. The simulation analysis shows that the proposed hybrid genetic algorithm can effectively solve the flexible job shop multi-objective scheduling optimization problem.

flexible job shop; multi-objective scheduling; genetic algorithm

TH186；TG506

：A

1001-2265(2017)09-0157-04

10.13462/j.cnki.mmtamt.2017.09.041

2016-12-09；

：2016-12-21

國家自然科學基金(51365054)；新疆維吾爾自治區(qū)自然科學基金(2014211A008)

余鵬飛(1991—)，男，河南信陽人，新疆大學碩士研究生，研究方向為工業(yè)工程，(E-mail)1512994226@qq.com。