林飛龍，陶 澤，王曉晨

(1.沈陽理工大學 機械工程學院，沈陽 110159；2.大連海事大學 航運經(jīng)濟與管理學院，遼寧 大連 116026)

近年來，越來越多的學者開始進行調度問題的研究[1]。國內外對于車間調度優(yōu)化問題也提出了較多的解決方案[2-5]。企業(yè)為提高生產(chǎn)效率、增加收益，優(yōu)化車間調度無疑是最好的方法之一。車間調度問題目前已被證明是NP-complete問題[6]，在實際研究過程中需要考慮很多因素，所以至今為止仍沒有形成一套完整系統(tǒng)的理論。

杜利珍等基于果蠅優(yōu)化算法求解不相關并行機混合流水車間調度問題，并采用標桿實例進行仿真實驗，驗證了算法的有效性[7]。陶澤等提出小生境遺傳算法解決雙目標混合流水車間調度問題，并通過仿真實驗得出最優(yōu)方案[8]。Fernandez-Viagas V等針對解決混合流水車間調度問題，比較了20種啟發(fā)式算法，并提出了兩種基于記憶的構造性啟發(fā)式算法來求解置換flowshop調度問題[9]。Zhong W等研究了兩階段無等待混合流水車間環(huán)境下調度算法的性能，該環(huán)境具有階段間靈活性，每個階段有多臺并行機[10]。本文對具有并行機的混合流水車間進行研究，并與EDA[11]遺傳算法和SFLA[12]遺傳算法進行對比分析，進一步驗證本文算法的有效性和魯棒性。

1 問題描述

相對于流水車間(FSP)調度問題，混合流水車間(HFSP)調度不僅要解決工件的加工順序且要解決并行機的分配問題。HFSP調度可描述為：n個工件在M臺機器上進行加工，如圖1所示。各個工件的加工順序相同，至少有一道工序存在并行機，需要確定工件在哪臺機器上加工能夠使加工時間最短。

圖1 Flow Shop調度的結構

構建具有并行機的混合流水車間調度的數(shù)學模型，主要包括工件約束、加工設備能力約束、工藝順序約束，計算原理如下所示。

xi1為0-1變量(若工件i被安排在第1個位置則取值為1，否則取值為0)；

yijk也為0-1變量(若工件i的第j道工序被安排在第k臺機器上取值為1，否則取值為0)；

sij表示工件i的第j道工序的開始加工時間；

eij則表示工件i的第j道工序的完成時間。

eij=sij+tij,i=1,2;j=1,2,

eijsi(j+1),i=1，2；j=1,2,

j=1，2，…，m

2 遺傳算法求解

由于混合流水車間調度問題已經(jīng)被證明是NP完全問題，所以本文將基于遺傳算法對HFSP調度問題展開研究。應用遺傳算法求解的一般流程如圖2所示。

圖2 遺傳算法的流程圖

2.1 編碼方法

混合流水車間的編碼方式采用基于工件的編碼方式。例如用vk=[1，2，3]來表示第k個染色體，工件的加工順序為：J1、J2、J3。本文討論的HFSP調度問題，每一加工工序上并行機的加工性能不同，即同一工件在同一工序不同機器上的加工時間不同。

解碼規(guī)則是依據(jù)最小化完工時間，通過計算若在閑置機器M1上加工的完工時間小于工件在正在工作的并行機所需的加工時間與等待時間之和，則在M1上進行加工，反之工件在M2上進行加工，具體示例如下所示。

假定現(xiàn)有3個工件J1、J2、J3依次三道工序進行加工，機器的編碼以及并行機的分布情況如圖3所示，工件在各個機器上的加工時間為：M1(2，5，3)、M2(5，4，2)、(6，2，5)、M4(2，1，3)。隨機產(chǎn)生的染色體為{1,3,2}。

圖3 FSP調度的機器編號

(1)工序1：T(1，1)=2，T(3，1)=3，T(2，1)=5。

(2)工序2：T(1，2)=5，T(3，2)=2，T(2，2′)=2；T(1，2)+T(1，1)=7；T(1，1)+T(1，2)+T(3，2)=9；T(1，1)+T(3，1)+T(2，1)+T(2，2′)=12。

(3)工序3：T(1，3)=2，T(3，3)=3，T(2，3)=1；T(1，2)+T(1，1)+T(1，3)=9；T(1，1)+T(1，2)+T(3，2)+T(3，3)=12；T(1，1)+T(3，1)+T(2，1)+T(2，2′)+T(2，3)=13。

2.2 初始種群

初始種群通過計算機隨機產(chǎn)生。然后按照一定的方法選擇相對較優(yōu)的個體作為子代，淘汰適應度值相對較低的個體，保證方案向著最優(yōu)轉化。

2.3 適應度函數(shù)

用Cmax表示第k個染色體的最大完工時間，那么適應度函數(shù)為

F(k)=1/Cmax

2.4 遺傳算子的設計

(1)選擇算子

按每個個體的適應度函數(shù)值大小排名，選出較好的染色體個體，淘汰排名靠后的個體。

(2)交叉算子

首先選取父代染色體1和2，隨機產(chǎn)生一個與染色體長度相同的向量，由數(shù)字1、2組成。向量定義了由父代1、2中選取基因的順序，從向量所指定的父代中選取基因并從另一個父代中消除對應的基因，重復該步驟，直到兩父代染色體為空且子代包含所有染色體為止。如父代1表示加工工件的數(shù)目為10個，且加工時優(yōu)先考慮加工工件的順序為J1、J2、J4、J6、J8、J7、J5、J3、J0、J9。隨機產(chǎn)生一個與染色體長度相同的向量，由數(shù)字1、2組成。

父代1：1 2 4 6 8 7 5 3 0 9；

父代2：1 0 2 4 6 3 9 7 5 8。

隨機產(chǎn)生的數(shù)字：1 1 2 1 2 2 1 1 2 2。

交叉結果：

子代1：1 2 0 4 6 3 8 7 9 5；

子代2：1 0 2 4 6 8 3 5 7 9。

(3)變異算子

遺傳算法中的變異運算，是指將個體染色體編碼串中的某些基因用該基因座的其他等位基因來替換，從而形成一個新的個體。本文使用逆序變異算子，如下例所示。

染色體：1 2 04 6 3 87 9 5；

變異后：1 2 08 3 6 47 9 5。

(4)終止條件

取總的繁衍代數(shù)為終止條件。

3 仿真實驗及結果分析

3.1 仿真案例1

為驗證算法的可行性，本文將應用Matlab對HFSP調度進行實例分析?，F(xiàn)有10個工件要一次經(jīng)過9道工序進行加工，其中第8道工序上有兩臺機器，且其加工性能不完全相同。

設個體數(shù)目NIND=40，交叉概率為XOVR=0.8，變異率為MUTR=0.01。最大遺傳代數(shù)GENmax=200。

這里用矩陣R表示各工件在各個工序上的加工時間。矩陣的每一行表示工件J1、J2、J3、J4、J5、J6、J7、J8、J9、J10在機器M0、M1、M2、M3、M4、M5、M6、M7、M8、M9上的加工時間。

3.1.1穩(wěn)定性分析

本次實施的程序，本文通過應用軟件進行50次模擬仿真，對比所得數(shù)據(jù)，進行軟件穩(wěn)定性分析。所得數(shù)據(jù)如表1所示。

表1 仿真結果 min

由表1可以看出，程序穩(wěn)定性良好，其中非最優(yōu)解115與最優(yōu)解的誤差為0.88%，且在50次仿真中只出現(xiàn)3次，而非最優(yōu)解117的誤差為2.63%，但在50次仿真中只出現(xiàn)1次，故認為程序誤差在可接受范圍內。

3.1.2改變運行參數(shù)

在其他參數(shù)不變的情況下，對交叉概率為XOVR=0.8、XOVR=0.7、XOVR=0.6分別各自進行10次仿真模擬，比較得出較優(yōu)調度方案。

(1)交叉概率XOVR=0.8時，應用Matlab仿真10次結果如表2所示。

表2 XOVR=0.8時的最大完工時間 min

(2)交叉概率XOVR=0.7時，應用Matlab仿真10次結果如表3所示。

表3 XOVR=0.7時的最大完工時間 min

(3)交叉概率XOVR=0.6時，應用Matlab仿真10次結果如表4所示。

表4 XOVR=0.6時的最大完工時間 min

從表2、表3、表4不難看出，當交叉概率XOVR=0.8時，出現(xiàn)了相對較優(yōu)的結果128min。

當交叉概率XOVR=0.85時，出現(xiàn)的最優(yōu)結果仍為128min，但其對系統(tǒng)運行效率影響如表5所示。

表5 改變XOVR對系統(tǒng)運行效率的影響

由此可見XOVR取0.8更優(yōu)。

按照上述方法改變最大遺傳代數(shù)和個體數(shù)目，最終得出相對較優(yōu)方案為：交叉率XOVR=0.8，最大遺傳代數(shù)GENmax=200，個體數(shù)目NIND=50。

3.1.3運行結果

程序仿真模擬的結果通過甘特圖和進化曲線表示，如圖4、圖5所示。

3.1.4結果分析

本次仿真設定的最大遺傳代數(shù)為200，即迭代次數(shù)為200次。圖4直觀的體現(xiàn)了每臺機器上工件的加工順序，valmin=114min。其中每臺機器加工工件的順序并不完全相同，第一臺機器上工件的加工順序即按照隨機產(chǎn)生的染色體決定工件的加工順序，根據(jù)所設定的加工時間矩陣R，程序將基于加工周期最小的原則，重新考慮每臺機器上工件的加工順序，但必須保證工件經(jīng)過每道工序的時間在上一工序之后，即保證每一工件的加工順序完全相同，符合流水加工的特點。

圖4 Matlab仿真甘特圖

圖5直觀的體現(xiàn)了在迭代過程中每次迭代產(chǎn)生的最優(yōu)解的變化以及種群均值的變化，其中種群均值即種群中每一染色體的解求平均值。曲線的起點表示隨機產(chǎn)生的初始種群中的最優(yōu)解，即初始種群中的最佳調度方案。由于初始種群為隨機產(chǎn)生，故導致最優(yōu)解與最差解差異較大，體現(xiàn)在初始階段兩條曲線相差較大，隨著遺傳代數(shù)的增加，種群中的個體逐漸趨于最優(yōu)化，圖5中的兩條曲線逐漸趨于重合。

圖5 Matlab仿真進化曲線

3.2 仿真案例2

為進一步驗證本文算法的有效性和魯棒性，對文獻[11]中的案例進行仿真并與EDA算法和SFLA算法所得的結果進行對比分析，調度結果如表6所示。種群數(shù)目NIND=40，交叉概率為XOVR=0.8，變異率為MUTR=0.01。最大遺傳代數(shù)GENmax=200。

表6 調度結果對比分析

表6表明本文算法取得的最優(yōu)解優(yōu)于SFLA方法，運行10次，其中所得解60%優(yōu)于SFLA所得解；與EDA方法取得的最優(yōu)解相同，且兩者都具有較好的魯棒性，表明本文所提出的方法確實有效可行。

4 結論

提出基于遺傳算法研究具有并行機的混合流水車間的調度問題，解決了混合流水車間n個工件在每臺機器上的加工順序以及工件在并行機上的分配問題。通過Matlab進行仿真模擬所得的甘特圖給出最終的調度方案。結果表明，基于遺傳算法應用Matlab進行仿真模擬，對混合流水車間的調度問題進行優(yōu)化，可以很快得出最優(yōu)解或近似最優(yōu)解，且易于實現(xiàn)。