葛 艷，王愛(ài)民，葉介然

(北京理工大學(xué) 機(jī)械與車(chē)輛學(xué)院，北京 100081)

1 問(wèn)題的提出

車(chē)間調(diào)度是在有限的設(shè)備資源上安排工件進(jìn)行加工，車(chē)間調(diào)度問(wèn)題在最近幾十年已經(jīng)成為工程領(lǐng)域的研究熱點(diǎn)。作業(yè)車(chē)間調(diào)度問(wèn)題(Job-shop Scheduling Problem, JSP)被證明是非確定性多項(xiàng)式(Non-deterministic Polynomial, NP)難問(wèn)題[1]。針對(duì)JSP，VAN LAARHOVEN等[2]以最小化Cmax為目標(biāo)，提出一種基于模擬退火的近似算法；GON?ALVES等[3]利用混合遺傳算法對(duì)JSP進(jìn)行了優(yōu)化。更多研究致力于解決與實(shí)際生產(chǎn)更接近的柔性作業(yè)車(chē)間調(diào)度問(wèn)題(Flexible Job-shop Scheduling Problem, FJSP)，該問(wèn)題是比JSP更為復(fù)雜的NP難問(wèn)題[4]，BRCUKER等[5]率先提出求解包括兩個(gè)工件的FJSP多項(xiàng)式算法。隨著全局優(yōu)化算法的出現(xiàn)和普及，更多研究采用元啟發(fā)式算法求解FJSP。LEE等[6]以最小化Cmax為目標(biāo)，設(shè)計(jì)了一種改進(jìn)遺傳算法，實(shí)現(xiàn)了FJSP的優(yōu)化求解；SAIDI-MEHRABAD等[7]針對(duì)具有工序準(zhǔn)備時(shí)間的FJSP，提出一種基于禁忌搜索的層次逼近算法，并證明該算法在大規(guī)模問(wèn)題和實(shí)際加工問(wèn)題求解中表現(xiàn)突出；LI等[8]提出一種基于混合Pareto前沿的離散人工蜂群算法，實(shí)現(xiàn)了對(duì)多目標(biāo)FJSP的求解。

在JSP和FJSP中，對(duì)于任意一道工序，只要其工藝路線約束下的前一道工序加工完成，且該工序的可加工設(shè)備存在空閑，便可開(kāi)始加工。然而，隨著企業(yè)對(duì)精益生產(chǎn)的貫徹執(zhí)行，在生產(chǎn)過(guò)程中經(jīng)常穿插質(zhì)檢環(huán)節(jié)，使得相鄰工序之間不能直接銜接。根據(jù)生產(chǎn)實(shí)際，產(chǎn)品的質(zhì)檢結(jié)果一般分為合格、返修、報(bào)廢3種。若工件的某一道工序質(zhì)檢結(jié)果為合格，則該工件可直接安排進(jìn)入下一道工序；若工件的某一道工序質(zhì)檢結(jié)果為返修，則該工件需要重新安排當(dāng)前加工工序，直至質(zhì)檢合格或報(bào)廢，如圖1所示；若某一道工序的質(zhì)檢結(jié)果為報(bào)廢，則該工件不能進(jìn)行后續(xù)工序加工，已經(jīng)加工完成的工序也會(huì)作廢，在原問(wèn)題規(guī)模涉及的n個(gè)工件中應(yīng)相應(yīng)增加一個(gè)新的與報(bào)廢工件相同的工件，重新從第一道工序開(kāi)始安排，如圖1所示。

傳統(tǒng)調(diào)度問(wèn)題不涉及工件質(zhì)檢，其排產(chǎn)方法更不涉及如何應(yīng)對(duì)質(zhì)檢結(jié)果出現(xiàn)返修的情況；而對(duì)于質(zhì)檢出現(xiàn)工件報(bào)廢的情況，通常根據(jù)預(yù)先估計(jì)的工件廢品率，在工件加工開(kāi)始就增加工件的排產(chǎn)數(shù)量，從而增加排產(chǎn)方案對(duì)報(bào)廢件的容忍度。這種排產(chǎn)方式?jīng)]有考慮加工過(guò)程中由質(zhì)檢返修帶來(lái)的單道工序重入和由質(zhì)檢報(bào)廢帶來(lái)的工件重新投產(chǎn)的情況，使作業(yè)計(jì)劃與生產(chǎn)實(shí)際脫節(jié)，無(wú)法持續(xù)指導(dǎo)實(shí)際生產(chǎn)。

因此，作業(yè)計(jì)劃需要根據(jù)質(zhì)檢結(jié)果實(shí)時(shí)調(diào)整，確保調(diào)度方案對(duì)生產(chǎn)實(shí)際的持續(xù)指導(dǎo)，即動(dòng)態(tài)調(diào)度[9]。另外，由于在實(shí)際生產(chǎn)中，車(chē)間會(huì)根據(jù)已生成的靜態(tài)作業(yè)計(jì)劃形成物料準(zhǔn)備方案，調(diào)整作業(yè)計(jì)劃可能導(dǎo)致已生成的物料準(zhǔn)備方案不可行。為減少物料準(zhǔn)備方案的頻繁變更，本文動(dòng)態(tài)調(diào)度所形成的排產(chǎn)方案不僅需要如傳統(tǒng)FJSP一樣保證工件最大完工時(shí)間(Cmax)最小化，還應(yīng)保證排產(chǎn)計(jì)劃與初始計(jì)劃的差距最小化。

HOLLOWAY等[10]率先對(duì)作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題進(jìn)行研究，通過(guò)周期性地進(jìn)行排產(chǎn)計(jì)算不斷生成新的調(diào)度方案，并證明了這種周期策略對(duì)求解動(dòng)態(tài)調(diào)度問(wèn)題的有效性；HOLTHAUS[11]針對(duì)設(shè)備故障引發(fā)的工序加工時(shí)間延遲問(wèn)題，提出一種基于仿真的調(diào)度規(guī)則分析方法；FANG等[12]將調(diào)度規(guī)則融入遺傳算法，求解具有工序準(zhǔn)備時(shí)間、工件交貨期約束和設(shè)備故障的作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題；XIONG等[13]以最小化Cmax和最小化排產(chǎn)方案的魯棒性為目標(biāo)，提出一種多目標(biāo)進(jìn)化算法，實(shí)現(xiàn)了具有隨機(jī)設(shè)備故障的FJSP動(dòng)態(tài)調(diào)度。

LIU等[14]針對(duì)具有模糊處理時(shí)間的柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題(Dynamic Flexible Job-shop Scheduling Problem, DFJSP)，提出一種快速分布估計(jì)算法(fast Distribution Estimation Algorithm, fDEA)，實(shí)現(xiàn)了快速尋優(yōu)；SHEN等[15]提出一種多目標(biāo)進(jìn)化算法，解決了DFJSP，并通過(guò)實(shí)例驗(yàn)證了該算法具有較好的整體性能；WANG等[16]采用改進(jìn)遺傳算法求解了具有設(shè)備故障、緊急插單和工件損壞的DFJSP；ZHOU等[17]針對(duì)多目標(biāo)DFJSP，提出一種基于協(xié)同進(jìn)化機(jī)制的非支配遺傳算法，并驗(yàn)證了該算法的有效性和競(jìng)爭(zhēng)力。以上文獻(xiàn)解決了DFJSP，但是均未考慮動(dòng)態(tài)調(diào)度之后的方案對(duì)初始方案的繼承性，新方案一味追求優(yōu)化調(diào)度目標(biāo)，而與初始方案相去甚遠(yuǎn)，使原來(lái)的物料準(zhǔn)備計(jì)劃變得不可行。

綜上所述，本文針對(duì)工序質(zhì)檢結(jié)果造成的原作業(yè)計(jì)劃不具備持續(xù)生產(chǎn)指導(dǎo)依據(jù)的現(xiàn)狀，以及保持新舊排產(chǎn)計(jì)劃一致性的需求，以最小化Cmax和最小化新舊計(jì)劃方案差異性為目標(biāo)，研究具有質(zhì)檢環(huán)節(jié)的DFJSP。針對(duì)問(wèn)題特點(diǎn)和兩個(gè)目標(biāo)，本文結(jié)合遺傳算法的全局搜索能力和模擬退火算法的局部尋優(yōu)能力，提出一種基于局面評(píng)價(jià)的遺傳退火算法。該算法通過(guò)基于局面評(píng)價(jià)的解碼規(guī)則，提高每一個(gè)個(gè)體在新舊排產(chǎn)計(jì)劃一致性方面的性能；同時(shí)，通過(guò)遺傳退火算法的快速尋優(yōu)機(jī)制，重點(diǎn)優(yōu)化最小化Cmax的調(diào)度目標(biāo)。

2 問(wèn)題描述與數(shù)學(xué)建模

2.1 問(wèn)題描述及內(nèi)涵分析

本文研究的具有質(zhì)檢環(huán)節(jié)的FJSP是傳統(tǒng)FJSP的擴(kuò)展。傳統(tǒng)FJSP涉及n個(gè)待加工工件Ji(i=1,2,…,n)和m臺(tái)設(shè)備Mp(p=1,2,…,m)；每個(gè)工件Ji包含一系列具有嚴(yán)格順序的加工工序，每一道工序都可由一臺(tái)或多臺(tái)設(shè)備加工；當(dāng)某一道工序完成加工后，后續(xù)工序即可開(kāi)始加工。

與傳統(tǒng)FJSP不同的是，在本文研究的動(dòng)態(tài)調(diào)度問(wèn)題中，工序分為質(zhì)檢工序和普通工序。對(duì)于質(zhì)檢工序，其加工完成后不能如普通工序一樣直接轉(zhuǎn)向下一道工序，而須進(jìn)行質(zhì)檢，只有當(dāng)質(zhì)檢結(jié)果為合格時(shí)，才能開(kāi)始工件的下一道工序，否則需要重新在當(dāng)前工序加工(質(zhì)檢結(jié)果為返修)，或從第一道工序開(kāi)始重新加工當(dāng)前工件(質(zhì)檢結(jié)果為報(bào)廢)。

由于無(wú)法事先預(yù)測(cè)每一道質(zhì)檢工序的質(zhì)檢結(jié)果，制定初始作業(yè)計(jì)劃時(shí)只能假設(shè)所有質(zhì)檢工序的質(zhì)檢結(jié)果均為合格。在工件加工過(guò)程中，一旦出現(xiàn)某一道工序的質(zhì)檢結(jié)果為返修或報(bào)廢，就意味著當(dāng)前工件甚至其余工件均無(wú)法根據(jù)原作業(yè)計(jì)劃繼續(xù)生產(chǎn)，需要根據(jù)當(dāng)前計(jì)劃和當(dāng)前工件的完成情況重新制定生產(chǎn)計(jì)劃。本文研究的具有質(zhì)檢環(huán)節(jié)的DFJSP特征如下：

(1)問(wèn)題同樣涉及n個(gè)工件Ji(i=1,2,…，n)和m臺(tái)設(shè)備Mp(p=1,2,…,m)，每個(gè)工件Ji包含一系列有嚴(yán)格順序的加工工序，每一道工序都可由一臺(tái)或多臺(tái)設(shè)備加工。

(2)有一個(gè)初始計(jì)劃，初始計(jì)劃中規(guī)定了每一道工序的原加工設(shè)備、原加工開(kāi)始時(shí)間和原加工結(jié)束時(shí)間。

(3)有擾動(dòng)節(jié)點(diǎn)，即質(zhì)檢結(jié)果為不合格或返修的工序的原加工結(jié)束時(shí)間。

(4)原計(jì)劃中，在擾動(dòng)節(jié)點(diǎn)前開(kāi)始的工序已經(jīng)開(kāi)始加工或已經(jīng)完成加工，無(wú)需參與重排，動(dòng)態(tài)調(diào)度僅重新安排原計(jì)劃中在擾動(dòng)節(jié)點(diǎn)后開(kāi)始的工序。

(5)在進(jìn)行動(dòng)態(tài)調(diào)度時(shí)，所有設(shè)備的可用時(shí)間由原先FJSP中的0時(shí)刻變?yōu)楫?dāng)前問(wèn)題中的擾動(dòng)節(jié)點(diǎn)。

(6)問(wèn)題的調(diào)度目標(biāo)為最小化Cmax的同時(shí)最小化新舊方案的差異，以減少對(duì)根據(jù)原方案所制定的物料準(zhǔn)備方案的變更。

根據(jù)以上描述，具有質(zhì)檢環(huán)節(jié)的DFJSP的求解難點(diǎn)在于：

(1)新舊方案差異程度的量化 新舊方案的差異主要體現(xiàn)在所有工序的加工設(shè)備差異和加工開(kāi)始時(shí)間差異兩方面，如何建立合適的評(píng)價(jià)機(jī)制，量化兩個(gè)方案的相似程度，是一大難點(diǎn)。

(2)調(diào)度目標(biāo)之間的平衡 問(wèn)題涉及的兩個(gè)調(diào)度目標(biāo)在一定程度上存在沖突，即獲得最低Cmax的調(diào)度方案與其舊方案的差異未必最??；同樣，與原排產(chǎn)計(jì)劃最接近的方案未必能獲得最低的Cmax。如何獲得能夠綜合優(yōu)化兩個(gè)目標(biāo)的方案是亟待解決的問(wèn)題。

為了更好更嚴(yán)謹(jǐn)?shù)亟鉀Q該問(wèn)題，提出以下假設(shè)：

(1)同一工序在不同設(shè)備上加工所需的處理時(shí)間相同。

(2)屬于不同工件的工序之間沒(méi)有順序約束。

(3)一臺(tái)設(shè)備在同一時(shí)刻只能加工一道工序。

(4)任意一道工序在加工時(shí)不能被打斷，直到該工序加工結(jié)束。

(5)不考慮設(shè)備故障的情況。

(6)不考慮工序周轉(zhuǎn)的時(shí)間。

2.2 數(shù)學(xué)建模

(1)參數(shù)

Ji表示工件i,i=1,2,…,n,n為工件的數(shù)量；

Mp表示設(shè)備p,p=1,2,…,m,m為設(shè)備的數(shù)量；

Oij表示Ji的第j道工序,j=1,2,…,Gi,Gi為Ji的工序數(shù)量；

Tij為工序Oij的加工工時(shí)；

OSij為原計(jì)劃中工序Oij的加工開(kāi)始時(shí)刻；

OEij為原計(jì)劃中工序Oij的加工結(jié)束時(shí)刻；

RT為擾動(dòng)節(jié)點(diǎn)；

L為一個(gè)足夠大的常數(shù)；

α為工序加工設(shè)備變動(dòng)影響系數(shù)，是一個(gè)常數(shù)；

β為工序加工開(kāi)始時(shí)間變動(dòng)影響系數(shù)，是一個(gè)常數(shù)。

(2)決策變量

STij為新計(jì)劃中工序Oij的加工開(kāi)始時(shí)間；

ETij為新計(jì)劃中工序Oij的加工結(jié)束時(shí)間；

Cmax為新計(jì)劃中所有工序的最大完工時(shí)間；

基于以上假設(shè)和符號(hào)，建立如下數(shù)學(xué)模型：

minCmax；

(1)

(2)

Cmax=max(ETij),?i。

(3)

s.t.

STij+Tij=ETij,?i,j；

(4)

OSij+Tij=OEij,?i,j；

(5)

(6)

RT=max(Rij·OEij),?i,j；

(7)

ifOSij

(8)

ifOSij

(9)

(10)

Xijp-Uijp≥0,?i,j,p；

(11)

Xijp-Vijp≥0,?i,j,p；

(12)

(13)

(14)

STi(j+1)≥ETij,?i,j；

(15)

OSi(j+1)≥OEij,?i,j;

(16)

STij+(1-Bi′j′p-ijp)·L≥STi′j′+Ti′j′,

?i,i′∈(1,2,…,n),j,j′∈(1,2,…,Gi),

p∈(1,2,…,m)；

(17)

OSij+(1-Ci′j′p-ijp)·L≥OSi′j′+Ti′j′,

?i,i′∈(1,2,…,n),j,j′∈(1,2,…,Gi),

p∈(1,2,…,m)。

(18)

其中：式(3)為工序最大完工時(shí)間的具體計(jì)算方法；式(4)和式(5)為新舊方案中工序的加工開(kāi)始時(shí)間、加工結(jié)束時(shí)間和加工時(shí)長(zhǎng)之間的數(shù)值關(guān)系；式(6)表示每次重新排產(chǎn)時(shí)，擾動(dòng)工序只有一個(gè)；式(7)為擾動(dòng)節(jié)點(diǎn)的計(jì)算方法，即擾動(dòng)工序在原方案中的加工結(jié)束時(shí)間；式(8)和式(9)表示若工序在原方案中的加工開(kāi)始時(shí)間在擾動(dòng)節(jié)點(diǎn)之前，則新方案中工序的加工時(shí)間和加工設(shè)備保持不變；式(10)～式(14)為設(shè)備約束，表示無(wú)論在新方案還是原方案中，任意一道工序的加工設(shè)備僅有一臺(tái)，且屬于其可選加工設(shè)備集合；式(15)和式(16)為工件加工的工藝路線約束，即任意一道工序都需要在其工藝路線約束下的前一道工序完工后才能開(kāi)始加工；式(17)和式(18)保證每一臺(tái)設(shè)備在同一時(shí)刻最多只能加工一道工序。

3 基于局面評(píng)價(jià)的遺傳退火算法

本文提出的基于局面評(píng)價(jià)的模擬退火算法是傳統(tǒng)模擬退火算法與遺傳算法的結(jié)合。模擬退火算法來(lái)源于固體退火原理，算法迭代從某一較高初溫出發(fā)，隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即能以一定概率跳出局部最優(yōu)解并達(dá)到全局最優(yōu)解，然而這種概率突跳是以犧牲算法運(yùn)行時(shí)間為代價(jià)[18]。如果初始溫度設(shè)置得不夠高或者降溫太快，則容易陷入局部最優(yōu)；如果為了跳出局部最優(yōu)，將初始溫度設(shè)置得足夠高，降溫足夠慢，則會(huì)增加算法時(shí)間。

為了利用模擬退火算法優(yōu)秀的局部尋優(yōu)能力，同時(shí)避免其在尋找全局最優(yōu)解過(guò)程中耗費(fèi)大量時(shí)間，從而在有限計(jì)算時(shí)間內(nèi)找到全局最優(yōu)解的近似解，本文將遺傳算法的種群和變異思想引入模擬退火算法，提出遺傳退火算法。該算法首先通過(guò)遺傳算法產(chǎn)生一系列初始解，作為模擬退火算法的輸入；然后根據(jù)初始解，采用模擬退火算法快速迭代生成一個(gè)局部最優(yōu)解；在當(dāng)前陷入局部最優(yōu)種群的基礎(chǔ)上，再執(zhí)行遺傳算法的變異操作，使種群重新分布于解空間，繼續(xù)尋找下一個(gè)局部最優(yōu)解。通過(guò)“獲得局部最優(yōu)解1→變異→獲得局部最優(yōu)解2→……→獲得局部最優(yōu)解k”的過(guò)程，從多個(gè)局部最優(yōu)解中產(chǎn)生全局近優(yōu)解。該算法沒(méi)有刻意避免算法陷入局部最優(yōu)，反而利用模擬退火算法本身容易陷入局部最優(yōu)的特點(diǎn)，甚至通過(guò)調(diào)節(jié)模擬退火算法的降溫速度來(lái)促進(jìn)算法更加快速地達(dá)到局部最優(yōu)，然后從多個(gè)局部最優(yōu)解中選擇最好解。圖2所示為本文所提遺傳退火算法的流程。

3.1 初始化種群

本節(jié)采用基于工序的編碼方式生成表示工序順序的染色體。染色體中的每個(gè)基因表示對(duì)應(yīng)工件的編號(hào)，相同的基因表示屬于同一工件的不同工序。圖3所示為一個(gè)包括3個(gè)工件的染色體編碼，其表示所有工序的安排順序?yàn)镺31→O11→O21→O32→O12→O22→O33→O13。

3.2 基于局面評(píng)價(jià)的解碼策略

解碼是從染色體生成排產(chǎn)方案的過(guò)程。針對(duì)本文研究的具有質(zhì)檢工序的DFJSP，當(dāng)某一工序的質(zhì)檢結(jié)果為不合格時(shí)，擾動(dòng)節(jié)點(diǎn)之前已經(jīng)開(kāi)始的工序保持其原調(diào)度計(jì)劃中的加工時(shí)間和加工設(shè)備不變，對(duì)擾動(dòng)節(jié)點(diǎn)之后開(kāi)始的工序進(jìn)行重調(diào)度。為響應(yīng)問(wèn)題的調(diào)度目標(biāo)，在安排每一道工序的加工時(shí)間和加工設(shè)備時(shí)，應(yīng)考慮本次安排對(duì)最小化新計(jì)劃的Cmax和最小化新舊計(jì)劃差異程度的影響。

由于編碼只能反映工序的安排順序，并不能規(guī)定工序的設(shè)備選擇和時(shí)間安排。對(duì)于任意一條編碼，每個(gè)基因所代表的工序可能是已安排工序，也可能是未安排工序，對(duì)于未安排工序，需要重新為其安排設(shè)備和加工時(shí)間，如圖4所示。

因?yàn)槊恳坏拦ば虻脑O(shè)備選擇不唯一，所以每一道工序的安排都有很多種方案。為了避免產(chǎn)生劣質(zhì)解，本文建立一種局面評(píng)估機(jī)制來(lái)評(píng)估每一道工序在當(dāng)前狀態(tài)下的不同安排方案，從中選擇當(dāng)前該工序最好的設(shè)備和加工時(shí)間安排。基于局面評(píng)價(jià)的解碼策略流程如圖5a所示。

以一個(gè)包括4個(gè)工件、5臺(tái)設(shè)備的DFJSP為例(基礎(chǔ)數(shù)據(jù)如表1)，介紹局面評(píng)價(jià)策略在某一道具體工序上的應(yīng)用。

根據(jù)圖5a，首先獲得擾動(dòng)工序O41和擾動(dòng)節(jié)點(diǎn)4，在該節(jié)點(diǎn)前開(kāi)始的工序(O31，O21，O11，O22)保持原計(jì)劃的設(shè)備和加工時(shí)間安排，其余工序進(jìn)行重調(diào)度。在重新安排工序O41時(shí)有5臺(tái)可選設(shè)備，因此生成5個(gè)備選方案。

根據(jù)式(19)分別計(jì)算各個(gè)備選方案的評(píng)價(jià)值

Pijp=(STij-OSij)2/(Uijp+Vijp)。

(19)

式中：Pijp為工序Oij選擇設(shè)備Mp為加工設(shè)備時(shí)，當(dāng)前備選方案的評(píng)價(jià)值；分子表示新舊方案中工序Oij的加工開(kāi)始時(shí)間差異，分母表示新舊方案中工序Oij的加工設(shè)備差異?？梢钥闯?，新舊方案中工序Oij的加工時(shí)間和加工設(shè)備差異越大，Pijp的值越小。

根據(jù)式(19)，圖5b所示各備選方案的評(píng)價(jià)值分別為16，64，16，8，36，因此選擇評(píng)價(jià)值最小的備選方案4作為工序O41的安排方案。

表1 柔性作業(yè)車(chē)間工序加工時(shí)間表

按照上述方法，執(zhí)行圖5a中的步驟，可完成對(duì)當(dāng)前染色體的解碼。

3.3 適應(yīng)度函數(shù)

本文研究的存在質(zhì)檢工序的DFJSP有兩個(gè)目標(biāo)函數(shù)：①最小化工件的最大完工時(shí)間；②最小化重調(diào)度方案與原計(jì)劃之間的差異。由于解碼操作中已經(jīng)對(duì)新舊方案的差異進(jìn)行了控制，此處僅以Cmax的值作為個(gè)體的適應(yīng)度值。

3.4 基于模擬退火算法的局部尋優(yōu)

局部尋優(yōu)即利用模擬退火算法，對(duì)遺傳算法產(chǎn)生的初始解和大規(guī)模變異后的解進(jìn)行迭代搜索，得到局部最優(yōu)解的過(guò)程。傳統(tǒng)的模擬退火算法為了避免陷入局部最優(yōu)，要求初始溫度T足夠大，降溫足夠慢，往往需要耗費(fèi)大量的時(shí)間。而本文提出的遺傳退火算法不刻意避免算法陷入早熟，反而利用模擬退火算法容易陷入早熟的特點(diǎn)，快速產(chǎn)生局部最優(yōu)解。圖6所示為基于模擬退火算法的局部最優(yōu)解的產(chǎn)生流程。

根據(jù)圖6，利用模擬退火算法進(jìn)行局部尋優(yōu)的步驟如下：

(1)初始化模擬退火算法的溫度T和溫度的單位變化量ΔT。

(2)以染色體中基因置換的方式獲得每一個(gè)個(gè)體的鄰域，如圖7所示。

(3)計(jì)算每一個(gè)鄰域個(gè)體i′的適應(yīng)度f(wàn)(i′)，并獲得該適應(yīng)度值與原個(gè)體i的適應(yīng)度值f(i)的增量ΔEi=f(i′)-f(i)。

(4)對(duì)于某一個(gè)體i，若適應(yīng)度值的增量滿足ΔEi<0，則個(gè)體i的鄰域個(gè)體i′獲得的Cmax值較小，解的質(zhì)量更優(yōu)，將個(gè)體i更新為個(gè)體i′。

(5)對(duì)于某一個(gè)體i，若適應(yīng)度值的增量滿足ΔEi≥0，則根據(jù)式(20)計(jì)算個(gè)體i′的接受度，式中T為當(dāng)前溫度值，k為算法當(dāng)前的迭代次數(shù)。

(20)

(6)生成一個(gè)(0,1)范圍內(nèi)的隨機(jī)數(shù)rand，若ri>rand，則將個(gè)體i更新為個(gè)體i′，否則保留個(gè)體i。

(7)根據(jù)ΔT的值更新當(dāng)前溫度T，并判斷算法是否達(dá)到終止條件。若是，則結(jié)束算法，輸出多個(gè)局部最優(yōu)解；否則，進(jìn)行下一次迭代，轉(zhuǎn)步驟(2)。

3.5 跳出局部最優(yōu)——大規(guī)模變異策略

變異是改變?nèi)旧w中的某些基因、生成新的染色體的過(guò)程。當(dāng)模擬退火算法結(jié)束時(shí)，由于其卓越的局部搜索能力，算法得到的解大多集中在局部最優(yōu)解附近，為使算法跳出局部最優(yōu)，需要對(duì)這些解進(jìn)行大規(guī)模變異，以增強(qiáng)種群多樣性，改善算法的全局搜索能力。變異算子的設(shè)計(jì)如圖8所示。

4 實(shí)例驗(yàn)證與算法比較

為了驗(yàn)證基于局面評(píng)價(jià)的設(shè)備選擇規(guī)則對(duì)縮小解空間、減小重調(diào)度前后排產(chǎn)方案差異性的貢獻(xiàn)，以及遺傳退火算法對(duì)提高算法收斂性的貢獻(xiàn)，本文以文獻(xiàn)[19]的案例MK1～MK3為例，在每一個(gè)案例中設(shè)置若干質(zhì)檢工序，利用所提算法和文獻(xiàn)中的其他3種算法對(duì)每道質(zhì)檢工序返修和報(bào)廢兩種擾動(dòng)進(jìn)行響應(yīng)，探索擾動(dòng)節(jié)點(diǎn)對(duì)算法求解結(jié)果的影響。

表2所示為案例的詳細(xì)信息，表中N和M分別為工件數(shù)量和設(shè)備數(shù)量，Tnop和Qnop分別為案例的總工序數(shù)量和質(zhì)檢工序數(shù)量，meq為每一道工序的可選加工設(shè)備數(shù)，proc為每一道工序加工工時(shí)的取值范圍，ICmax為初始方案的最大完工時(shí)間。

表2 案例詳細(xì)信息

本章采用Visual C#語(yǔ)言編程實(shí)現(xiàn)參與對(duì)比的4種算法，在處理器為i7-7500U CPU、主頻為2.7 GHz、內(nèi)存為24 GB的個(gè)人計(jì)算機(jī)上運(yùn)行，求解上述3個(gè)案例。在求解案例時(shí)，每種算法連續(xù)運(yùn)行20次，取最好結(jié)果，4種算法的詳細(xì)信息和運(yùn)行結(jié)果分別如表3和表4所示。算法運(yùn)行時(shí)，A1和A3采用直線降溫策略共降溫10次，每個(gè)溫度下迭代60次，種群規(guī)模為6，大規(guī)模變異次數(shù)設(shè)置為10，最大迭代600次；A2和A4的種群數(shù)量為60，迭代次數(shù)為600。

表3 4種算法的詳細(xì)信息

表4 案例運(yùn)行結(jié)果

續(xù)表4

注：dt為擾動(dòng)工序在初始調(diào)度方案中的結(jié)束時(shí)間；dn為按照式(2)計(jì)算的新舊方案的差異；α和β分別設(shè)置為1/Tnop和1/ICmax。

根據(jù)表4中的運(yùn)行結(jié)果，分別從橫向和縱向兩個(gè)維度對(duì)算法進(jìn)行Cmax、新舊方案差異程度、運(yùn)行時(shí)間、迭代性能4個(gè)方面的比較和分析。其中，縱向分析主要探索算法運(yùn)行結(jié)果隨dt變化的趨勢(shì)，橫向?qū)Ρ戎饕容^4種算法的優(yōu)劣。

(1)案例規(guī)模對(duì)Cmax的影響分析

如圖9所示，應(yīng)對(duì)返修擾動(dòng)時(shí)，對(duì)于小規(guī)模案例，重調(diào)度方案的Cmax與初始方案差異較小，基本與dt無(wú)關(guān)；對(duì)于大規(guī)模案例MK3，Cmax隨dt的增大呈下降趨勢(shì)。原因是，在小規(guī)模案例中，返修擾動(dòng)造成的受影響工序較少，無(wú)論dt為多少，最好的情況下，重調(diào)度方案僅需要比初始方案多安排一道工序(當(dāng)前擾動(dòng)工序)，因此Cmax的差異較??；在大規(guī)模案例中，dt越小，返修擾動(dòng)造成的受影響工序越多，在初始方案足夠完備的情況下，需要重排的工序越多，Cmax值增大得越明顯。

應(yīng)對(duì)報(bào)廢擾動(dòng)時(shí)，重調(diào)度方案需要重新安排包括當(dāng)前擾動(dòng)工序在內(nèi)的所屬工件之前的所有工序，一般dt越大，需要重新安排的工序越多，Cmax增大得越多。因此，圖9中3種算法形成的重調(diào)度方案的Cmax隨dt的增大呈上升趨勢(shì)，這種趨勢(shì)在小規(guī)模案例MK1和MK2的表現(xiàn)更為明顯。

(2)算法對(duì)Cmax的影響分析

在應(yīng)對(duì)返修擾動(dòng)和報(bào)廢擾動(dòng)時(shí)，A1和A3獲得的Cmax大致相同，均低于A2，而且這種差距隨dt的增大逐漸減小。原因是，A1和A3采用本文所提遺傳退火算法進(jìn)行尋優(yōu)，A2采用的是傳統(tǒng)遺傳算法，傳統(tǒng)遺傳算法易早熟，從而陷入局部最優(yōu)。本文所提遺傳退火算法在迭代過(guò)程中包括定期跳出局部最優(yōu)的大規(guī)模變異操作，相當(dāng)于從多個(gè)局部最優(yōu)解中選出一個(gè)最終解，因此具有較好的全局搜索性能。然而，隨著dt的增大，案例中需要重新安排的工序逐漸減少，解空間隨之減小，甚至減小到1(例如原初始方案中的最后一道工序發(fā)生返修擾動(dòng))，這種情況下尋優(yōu)算法的優(yōu)勢(shì)不能體現(xiàn)，出現(xiàn)圖9中后期3條線重合的現(xiàn)象。

與其他3種算法相比，A4獲得的Cmax沒(méi)有明顯的優(yōu)勢(shì)或劣勢(shì)，原因是非支配遺傳算法雖然具有多目標(biāo)優(yōu)化能力，但是多個(gè)目標(biāo)之間地位平等、不分主次，難以應(yīng)對(duì)本文要求的在最小化Cmax的前提下保證新舊方案差異程度的特殊性。

(3)案例規(guī)模和擾動(dòng)類(lèi)型對(duì)新舊方案差異程度的影響分析

如圖10所示，應(yīng)對(duì)返修擾動(dòng)和報(bào)廢擾動(dòng)時(shí)，3種算法形成的重調(diào)度方案與初始方案的差異程度均隨dt的增大而下降。原因是，隨著dt的增大，應(yīng)對(duì)擾動(dòng)時(shí)需要重新排產(chǎn)的工序逐漸減少，新方案對(duì)初始方案的繼承逐漸增多。

(4)算法對(duì)新舊方案差異程度的影響分析

當(dāng)應(yīng)對(duì)返修擾動(dòng)和報(bào)廢擾動(dòng)時(shí)，A1和A2產(chǎn)生的新方案與初始方案的差異程度相近，均優(yōu)于A3，而且隨著dt的增大，3種算法的差距逐漸減小。原因是，A1和A2采用本文所提基于局面評(píng)價(jià)的解碼策略，可以在安排工序時(shí)綜合比較該工序的各種安排方案與初始計(jì)劃的差異，通過(guò)局面評(píng)價(jià)策略選擇差異較小的方案，從而減小整個(gè)計(jì)劃與初始計(jì)劃的差異；A3基于最早開(kāi)始規(guī)則的解碼策略不能在解碼即進(jìn)行這種考慮。同樣，隨著dt的不斷增大，解空間不斷減小，該解碼策略的優(yōu)勢(shì)也會(huì)減弱。與(2)所述一樣，與其他3種算法相比，A4獲得的dn值沒(méi)有明顯的優(yōu)勢(shì)或劣勢(shì)。

(5)不同算法運(yùn)行時(shí)間對(duì)比分析

當(dāng)應(yīng)對(duì)返修擾動(dòng)和報(bào)廢擾動(dòng)時(shí)，A1，A3，A4的運(yùn)行時(shí)間接近，均明顯小于A2，說(shuō)明本文所提遺傳退火算法較傳統(tǒng)遺傳算法具有較好的時(shí)間性能。

最后，為驗(yàn)證本文所提遺傳退火算法的全局搜索性能，以案例MK3中dt=29時(shí)應(yīng)對(duì)返修擾動(dòng)的情況為例，比較4種算法的收斂性能。圖11所示為4種算法的收斂曲線，其中橫坐標(biāo)表示算法的迭代次數(shù)，縱坐標(biāo)為算法在對(duì)應(yīng)迭代次數(shù)下獲得的Cmax值。

由圖11可見(jiàn)，A1和A3的迭代曲線中均有多個(gè)突變點(diǎn)，這些突變點(diǎn)即為發(fā)生大規(guī)模變異的時(shí)刻。多次大規(guī)模變異將算法的全局尋優(yōu)過(guò)程分為多個(gè)局部尋優(yōu)階段，使算法從多個(gè)局部最優(yōu)解中選出最終解。而A2在算法迭代的初始階段便陷入早熟，這與前文的分析一致，這種早熟在一定程度上抑制了算法的全局尋優(yōu)進(jìn)程。經(jīng)過(guò)改進(jìn)，A4的尋優(yōu)速度和深度均優(yōu)于A2，但仍然易陷入早熟。

5 結(jié)束語(yǔ)

本文研究具有質(zhì)檢環(huán)節(jié)的DFJSP，該問(wèn)題的部分工序加工完成后不能立刻開(kāi)始下一道工序，而須經(jīng)歷質(zhì)檢環(huán)節(jié)。質(zhì)檢環(huán)節(jié)的結(jié)果有合格、返修和報(bào)廢3種情況，一旦某道工序的質(zhì)檢結(jié)果為返修或報(bào)廢，該工序甚至對(duì)應(yīng)工件必須重新加工，因此需要重新生成排產(chǎn)方案。

根據(jù)分析問(wèn)題約束和特點(diǎn)，本文以最小化工件的最大完工時(shí)間和最小化新舊方案差異為目標(biāo)，建立了一個(gè)混合整數(shù)規(guī)劃模型，描述了返修擾動(dòng)和報(bào)廢擾動(dòng)的處理方式，然后提出一種基于局面評(píng)價(jià)的遺傳退火算法求解問(wèn)題。該算法將遺傳算法的編碼方式、變異算子和退火算法的逐溫度尋優(yōu)過(guò)程高效結(jié)合，以提高算法在有限運(yùn)行時(shí)間內(nèi)的全局搜索性能。在實(shí)例驗(yàn)證部分，本文選取Brandimarte[19]的案例MK1～MK3，在每一個(gè)案例中添加若干道質(zhì)檢工序，分別采用該算法與另外3種算法求解各工序?qū)_動(dòng)的響應(yīng)，驗(yàn)證擾動(dòng)節(jié)點(diǎn)、案例規(guī)模和所用算法對(duì)案例求解結(jié)果的影響。實(shí)例驗(yàn)證表明，基于局面評(píng)價(jià)的遺傳退火算法具有較好的全局搜索性能，可以有效解決本文涉及的帶有質(zhì)檢環(huán)節(jié)的DFJSP，并能在一定程度上保證重調(diào)度方案與初始方案一致。