一種求解等效并行機(jī)調(diào)度問題的改進(jìn)遺傳算法

劉 宇，吳杰程，錢晨紅，潘厲冰

(溫州大學(xué) 機(jī)電工程學(xué)院，浙江 溫州325035)

并行機(jī)生產(chǎn)是目前工業(yè)上普遍采用的一種生產(chǎn)方式，如LED半導(dǎo)體晶粒揀選工藝[1]等。并行機(jī)調(diào)度是車間生產(chǎn)調(diào)度中的一個重要問題。關(guān)于并行機(jī)調(diào)度問題的研究，通常需假設(shè)所有并行機(jī)在調(diào)度過程中持續(xù)可用，但實(shí)際調(diào)度生產(chǎn)過程經(jīng)常會出現(xiàn)由機(jī)器故障或長時間運(yùn)行損耗等導(dǎo)致的停機(jī)問題，因此必須進(jìn)行預(yù)防性維修來保障正常生產(chǎn)過程[2]。此外，在精益生產(chǎn)和無庫存生產(chǎn)方式下，工件通常不都是同一時刻到達(dá)而是在計劃范圍內(nèi)隨機(jī)到達(dá)的。因此，安排生產(chǎn)計劃時應(yīng)考慮工件到達(dá)時間的約束。

對于預(yù)防性維修的并行機(jī)調(diào)度問題，已有不少學(xué)者進(jìn)行了研究，如：劉民等提出一種解決較大規(guī)模并行機(jī)調(diào)度問題的遺傳算法[3]；常俊林等針對并行多機(jī)調(diào)度問題，基于遺傳算法的搜索能力提出一種能改善求解質(zhì)量的混合啟發(fā)式算法[4]；金壽松等采用兩段染色體編碼方式，對種群的初始化過程進(jìn)行優(yōu)化，并結(jié)合自適應(yīng)算子改進(jìn)了遺傳算法[5]；江才林等針對考慮周期預(yù)防性維護(hù)的異速并行機(jī)系統(tǒng)，提出了一種混合遺傳算法[6]；蔣凱麗等針對具有時間窗的預(yù)防性維護(hù)并行機(jī)下的混合流水線系統(tǒng)，提出了一種構(gòu)造式算法[7]。分析有關(guān)文獻(xiàn)可知，對于同時考慮預(yù)防性維修和工件到達(dá)時間的等效并行機(jī)調(diào)度問題，用傳統(tǒng)遺傳算法求解可以獲得不錯的結(jié)果，但存在種群中個體多樣性不強(qiáng)、易陷入局部最優(yōu)等問題。為此，本文提出一種基于自適應(yīng)交叉變異概率以及災(zāi)變機(jī)制的改進(jìn)遺傳算法。

1 并行機(jī)調(diào)度問題

并行機(jī)調(diào)度問題可描述為：將n個工件安排在m臺并行機(jī)中的一臺機(jī)器上加工，實(shí)現(xiàn)預(yù)期目標(biāo)的最優(yōu)。

1.1 并行機(jī)調(diào)度的五要素

(1) 待加工工件集。設(shè)J={J1,J2,…,Jn}是一組數(shù)量為n的不可中斷加工工件。Jj表示第j(j=1,2,…,n)個工件。其中工件Jj的加工時間為p[j]，工件Jj的到達(dá)時間為r[j]，且每個工件到達(dá)的時間是動態(tài)的。

(2) 加工機(jī)器集。設(shè)M={M1,M2,…,Mm}是m臺機(jī)器的集合。

(3) 預(yù)防性維修(Preventive Maintenance,PM)。機(jī)器需要進(jìn)行彈性的PM，以保證機(jī)器能正常生產(chǎn)。本文考慮的預(yù)防性維修均為彈性維修形式，即連續(xù)加工工件時間或者機(jī)器的使用時限不能超過維修時間的門檻(即維護(hù)門檻)Tu，且機(jī)器上工件Jj的加工時間不超過維護(hù)門檻，即p[j]≤Tu。維護(hù)作業(yè)所需時間(即維修時間)固定為t。

(4) 約束條件。①加工過程中不允許搶占工件，也不允許中斷工件供應(yīng)；②每臺機(jī)器在同一時刻只能加工一個工件，且每個工件在同一時刻只能在一臺機(jī)器上加工；③工件之間沒有加工優(yōu)先級之別；④每個工件都有自己的到達(dá)時間；⑤工件Jj的到達(dá)時間r[j]和加工時間p[j]都是預(yù)先給定的；⑥機(jī)器的維修門檻Tu和維修時間t都是預(yù)先給定的；⑦同一工件在任一臺機(jī)器上的加工時間相同。

(5) 調(diào)度目標(biāo)。調(diào)度目標(biāo)是最大完工時間的最小化。

1.2 并行機(jī)調(diào)度問題的甘特圖

根據(jù)調(diào)度問題的三域表示法[8]，可將考慮PM與工件到達(dá)時間約束，以最小化完工時間為目標(biāo)的調(diào)度問題標(biāo)記為Pm/r[j],FPM/Cmax。圖1所示為考慮PM和工件到達(dá)時間約束的多臺等效并行機(jī)單目標(biāo)調(diào)度問題甘特圖。

圖1 考慮PM和工件到達(dá)時間約束的多臺等效并行機(jī)單目標(biāo)調(diào)度問題甘特圖

考慮PM和工件到達(dá)時間約束的多臺等效并行機(jī)單目標(biāo)調(diào)度問題包括M1，M2，…，Mm機(jī)器上所有工件的排序。Ji[k]表示機(jī)器Mi上第k個位置加工的工件。r[i][k]表示工件Ji[k]的到達(dá)時間，p[i][k]表示工件Ji[k]的加工時間，Ti[a]表示工件Ji[k]的總加工時間。PMia表示對機(jī)器Mi的第a次PM。C[i][nm]表示機(jī)器Mi的完工時間。

2 數(shù)學(xué)規(guī)劃模型

2.1 參數(shù)定義

C[j]：工件Jj的完工時間,j=1,2,…,n。

Ts,[i][k]：機(jī)器Mi上第k個位置的開始加工時間(i=1,2,…,m;k=1,2,…,n-m+1)。

Q[i][k]：機(jī)器Mi上第k個位置的累計加工時間。

Tc,[j][k]：工件Jj在機(jī)器Mi上第k個位置的完工時間。

Cmax：m臺機(jī)器中最大的完工時間。

2.2 決策變量設(shè)置

X[i][j][k]：若工件Jj在第i臺機(jī)器Mi的第k個位置上加工，則為1；否則為0(i=1,2,…,m;j=1,2,…,n;k=1,2,…,n-m+1)。

Y[i][k]：若在機(jī)器Mi的第k個位置加工工件后需要維護(hù)機(jī)器,則為1；否則為0。

2.3 模型構(gòu)建

以最大完工時間最小為目標(biāo)的數(shù)學(xué)模型為：

Min.Cmax

(1)

每臺機(jī)器的每個位置最多加工一個工件，每個工件也必須在一臺機(jī)器的一個位置上加工。由此可列出下列式子：

(2)

每臺機(jī)器的最后一個位置不需要維修。由此可列出下列式子：

Y[i][n-m+1]=0

(3)

機(jī)器Mi第k個位置的開始加工時間與累計到達(dá)時間的關(guān)系為：

(4)

機(jī)器Mi第k個位置的開始加工時間要大于等于上一個工件的完工時間與該位置的PM時間之和。由此可列出下列式子：

Ts,[i][k]≥Tc,[j][k-1]+Y[i][k-1]·t

(5)

機(jī)器Mi第k個位置的完工時間等于該位置的開始加工時間與該位置上工件的加工時間之和。由此可列出下列式子：

(6)

每臺機(jī)器上各位置的累計加工時間為：

(7)

機(jī)器Mi的累計加工時間的約束可表示為：

為盡早安排工件的加工，決策變量應(yīng)滿足下列條件：

(9)

工件Jj完工時間的約束可表示為：

(10)

最大完工時間可表示為：

Cmax≥C[j]

(11)

3 改進(jìn)遺傳算法

為解決考慮預(yù)防性維修的并行多機(jī)調(diào)度問題，這里給出了圖2所示基于災(zāi)變機(jī)制的改進(jìn)遺傳算法流程。相比傳統(tǒng)遺傳算法，本文提出的算法采用隨機(jī)與啟發(fā)式混合方法生成初始種群，設(shè)計了自適應(yīng)交叉概率、變異概率和災(zāi)變算子。

圖2 基于災(zāi)變機(jī)制的改進(jìn)遺傳算法流程

3.1 設(shè)計編碼并生成初始種群

編碼方式采用自然數(shù)編碼，1～n表示工件號，用0區(qū)別兩臺機(jī)器，兩個0之間的數(shù)表示在一臺機(jī)器上加工的工件序號。

Pm/r[j],FPM/Cmax問題具有下列性質(zhì)：若每臺機(jī)器的完工時間趨于一致，則最大完工時間趨于最??；在機(jī)器都空閑的情況下，到達(dá)時間早的工件先加工；在已經(jīng)確定每臺機(jī)器加工工件順序的情況下，最優(yōu)解一定是耗費(fèi)時間最少的[8]。根據(jù)文獻(xiàn)[9],若能盡量使機(jī)器滿載，則最大完工時間趨于最優(yōu)。

為確保初始種群的質(zhì)量和多樣性，本文利用啟發(fā)式算法生成80%的初始種群，讓剩余的20%種群隨機(jī)生成。

按啟發(fā)式算法生成較優(yōu)初始種群的具體步驟有6個。

(1) 根據(jù)工件Jj到達(dá)時間r[j]從小到大的順序，對每個工件的序號進(jìn)行逆排序。如果兩個工件的加工時間相同，則將工件序號小的排在前面；如果兩個工件的到達(dá)時間相同，則將加工時間短的工件排在前面。

(2) 取前m個工件，分別安排在m臺機(jī)器的第一個位置。

(4) 將剩余的n-m個工件隨機(jī)排序并安排加工，若某臺機(jī)器的完工時間超過了S3，就將相應(yīng)的工件安排到下一臺機(jī)器上，以此類推到最后一臺機(jī)器。

(5) 將剩余工件分配結(jié)束，并針對每臺機(jī)器上的工件,根據(jù)r[j]的值從小到大重新排序。

(6) 根據(jù)維護(hù)門檻Tu，對每臺機(jī)器上的工件進(jìn)行滿載調(diào)整。

3.2 計算目標(biāo)函數(shù)適應(yīng)度并進(jìn)行個體的選擇復(fù)制

個體I的適應(yīng)度為：

(12)

式中，Cmax(I)為對應(yīng)個體I的目標(biāo)最大值。

根據(jù)適應(yīng)度大小，采用輪盤賭法[10]選擇個體，并將其復(fù)制到后代種群中。

3.3 自適應(yīng)操作

在文獻(xiàn)[11]的基礎(chǔ)上，本文采用一種能自適應(yīng)調(diào)整交叉概率和變異概率的方法,進(jìn)一步提高遺傳算法的求解速度和收斂速度，以實(shí)現(xiàn)遺傳操作后的種群多樣化。

交叉概率為：

(13)

式中:gmax為后代種群中個體的最大適應(yīng)度；gmin為后代種群中個體的最小適應(yīng)度；g′為遺傳操作中兩個個體中較大的適應(yīng)度；gavg為后代種群中個體的平均適應(yīng)度；k1、k2、k3、k4均為指定系數(shù)，且1>k1>k2>k3>k4>0。

變異概率為：

(14)

式中，1>k5>k6>k7>k8>0。

只要指定kq(q=1,2,3,4,5,6,7,8)的值，就可以實(shí)現(xiàn)交叉概率和變異概率的自適應(yīng)調(diào)整。

3.4 交叉操作

將隨機(jī)選擇的兩條染色體分別作為父代1和父代2，并隨機(jī)采用兩種交叉方法(交叉方法A和交叉方法B)中的一種，進(jìn)行交叉操作，生成兩個子代。

(1) 交叉方法A：在兩個父代P1、P2中各選擇一個基因段，進(jìn)行交換?；蚨蔚奶攸c(diǎn)在于其兩個端點(diǎn)各為兩個相鄰的0。對于較優(yōu)的父代，選擇最大完工時間值最大的一段基因；對于較差的父代，選擇最大完工時間值最小的一段基因。交叉方法A的操作如圖3所示。

圖3 交叉方法A的操作示意圖

(2) 交叉方法B：鑒于工件數(shù)量為n、機(jī)器數(shù)量為m，可從1到n+m+1隨機(jī)生成兩個交叉點(diǎn)，將兩個父代P1，P2各分成3個區(qū)域；從集合{1,2,3}中隨機(jī)生成一個整數(shù)γ。如果γ=1，則交換P1，P2的前段區(qū)域；如果γ=2，則交換P1，P2的中段區(qū)域；如果γ=3，則交換P1，P2的后段區(qū)域。這里給出了γ=2 時交叉方法B的操作示意圖(圖4)。

圖4 γ=2時交叉方法B的操作示意圖

3.5 變異操作

對隨機(jī)選擇的染色體進(jìn)行變異操作時，應(yīng)先后采用兩種變異方法(變異方法A和變異方法B)，進(jìn)行變異操作。

(1) 變異方法A：在前50%代的種群中，隨機(jī)選擇兩個基因，進(jìn)行交換(若取到了0，則需要重新選擇)。變異方法A的操作如圖5所示。

圖5 變異方法A的操作示意圖

(2) 變異方法B：在后50%代的種群中，隨機(jī)選擇一個基因段，并對基因段內(nèi)的排序進(jìn)行倒置處理。變異方法B的操作如圖6所示。

圖6 變異方法B的操作示意圖

3.6 災(zāi)變操作

為避免遺傳種群出現(xiàn)“早熟”，可在傳統(tǒng)遺傳算法中加入災(zāi)變機(jī)制，運(yùn)用災(zāi)變算子進(jìn)行災(zāi)變操作[12]。在多次迭代后，大多數(shù)個體與最優(yōu)個體相似度較高時，應(yīng)進(jìn)行災(zāi)變操作。災(zāi)變操作是指，保存當(dāng)前種群中部分較優(yōu)秀個體而刪除其他個體，并隨機(jī)產(chǎn)生新的個體，對種群進(jìn)行補(bǔ)充，從而提高種群的多樣性[13]。

在災(zāi)變操作時，傳統(tǒng)上要將災(zāi)變規(guī)模設(shè)置成常數(shù)，若迭代后期使用前期的較大災(zāi)變規(guī)模，則會導(dǎo)致求解速度變慢以及最優(yōu)解的質(zhì)量變差。為保障算法的收斂性和最優(yōu)解的質(zhì)量，本文設(shè)置了動態(tài)的自適應(yīng)災(zāi)變規(guī)模(即災(zāi)變算子)，使其能隨著遺傳種群迭代次數(shù)的改變而發(fā)生變化。災(zāi)變算子可表示為：

x=е-μr/Rx1

(15)

式中:μ為控制變量，1>μ>0；R為最大迭代次數(shù)；x1為初始設(shè)置的災(zāi)變規(guī)模。

設(shè)置災(zāi)變計數(shù)h′，用于記錄前一個種群最優(yōu)個體與后一個種群最優(yōu)個體相同時迭代的次數(shù)。如果h′達(dá)到了預(yù)設(shè)的最大災(zāi)變次數(shù)H，則需進(jìn)行災(zāi)變操作并啟用災(zāi)變算子。

災(zāi)變操作的具體步驟為：①針對遺傳種群內(nèi)所有個體，根據(jù)適應(yīng)度從小到大進(jìn)行排序；②計算當(dāng)前種群迭代次數(shù)下的災(zāi)變規(guī)模(即災(zāi)變的個體數(shù))x；③刪除當(dāng)前種群適應(yīng)度較低的前x個個體，而保留其他較優(yōu)秀的個體；④按隨機(jī)規(guī)則產(chǎn)生x個新個體，加入當(dāng)前種群，構(gòu)成災(zāi)變操作后的新種群。

3.7 算法停止

當(dāng)算法滿足迭代次數(shù)為200時，停止算法，得到最終結(jié)果。

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

為了評估數(shù)學(xué)規(guī)劃模型與改進(jìn)遺傳算法的求解效率、最優(yōu)解質(zhì)量，本文進(jìn)行了相應(yīng)的實(shí)驗(yàn)和計算。實(shí)驗(yàn)數(shù)據(jù)包括機(jī)器參數(shù)、工件參數(shù)和PM參數(shù)等。其中：機(jī)器參數(shù)為機(jī)器的數(shù)量m;工件參數(shù)包括工件數(shù)量n、加工時間p[j]、到達(dá)時間r[j]；PM參數(shù)包括維護(hù)門檻Tu和維護(hù)作業(yè)所需時間t；災(zāi)變機(jī)制參數(shù)包括初始設(shè)置的災(zāi)變規(guī)模x1、預(yù)設(shè)的最大災(zāi)變次數(shù)H。

實(shí)驗(yàn)以中小規(guī)模問題為例，工件數(shù)量n設(shè)置了7種，即n={6,7,9,10,11,12,15}；工件加工時間p[j]服從統(tǒng)計分布U[1,10];Tu設(shè)置了3個水平，即Tu={10,15,20}；t設(shè)置2個水平，即t={2,5}。機(jī)器數(shù)量m設(shè)置為3。Tu和t一共產(chǎn)生了6種組合。實(shí)驗(yàn)組合總共有42種，每種組合做10次實(shí)驗(yàn)，結(jié)果取平均值。

初始設(shè)置的災(zāi)變規(guī)模x1為50，預(yù)設(shè)的最大災(zāi)變次數(shù)H為5。k1=0.8,k2=0.6,k3=0.5,k4=0.2,k5=0.1,k6=0.05，k7=0.03，k8=0.01。

本文利用Dev-C++語言編寫改進(jìn)遺傳算法的程序，并在IBM ILOG CPLEX Optimization Studio Ver. 12.7.1平臺上構(gòu)建了數(shù)學(xué)規(guī)劃模型；針對不同工件數(shù)量，采用數(shù)學(xué)規(guī)劃模型、傳統(tǒng)遺傳算法、改進(jìn)遺傳算法，分別求得最優(yōu)解，并統(tǒng)計了運(yùn)算時間。

4.2 結(jié)果分析

采用數(shù)學(xué)規(guī)劃模型、傳統(tǒng)遺傳算法、改進(jìn)遺傳算法求解的結(jié)果和平均運(yùn)算時間分別見表1、表2。表1中偏差程度的計算公式為：

表1 數(shù)學(xué)規(guī)劃模型、傳統(tǒng)遺傳算法和改進(jìn)遺傳算法的求解結(jié)果

表2 數(shù)學(xué)規(guī)劃模型、傳統(tǒng)遺傳算法和改進(jìn)遺傳算法的平均運(yùn)算時間

(16)

由表1可知：對于小規(guī)模問題的求解來說，數(shù)學(xué)規(guī)劃模型具有明顯的優(yōu)勢；從偏差程度來看，本文提出的改進(jìn)遺傳算法求解結(jié)果比傳統(tǒng)遺傳算法穩(wěn)定，且求解質(zhì)量優(yōu)于傳統(tǒng)遺傳算法，具有更好的搜索能力。隨著工件數(shù)量的增大，改進(jìn)遺傳算法相對傳統(tǒng)遺傳算法的優(yōu)勢越來越明顯：當(dāng)工件為6件時，改進(jìn)遺傳算法與傳統(tǒng)遺傳算法的偏差程度都近似于0.00；當(dāng)工件為15件時，對于Tu和t的6種組合來說，傳統(tǒng)遺傳算法的平均偏差程度是改進(jìn)遺傳算法平均偏差程度的21.01倍。

由表2可知，對于小規(guī)模問題的求解來說，數(shù)學(xué)規(guī)劃模型雖可得到最優(yōu)解，但隨著工件數(shù)量的增大，其運(yùn)算時間明顯增加。這是因?yàn)檎{(diào)度問題的可行解空間隨著工件數(shù)量的增大呈指數(shù)型增加，而數(shù)學(xué)規(guī)劃模型的求解需要搜索全部可行解空間，所以運(yùn)算時間會急劇增加。而遺傳算法僅搜索其中一部分解即可，因此效率更高。對于中小規(guī)模問題的求解來說，改進(jìn)遺傳算法的災(zāi)變算子雖然會導(dǎo)致其運(yùn)算時間的增加，但改進(jìn)遺傳算法有更強(qiáng)的限制搜索空間的能力，因此總體上，改進(jìn)遺傳算法比傳統(tǒng)遺傳算法的運(yùn)算效率更高，且隨著工件數(shù)量的增大，兩種算法的平均運(yùn)算時間差異越來越大，從工件為6件的0.39 s增加到了工件為15件的2.30 s。

4.3 改進(jìn)遺傳算法再驗(yàn)證

為進(jìn)一步驗(yàn)證加入災(zāi)變機(jī)制的改進(jìn)遺傳算法的性能，選取n=15,m=3,t=2,Tu=10的實(shí)例,以最大完工時間為目標(biāo)函數(shù)，最大迭代次數(shù)為200進(jìn)行了實(shí)驗(yàn)。遺傳算法加入災(zāi)變機(jī)制前、后的收斂曲線如圖7所示。

圖7 遺傳算法加入災(zāi)變機(jī)制前、后的收斂曲線

從圖7可看出：在相同迭代次數(shù)下，加入災(zāi)變機(jī)制后遺傳算法的解質(zhì)量優(yōu)于加入前；在目標(biāo)值相近的情況下，遺傳算法加入災(zāi)變機(jī)制后的迭代次數(shù)小于加入前的迭代次數(shù)，由此可認(rèn)為，迭代過程中加入災(zāi)變機(jī)制提高了算法的搜索能力；在目標(biāo)值相近的情況下，加入災(zāi)變機(jī)制前遺傳算法在115代收斂于目標(biāo)值30 min，而加入災(zāi)變機(jī)制后遺傳算法則在120代收斂于目標(biāo)值28 min。

5 結(jié) 語

本文針對預(yù)防性維修的等效并行機(jī)調(diào)度問題，考慮工件的到達(dá)時間和維修策略約束，以最大完工時間的最小化為目標(biāo)，建立了相應(yīng)的數(shù)學(xué)規(guī)劃模型，并提出了基于災(zāi)變機(jī)制的改進(jìn)遺傳算法。通過改變初始種群的生成方式，利用自適應(yīng)災(zāi)變算子并引入災(zāi)變機(jī)制，大大提高了算法的搜索能力和求解質(zhì)量。實(shí)驗(yàn)證明，改進(jìn)遺傳算法用于求解等效并行機(jī)調(diào)度問題是有效的。然而，本文只研究了單目標(biāo)的并行機(jī)調(diào)度問題，并行機(jī)的實(shí)際調(diào)度問題還存在工件投放時間、交貨期、交貨時間等諸多約束和目標(biāo)。因此，未來可根據(jù)解決實(shí)際調(diào)度問題的需要進(jìn)行多目標(biāo)動態(tài)調(diào)度方法的研究。