葛 艷,王愛(à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