安裝時間與次序相關(guān)的生產(chǎn)調(diào)度干擾管理研究

劉 鋒，王建軍，饒衛(wèi)振，2，楊德禮

（1.大連理工大學(xué)系統(tǒng)工程研究所，遼寧大連116023；2.山東科技大學(xué)經(jīng)濟(jì)管理學(xué)院，山東青島266590）

安裝時間與次序相關(guān)的生產(chǎn)調(diào)度干擾管理研究

劉 鋒1，王建軍1，饒衛(wèi)振1，2，楊德禮1

（1.大連理工大學(xué)系統(tǒng)工程研究所，遼寧大連116023；2.山東科技大學(xué)經(jīng)濟(jì)管理學(xué)院，山東青島266590）

在安裝時間和次序相關(guān)的單機(jī)調(diào)度問題中，為應(yīng)對突發(fā)性的工件優(yōu)先級變動造成的影響，構(gòu)建了雙目標(biāo)重調(diào)度模型。原目標(biāo)為生產(chǎn)的流程時間，擾動目標(biāo)為工件的加工次序擾動。針對模型中的雙目標(biāo)，設(shè)計了基于有效解的兩階段混合啟發(fā)式算法進(jìn)行求解，在原目標(biāo)和擾動目標(biāo)之間進(jìn)行權(quán)衡?；旌纤惴ǖ谝浑A段里，基于任意單個工件次序變化將雙目標(biāo)問題轉(zhuǎn)化成單目標(biāo)TSP問題，利用最近鄰域和插入混合求得單目標(biāo)問題的若干解，構(gòu)成初始種群。第二階段中基于非支配排序遺傳算法在處理多目標(biāo)問題上的優(yōu)勢，對初始種群進(jìn)行擴(kuò)展搜索，最后輸出問題的有效前沿。通過數(shù)值試驗運(yùn)算比較分析若干針對有效解集的指標(biāo)，驗證了混合算法求得的解集在多樣性和臨近性上要優(yōu)于單純的非支配排序遺傳算法。該混合算法可以有效地解決具有安裝時間的加工次序擾動問題。關(guān)鍵詞：重調(diào)度；次序擾動；雙目標(biāo)；有效前沿；非支配排序遺傳算法

1 引言

具有跟次序相關(guān)的安裝時間（sequence dependent setup times）的調(diào)度問題作為一類較為復(fù)雜的問題，在制造業(yè)中有著廣泛的應(yīng)用［1］。當(dāng)安裝時間與次序無關(guān)時，安裝時間可視為工件加工時間的一部分而不予特殊考慮；當(dāng)安裝時間與次序相關(guān)時，安裝時間就會對調(diào)度結(jié)果產(chǎn)生影響，無法忽略［2］。如何解決安裝時間與次序相關(guān)的調(diào)度問題引起了學(xué)術(shù)界廣泛的研究興趣。然而現(xiàn)有關(guān)于安裝時間的調(diào)度研究大都假設(shè)穩(wěn)定的加工環(huán)境，初始加工計劃可以順利執(zhí)行。實際加工過程容易受到各種干擾事件如機(jī)器維護(hù)［3］、計劃外新增加的加工任務(wù)［4］、工件優(yōu)先級變動［5］以及工件就緒時間變動［6］等因素的影響。面對突發(fā)性干擾事件，如何有效降低其對生產(chǎn)成本和初始計劃的影響，是目前機(jī)器排序領(lǐng)域需解決的熱點問題。

目前學(xué)術(shù)界除在經(jīng)典調(diào)度問題中研究與加工次序相關(guān)的安裝時間，如唐立新和黃琳［1］在流水車間背景下研究了安裝時間與次序相關(guān)時如何最小化生產(chǎn)流程時間，還針對工件的加工時間與位置相關(guān)時展開了研究。Kuo等［2］，Zhao Chuanli和Tang Hengyong［7］，Cheng等［8］分別在不同加工環(huán)境下，既考慮安裝時間與已經(jīng)完工的工件相關(guān)，又考慮工件的加工時間具有“惡化效應(yīng)”或者“學(xué)習(xí)效應(yīng)”。此外，由于問題內(nèi)在的復(fù)雜性，Bahalke等［9］設(shè)計了遺傳算法和禁忌搜索算法求解了具有跟次序相關(guān)的安裝時間和“惡化效應(yīng)”的單機(jī)調(diào)度問題，最小化了流程時間。

以上研究大都假設(shè)加工環(huán)境相對穩(wěn)定，而實際中受干擾事件的影響，初始為最優(yōu)化某個目標(biāo)的加工計劃將不再可行。此時需要對初始計劃進(jìn)行調(diào)整，Ouelhadj和Petrovic［10］針對實時發(fā)生的干擾事件，系統(tǒng)評述了各種動態(tài)地調(diào)整初始加工時間表的方法。面對干擾事件，如何合理度量其影響是干擾管理面臨的首要問題?，F(xiàn)有研究中，存在多種度量干擾事件影響的方式。Gurel等［11］針對機(jī)器故障，研究了如何以盡量小的成本使得新加工時間表在某時刻完全恢復(fù)到初始加工時間表。他們通過綜合考慮工件的柔性和干擾事件發(fā)生、持續(xù)的概率信息，制定出具有一定柔性的初始加工計劃來達(dá)到這一目的。此時干擾事件的影響體現(xiàn)在為盡快恢復(fù)到初始加工時間表而增加的加工成本。

當(dāng)加工環(huán)境為多機(jī)時，干擾事件可能會造成“工件-機(jī)器”的重新分配，產(chǎn)生額外的工件運(yùn)輸成本。Ozlen和Azizoglu［12］在變速機(jī)環(huán)境下研究了干擾事件發(fā)生后同時考慮工作流程時間與“工件-機(jī)器”重新分配成本的雙目標(biāo)重排序問題。Lee等［13］針對干擾發(fā)生時受擾工件或者等機(jī)器恢復(fù)后再處理，或者以一定成本運(yùn)輸至其他機(jī)器來處理，研究了如何考慮原目標(biāo)、運(yùn)輸成本和擾動目標(biāo)進(jìn)行重排序。

此外，干擾事件對初始加工時間表造成的影響通常表現(xiàn)在兩方面：工件完工時間的擾動以及工件加工次序的擾動。Hall和Potts［4，6］針對計劃外突發(fā)而至的任務(wù)，以及部分工件的就緒時間延后，研究了如何重排序使得干擾事件對初始加工時間表中工件的完工時間與加工次序的影響最小。Qi Xiangtong等［5］在單機(jī)和平行機(jī)環(huán)境下，分別研究了如何應(yīng)對機(jī)器干擾和工件干擾對工件完工時間的影響。與Hall和Potts［4，6］類似，在單機(jī)并且工件具有就緒時間時，Yuan Jinjiang和Mu Yundong［14］在干擾事件造成的最大加工次序擾動滿足一定約束條件下研究了流程時間的最小化；Yuan Jinjiang等［15］還研究了流程時間滿足一定約束條件下最小化工件次序擾動之和的問題。Al-Hinai和El Mekkawy［16］針對具有安裝時間的柔性作業(yè)車間調(diào)度問題，設(shè)計了混合遺傳算法求解具有魯棒性和穩(wěn)定性的初始調(diào)度計劃。這使得干擾事件發(fā)生并重調(diào)度后的新計劃不僅可以維持初始目標(biāo)的質(zhì)量，還可以使得新計劃在完工時間絕對偏差上比較小。他們研究的安裝時間與加工次序無關(guān)從而可附加到工件的處理時間內(nèi)。

從文獻(xiàn)綜述可見，盡管機(jī)器調(diào)度領(lǐng)域中針對工件的安裝時間已經(jīng)展開了各種研究，如同時考慮工件具有位置相關(guān)性的加工時間與安裝時間、安裝時間和已經(jīng)完工的工件相關(guān)等，但是現(xiàn)有和次序相關(guān)的安裝時間研究大都假設(shè)加工環(huán)境相對穩(wěn)定，初始加工計劃一旦制定好就可以順利執(zhí)行，較少考慮干擾事件對于初始計劃造成的影響。因此本文針對突發(fā)性的工件優(yōu)先級變化，同時考慮流程時間和干擾事件造成的加工次序擾動，研究如何在原目標(biāo)和擾動目標(biāo)之間進(jìn)行權(quán)衡。由于問題內(nèi)在的復(fù)雜性使精確算法基本不可行，本文針對雙目標(biāo)問題的特性，設(shè)計啟發(fā)式算法以期求得多目標(biāo)問題盡可能優(yōu)良的有效前沿。

2 問題描述

某工件集在0時刻就緒，決策者需要在不允許搶占（non-preemptive）單機(jī)環(huán)境下安排工件進(jìn)行加工，最小化加工的流程時間。工件在加工過程中如果受突發(fā)事件影響被強(qiáng)制中斷，則需完全重新進(jìn)行加工，即“中斷-重復(fù)”（preempt-repeat）［11］。工件之間存在依賴于加工次序的安裝時間。本文研究一般意義上的安裝時間，并假設(shè)出現(xiàn)的參數(shù)都為正整數(shù)。工件Ji的加工時間為pi，如果工件Ji安排在工件Jj之前加工，則Jj的安裝時間為sij；如果Ji安排第一個加工，則Ji的安裝時間為s0i；如果Ji安排在最后一個加工，則Ji在完工之后機(jī)器需要一段時間進(jìn)行檢測清理，清理時間記為si0。對于i=j，sij=0。

在執(zhí)行為最小化流程時間而制定的初始最優(yōu)加工時間表時，由于外部市場不確定性在計劃周期內(nèi)決策者獲知待加工工件Jd由于優(yōu)先級的緊急提高，加工完當(dāng)前正在處理的工件后需要馬上加工Jd。不失一般性，假設(shè)Jd完工之后還剩余n個工件待處理。如圖1所示重置Jd的完工時間為新的0時刻，并對剩余的n個工件按初始時間表中的次序重新進(jìn)行編號：J1，J2，…，Jn。

圖1 重置0時刻

Jd優(yōu)先級的變化對初始最優(yōu)加工次序造成了干擾，因此在新的0時刻重新安排J1，J2，…，Jn的加工次序時不僅需要考慮加工的流程時間，還需考慮干擾事件對整個生產(chǎn)系統(tǒng)的造成的影響。下面分別定義兩個目標(biāo)：

針對初始目標(biāo)，對于一個可行加工時間表π，令f1（π）表示工件的最大完工時間，則：

針對擾動目標(biāo)，對于一個可行加工時間表π，干擾事件造成的影響用π相對于初始加工次序J1，J2，…，Jn的變化來衡量，含義為干擾事件對加工系統(tǒng)整個生產(chǎn)周期內(nèi)資源重新配置造成的影響［4］。和Hall等［4］，Yuan Jinjiang等［14-15］用工件加工次序的變化來度量干擾類似，本文采用工件相對加工位置的變化來度量干擾。令Dij表示與初始加工次序中“Ji直接安排在Ji+1之前”相比，當(dāng)Ji直接安排在Jj之前加工時，加工次序的變化。因此，對于i，j=0，1，…，n，當(dāng)i＜j時，Dij=j-i-1；當(dāng)i=j時，Dij=0；當(dāng)i＞j時，Dij=j-i+n。

令 f2（π）表示擾動目標(biāo)，則 f2（π）=。采用經(jīng)典的三參數(shù)表示法［17］和Qi Xiangtong等［5］中干擾事件的表示法，所研究問題可以表示如下：

其中，“1”表示單機(jī)加工環(huán)境；“sij”表示工件之間存在與次序相關(guān)的安裝時間；“post-mgt”表示突發(fā)性干擾事件，只能等其結(jié)束才能進(jìn)行應(yīng)對處理；“f1（π），f2（π）”表示雙目標(biāo)排序問題。在不引起歧義下，簡記“f1（π），f2（π）”為“f1，f2”。與Qi Xiangtong［5］類似，計劃周期內(nèi)假設(shè)同一時刻只有一項干擾事件發(fā)生，如果多項干擾事件發(fā)生則按照發(fā)生的前后次序依次進(jìn)行處理。

3 問題求解

在排序領(lǐng)域由于很多問題本身是NP-Hard，因此啟發(fā)式算法求解是較為有效的一個途徑?，F(xiàn)有文獻(xiàn)中用于解決調(diào)度問題的啟發(fā)式算法主要有：解決具有批次容量限制的單機(jī)批處理問題的差分進(jìn)化算法［18］，解決混合流水車間問題的遺傳算法［19］，以及解決工件尺寸有差異的單機(jī)批處理問題的粒子群算法［20］等。以上問題都是單目標(biāo)問題，而針對問題（1）中的多目標(biāo)排序，基于Pareto最優(yōu)的遺傳算法已經(jīng)在多個領(lǐng)域如運(yùn)籌學(xué)、計算機(jī)科學(xué)等引起廣泛研究興趣［21］。Srinvas與Deb提出并經(jīng)改進(jìn)后的非支配排序遺傳算法（NSGA-II）是目前公認(rèn)的有效多目標(biāo)進(jìn)化算法之一［21-23］。改進(jìn)后的NSGA-II基于新的非支配排序方法，計算復(fù)雜度得以降低［24］。利用NSGA-II求解問題時，初始種群的優(yōu)劣會影響到遺傳算法的收斂速度以及最終多目標(biāo)問題有效前沿的質(zhì)量［16，21］。因此本文設(shè)計兩階段混合算法，在求得較優(yōu)初始種群的前提下再進(jìn)行深入擴(kuò)展搜索，以期獲得質(zhì)量較優(yōu)的有效前沿。

在沒有干擾事件發(fā)生的前提下，根據(jù)Pinedo［17］，本文研究的排序問題可以轉(zhuǎn)化成NP-Hard組合優(yōu)化問題——TSP問題。求解TSP問題時由于組合爆炸使得精確算法大多不可行，而啟發(fā)式算法由于能在合理時間內(nèi)找到近似解或最優(yōu)解得到了廣泛研究和應(yīng)用［25］。羅辭勇等［26］基于構(gòu)建型啟發(fā)式方法中的最近鄰域算法和插入算法的特點，結(jié)合兩者的優(yōu)點，提出了多項式時間的“最近鄰域與插入混合”的算法，并使用標(biāo)準(zhǔn)算例庫驗證了該算法對于求解一般性TSP問題的有效性［25］。因此，在饒衛(wèi)振等［25］的基礎(chǔ)上，本文結(jié)合構(gòu)建型啟發(fā)式算法和NSGA-II各自的優(yōu)點設(shè)計一種混合算法，針對問題（1）中的多目標(biāo)求得在鄰近性（proximity）和多樣性（diversity）兩方面都比較優(yōu)良的有效前沿。

混合算法主要分兩階段進(jìn)行：

階段1：基于“最近鄰域與插入混合”的構(gòu)建型算法進(jìn)行深入搜索求得問題（1）的解，構(gòu)建初始種群；

由于本文研究的干擾目標(biāo)含義是對生產(chǎn)周期內(nèi)資源的重新配置造成的影響，比較容易進(jìn)行估算并且與系統(tǒng)的生產(chǎn)成本具有可比性［4］。因此與Hall等［4］類似，令μ表示擾動目標(biāo)相對于原目標(biāo)的單位成本，μ≥0。問題（1）中的雙目標(biāo)此時可以轉(zhuǎn)化為單目標(biāo)來處理：決定工件J1，J2，…Jn加工次序的一個置換，使得最小。這使得干擾管理問題轉(zhuǎn)化成類似TSP的問題，可應(yīng)用求解TSP問題的方法進(jìn)行求解。

階段2：基于非支配排序遺傳算法，對第一階段得到的初始種群進(jìn)行搜索，基于有效前沿的劃分和適應(yīng)度值的分配沿問題的有效前沿進(jìn)行擴(kuò)展，最終輸出問題（1）的有效前沿。

具體方面首先根據(jù)解之間的支配關(guān)系將種群劃分為多個有效前沿。對于不同的有效前沿，質(zhì)量越好的有效前沿中的個體分配更高的適應(yīng)度值；對于同一有效前沿中，用個體間的擁擠距離來度量區(qū)域的稀疏程度，給較為稀疏區(qū)域的個體分配更高的適應(yīng)度值。

令J=｛1，…，n｝表示待加工工件的標(biāo)號集合，α為滿足0＜α＜1的常數(shù)，初始工件標(biāo)號為i=1，混合算法的具體流程圖2所示。圖2第一個判斷條件中的［n（1-α）］表示不超過n（1-α）的最大整數(shù)，插入算法和最近鄰域算法的構(gòu)造規(guī)則具體細(xì)節(jié)請參見饒衛(wèi)振等［25］，有效前沿的劃分以及適應(yīng)度值的分配等具體細(xì)節(jié)請參見Deb等［24］。

在給出混合算法的流程之后，對其計算復(fù)雜性進(jìn)行分析?；旌纤惴ǖ碾A段1是構(gòu)建型的啟發(fā)式方法，階段2是基于種群進(jìn)化的啟發(fā)式方法。

階段1求解問題的計算量可以表示為工件數(shù)量n的函數(shù)，記為φ（n），由參數(shù)α、最近領(lǐng)域算法和插入算法的計算量確定。

圖2 混合算法流程

令最近領(lǐng)域算法（nearest neighbor，NN）完成第k步構(gòu)造的計算量記為Φ（k）。第k步首先從其他n-1個工件中判斷出n-k個未處理工件，然后在n-k個未處理工件中判斷出跟當(dāng)前工件最小的安裝時間與擾動的加權(quán)和，第k步完成。因此最近鄰域算法的單步計算量Φ（k）和總計算量φ（n）NN可以計算為：

令插入算法（insertion，IN）完成第k步構(gòu)造的計算量記為Ω（k）。第k步首先從其他n-1個工件中判斷出n-k個未加工工件，然后計算當(dāng)前工件分別插入當(dāng)前k-1個位置使目標(biāo)增加的程度（i插入j、h之間，增加為：sji+sih-sjh+η·Dji+η·Dihη·Djh），在k-1個增加值中最小值對應(yīng)的位置即為待插入工件的最佳插入位置，最后更新加工時間表完成第k步。因此IN算法的單步計算量Ω（k）和總計算量φ（n）IN可以分別為：

令m=［n（1-α）］，那么第一階段算法的計算量可以由下式計算：

由0≤α≤1，可得0≤m≤n，因此有不等式成立：f（n）NN≤f（m，n）NN＆IN≤f（n）IN。不等式左右兩邊等號，分別在m=n和m=0即α=0和α=1處取得。由于算法復(fù)雜度僅由計算量多項式的最高次確定，所以第一階段的算法復(fù)雜度為O（n2）。

由Deb等［24］可知，階段2的算法復(fù)雜度主要由對種群根據(jù)個體間相互支配關(guān)系進(jìn)行有效前沿的劃分來決定。將適應(yīng)度值計算視為基本的運(yùn)算，令N為種群規(guī)模，每個個體都是對n個工件加工次序的遺傳編碼，具體方式在下一部分進(jìn)行介紹。每個個體都需要與種群中其他個體進(jìn)行比較，總共需要的比較次數(shù)為N（N-1）/2。每次比較都需要決定兩個個體在本文2個目標(biāo)下的支配關(guān)系，因此總體上計算復(fù)雜度為O（2N2）。

因此，本文設(shè)計混合算法的復(fù)雜度為O（n2）+O（2N2），是關(guān)于工件個數(shù)和遺傳算法種群規(guī)模的多項式時間算法。

4 數(shù)值試驗

由于問題（1）是雙目標(biāo)問題，同時最優(yōu)化兩個目標(biāo)的解幾乎不存在，只能求出問題（1）的由一系列有效解構(gòu)成的有效前沿［21］。有效前沿中的解不存在相互支配關(guān)系。一個多目標(biāo)問題有效前沿的質(zhì)量主要體現(xiàn)在解的多樣性（diversity）和與最優(yōu)有效前沿的鄰近性（proximity）［21］。多樣性體現(xiàn)在有效前沿中不重復(fù)解的個數(shù)以及分布的均勻程度，而臨近性體現(xiàn)在多目標(biāo)求解算法最終能否搜索到最優(yōu)有效前沿或者與最優(yōu)有效前沿較為接近的解集，即算法能否收斂到最優(yōu)有效前沿［21］，現(xiàn)有研究經(jīng)常使用跟最優(yōu)有效前沿的距離來度量［26-28］。因此，有效前沿的臨近性反應(yīng)了算法的收斂性。

為驗證本文所提算法的有效性，本部分首先給出現(xiàn)有度量有效前沿多樣性和臨近性的若干指標(biāo)，然后采用文獻(xiàn)［5，6，11，12，14-17，22，29］等驗證算法有效性的手段，通過隨機(jī)生成數(shù)值進(jìn)行算例驗證，最后對比試驗結(jié)果分析算法的收斂性和收斂速度。

4.1 有效前沿指標(biāo)

令E和E′分別表示兩種不同方法求出的問題（1）的有效前沿，指標(biāo)名稱和含義如下所示，具體計算公式請參見Li Binbin等［21］。

（1）ONVG：E的ONVG值含義為E中不重復(fù)解的數(shù)量。其值越大E的多樣性越好。

（2）CM（E，E′）：含義為E′中被E中的解支配的解的比例，直接反映了E和E′之間的相互支配關(guān)系。如果CM（E，E′）＞CM（E′，E），則E優(yōu)于E′。

（3）Dave：令R表示最優(yōu)有效前沿的參考集合，E的Dave值含義為R中的解到E的最近距離的平均值。Dave值越小，E的鄰近性越好，算法的收斂性越好。

（4）Dmax：令R表示最優(yōu)有效前沿的參考集合，E的Dmax值含義為R中的解到E的最近距離的最大值。與Dave類似，Dmax值越小，E的鄰近性越好。在利用Dave和Dmax比較E和E′時，如果最優(yōu)有效前沿未知，則合并E和E′構(gòu)成一個新的集合。選出這個集合中所有有效解構(gòu)成最優(yōu)有效前沿。

（5）TS：E的TS值含義為E中有效解分布的均勻程度，TS值越小，E的有效解分布越均勻，有效前沿的多樣性越好。

（6）AQ：E的AQ值含義為有效前沿在多樣性和鄰近性兩方面的平均性能。AQ考慮了鄰近性和多樣性之間的相互抵消，值越小有效前沿的平均性能越好。

本文采用的收斂性指標(biāo)和羅辭勇等［26］、畢曉君等［27］研究改進(jìn)NSGA-II時使用的收斂性指標(biāo)含義都是集合之間的距離，但區(qū)別在于：羅辭勇等、畢曉君等采用的是標(biāo)準(zhǔn)函數(shù)庫，因此事先可以獲知最優(yōu)有效前沿，從而基于跟最優(yōu)有效前沿的距離來判斷算法的收斂性。對此信息本研究無法提前預(yù)知，只能采用合并待比較有效前沿，選取其中所有有效解構(gòu)成參考集合的方式進(jìn)行處理［21］。此外，本文還采用指標(biāo)（2）根據(jù)有效前沿的相互支配關(guān)系直觀反映出算法的收斂性。

4.2 算例參數(shù)

數(shù)值試驗中的算例參數(shù)是在重置0時刻并且對工件重新編號后給出。初始加工次序J1，J2，…，Jn對應(yīng)的加工次序置換為1，2，…，n。分別考慮工件個數(shù)為n=50，100。工件之間的安裝時間sij服從區(qū)間［0，50］上的均勻分布。算法求解環(huán)境為MATLAB 7.6.0.324，采用MATLAB語言編程；計算機(jī)CPU為Intel（R）Core（TM）2 Duo CPU，內(nèi)存為2G，主頻為3.00GHz。

在利用“最近鄰域與插入混合”求解初始解時，選擇參數(shù)α=0.4。在考慮擾動目標(biāo)相對于原目標(biāo)的單位成本時，用原目標(biāo)的上界與擾動目標(biāo)的上界

數(shù)值試驗里考慮三種典型情況：coef等于0.5：比較偏向于原目標(biāo)；coef等于1，原目標(biāo)和擾動目標(biāo)重要性相當(dāng)；coef等于2，比較偏向于擾動目標(biāo)。

由于問題（1）不存在同時優(yōu)化兩個目標(biāo)的最優(yōu)解，因此對于某一固定coef，由混合算法流程可知可求得分別以J1，J2，…，Jn為首個加工工件的n個排序解，如此構(gòu)成的初始種群有利于提高種群的多樣性。

在利用NSGA-II對初始種群進(jìn)行進(jìn)一步搜索時，采用MATLAB7.6.0.324優(yōu)化工具箱中的GAMULTIOBJ函數(shù)來實現(xiàn)。種群個體采用實數(shù)編碼方式，個體長度為工件個數(shù)n。對于某個由n個實數(shù)構(gòu)成的個體，采用類似于隨機(jī)密鑰表示法（random key representation）的方式將n個實數(shù)轉(zhuǎn)化為問題（1）的可行解——工件次序的置換［21］：令n個實數(shù)排列中最小的值對應(yīng)工件1，次小的對應(yīng)工件2，依次類推直至工件n。如果出現(xiàn)兩個實數(shù)相等的情況，令排列中位置較前的實數(shù)對應(yīng)標(biāo)號較小的工件。

遺傳算子中選擇操作采用“錦標(biāo)賽”策略，每次選取2個個體；交叉操作采用兩點交叉；變異操作中的函數(shù)為均勻分布函數(shù)，概率為0.01。種群每隔20代進(jìn)行遷移，遷移方向為前向，比例為0.2。種群中個體之間的距離計算采用工具箱函數(shù)DISTANCECROWDING。在具體參數(shù)設(shè)置上，種群規(guī)的比值來進(jìn)行度量，并用非負(fù)的系數(shù)coef來調(diào)節(jié)擾動目標(biāo)相對于原目標(biāo)的重要程度。η的具體計算公式如下：模設(shè)置為150，初始種群除“最近鄰域與插入混合”提供之外，由均勻分布產(chǎn)生；最優(yōu)有效前沿中個體保留比例為0.5；算法終止由遺傳代數(shù)來控制，設(shè)為100；剩余操作的參數(shù)均為默認(rèn)值。

4.3 算例結(jié)果對比

給定算例參數(shù)后，本部分比較不同工件個數(shù)和相對單位成本下混合算法和NSGA-II的性能。對于n-coef的每種參數(shù)組合，進(jìn)行30次運(yùn)算。

每次運(yùn)算按照均勻分布U［1，50］隨機(jī)生成工件的安裝時間。統(tǒng)計30次運(yùn)算中每個有效前沿指標(biāo)的平均值ave和樣本方差值var。對于某一指標(biāo)，令xi表示第i次運(yùn)算的指標(biāo)值，則ave=。ave反映了該指標(biāo)多次運(yùn)算的平均情況；而var反映了某算法下該指標(biāo)的穩(wěn)定情況，樣本方差值越小指標(biāo)越穩(wěn)定。工件個數(shù)為n等于50，coef分別為0.5，1和2時，30次運(yùn)算中一次運(yùn)算結(jié)果如圖3-圖4所示。

圖3左下方的藍(lán)色、紅色和粉色“實心圓點”折線表示混合算法在coef等于0.5，1，2時，分別由最近鄰域與插入混合單獨(dú)提供初始種群時求出的有效前沿?！靶翘枴闭劬€表示NSGA-II中初始種群完全隨機(jī)生成，而“三角形”折線表示NSGA-II初始種群中一個個體為1，2，…，n，剩余部分隨機(jī)生成。由圖3可以直觀看出，混合算法不同系數(shù)下求得的有效前沿中絕大部分解都支配單純NSGA-II求出的解。單純NSGA-II求出的解在多樣性方面要更優(yōu)，但是混合算法求出的解的原目標(biāo)和擾動目標(biāo)都要更小。

當(dāng)coef不同時，混合算法求出的有效前沿優(yōu)勢不同。coef等于0.5，1，2時求得的有效前沿中原目標(biāo)的平均值分別為704.5，780.5和967，擾動目標(biāo)的平均值分別為265.2，136和25.5。當(dāng)coef= 0.5時，藍(lán)色有效前沿優(yōu)勢在于左端的解原目標(biāo)值比較??；當(dāng)coef=1時，紅色有效前沿優(yōu)勢在于原目標(biāo)和擾動目標(biāo)比較折中；而當(dāng)coef=2時，粉色有效前沿優(yōu)勢在于擾動目標(biāo)值比較小。當(dāng)決策者可以明確對于原目標(biāo)和擾動目標(biāo)的不同偏好之后，使用混合算法可直接求出比較理想的解。

此外，從雙目標(biāo)優(yōu)化角度出發(fā)，為搜索到問題（1）更優(yōu)的有效前沿，綜合coef等于0.5，1，2時得到的三組解集構(gòu)成初始種群。綜合初始解的具體做法為：首先使用混合算法分別在coef等于0.5，1，2時由最近鄰域與插入混合求出三組解集，按一定比例選擇三組解集中最優(yōu)的解構(gòu)成初始種群。由于種群規(guī)模為150，當(dāng)n=50時，選擇比例為92%；當(dāng)n =100時，選擇比例為46%。對應(yīng)于圖3，“綜合初始解后混合算法”運(yùn)算結(jié)果如圖4中“圓圈形”折線所示。此時的有效前沿在解的多樣性和鄰近性兩方面都更優(yōu)。

為說明問題（1）有效前沿中原目標(biāo)和擾動目標(biāo)之間的制約關(guān)系，從有效前沿形狀的角度說明混合算法在對原目標(biāo)和擾動目標(biāo)進(jìn)行權(quán)衡決策，這里引入坡度來度量為降低擾動目標(biāo)需增加原目標(biāo)的程度［11］，計算公式如下：

當(dāng)坡度值大于1時，可近似說明擾動目標(biāo)的降低程度要高于原目標(biāo)的增加程度。圖4中有效前沿的坡度值為2.43。當(dāng)n等于50，100時，30次運(yùn)算結(jié)果的平均坡度分別為2.22，4.41。這說明本文設(shè)計算法可在不顯著提高原目標(biāo)的同時有效降低干擾事件的擾動，并且當(dāng)問題規(guī)模越大算法優(yōu)勢越明顯。除有效前沿的坡度之外，將混合算法（以“綜合初始解的混合算法”為例）與單純NSGA-II在n分別等于50，100時進(jìn)行如表1的對比，表中的值為30次運(yùn)算的平均值。由表1可知，混合算法的各項指標(biāo)都要優(yōu)于NSGA-II。圖3所示混合算法和NSGAII在采取“依次右移受擾工件集”的策略時效果相同（對應(yīng)有效前沿最右端的解），而混合算法的最低成本遠(yuǎn)小于NSGA-II（特別是問題規(guī)模較大時）。因此混合算法可為決策者提供更小的成本，供決策者選擇的余地更大。

圖3 有效前沿對比

此外比較最低成本對應(yīng)的擾動、平均成本和平均擾動可知，混合算法能夠以較小的成本達(dá)到較低的擾動。綜合坡度和表1可以說明面對干擾事件造成的成本和擾動的權(quán)衡決策，本文設(shè)計的算法可為決策者提供更多和更優(yōu)的選擇。

圖4 綜合初始解后的混合算法

4.4 算法收斂性和收斂速度比較分析

為從雙目標(biāo)優(yōu)化角度量化算法有效性，將“綜合初始解的混合算法”分別與四種方法進(jìn)行對比：單純NSGA-II，coef等于0.5，1，2時單獨(dú)構(gòu)成初始種群的混合算法。

采用4.1中針對有效解集的指標(biāo)計算結(jié)果如表2所示。（如圖3所示由于初始種群完全隨機(jī)生成時求出的有效前沿質(zhì)量比較差，這里采取對比的“單純NSGA-II”中的初始種群中一個個體為1，2，…，n，剩余部分隨機(jī)生成）

由表2可知，“綜合初始解的混合算法”的各項指標(biāo)的平均值和樣本方差值在大多數(shù)情況下要優(yōu)于對比項，說明“綜合初始解的混合算法”求得的有效解集不但質(zhì)量比較好，而且多次運(yùn)算中比較穩(wěn)定。

雖然“綜合初始解后的混合算法”在反映有效解集多樣性的ONVG和TS上要稍劣于NSGA-II以及coef=0.5時的混合算法，但混合算法在指標(biāo)（2 -4）的表現(xiàn)均優(yōu)于NSGA-II，這說明混合算法相比之下具有更好的收斂性?；旌纤惴ㄇ蟮昧擞行把馗苁諗坑谧顑?yōu)有效前沿。此外從指標(biāo)（6）也可以看出“綜合初始解后的混合算法”平均質(zhì)量更優(yōu)。另外，由圖3和圖4可以看出干擾事件發(fā)生之后，問題（1）的原目標(biāo)和擾動目標(biāo)之間存在相互制約關(guān)系，只能通過增大其中一個目標(biāo)來改進(jìn)另外一個。面對突發(fā)性干擾事件決策者如果只考慮原目標(biāo)進(jìn)行重排序，就會產(chǎn)生較大的擾動費(fèi)用從而使得新計劃可行性比較低。因此，決策者需要根據(jù)自身情況在原目標(biāo)和擾動目標(biāo)之間進(jìn)行權(quán)衡。綜上，混合算法可以求得問題（1）質(zhì)量比較好的有效前沿，可以比較有效地解決具有安裝時間的工件次序擾動問題。

對混合算法的收斂性進(jìn)行分析后，用算法運(yùn)行的CPU時間來度量算法的收斂速度?？紤]coef等于0.5，1，2以及綜合初始解后的混合算法各自的運(yùn)行時間，相對于初始種群完全隨機(jī)生成的單純NSGA-II的運(yùn)行時間。單純NSGA-II在n等于50和100的平均運(yùn)行時間分別為56.85和81.05單位CPU時間。圖5和圖6反映了30次運(yùn)算相對于單純NSGA-II，不同混合算法運(yùn)行時間的下降百分比，橫軸表示30次運(yùn)行試驗，縱軸表示混合算法相對于單純NSGA-II的運(yùn)行時間下降百分比。由圖5-6所示，除個別情況外，四種混合算法總體上收斂速度要等于或優(yōu)于單純NSGA-II，這種趨勢隨著問題規(guī)模由50增加到100而相對更加明顯。

表1 原目標(biāo)和擾動目標(biāo)權(quán)衡決策對比

圖5 n=50時間下降百分比

圖6 n=100時間下降百分比

表2 數(shù)值運(yùn)算結(jié)果對比分析

對此現(xiàn)象的解釋為盡管混合算法階段1增加了復(fù)雜度為O（n2）的初始運(yùn)算，但是由于初始運(yùn)算可以提供高質(zhì)量的初始種群，反而最終加快了算法收斂到質(zhì)量更好的有效前沿。綜合表2與圖5-6可以說明本文設(shè)計算法在收斂性和收斂速度上優(yōu)于單純NSGA-II，驗證了方法的有效性。

5 結(jié)語

本文針對制造業(yè)中普遍存在的和工件次序相關(guān)的安裝時間，集中研究了現(xiàn)實世界中不確定性導(dǎo)致的突發(fā)干擾事件的影響。在單機(jī)環(huán)境下，工件優(yōu)先級變動的影響主要體現(xiàn)在流程時間的變化和工件加工次序的變化，對此構(gòu)建了雙目標(biāo)干擾管理模型。結(jié)合模型中的雙目標(biāo)，設(shè)計了基于有效解的混合啟發(fā)式算法進(jìn)行了求解，在加工流程時間和工件的加工次序擾動和之間進(jìn)行了權(quán)衡。研究發(fā)現(xiàn)，問題的原目標(biāo)和擾動目標(biāo)之間存在相互制約關(guān)系，當(dāng)干擾事件發(fā)生時如果只考慮原目標(biāo)就會導(dǎo)致較大的擾動目標(biāo)。本文設(shè)計的算法可以在不顯著增加原目標(biāo)的前提下降低干擾事件的影響。另外，通過比較分析針對有效前沿的指標(biāo)發(fā)現(xiàn)，由于利用最近鄰域和插入混合可以構(gòu)成質(zhì)量優(yōu)良的初始種群，混合算法最終可以更快地收斂到優(yōu)良的有效前沿。進(jìn)一步的研究方向可集中在：

第一，考慮新的擾動度量方式，比如和工件的具體完工時間相關(guān)的目標(biāo)；第二，并行機(jī)生產(chǎn)環(huán)境下協(xié)同考慮生產(chǎn)和運(yùn)輸?shù)母蓴_管理問題等；第三，本文算

法有效性的驗證主要依靠于現(xiàn)有研究中常用的數(shù)值算例，通過調(diào)研在實際案例中獲取真實數(shù)據(jù)從而驗證方法的有效性是未來值得重點關(guān)注的問題。

［1］唐立新，黃琳.調(diào)整時間與順序相關(guān)的flowshop調(diào)度的精確算法［J］.系統(tǒng)工程學(xué)報，2002，17（04）：309-315.

［2］Kuo W H，Hsu C J，Yang D L.Some unrelated parallel machine scheduling problems with past-sequence-dependent setup time and learning effects［J］.Computers &Industrial Engineering，2011，61（1）：179-183.

［3］Wang Jianjun，Wang Jibo，Liu F.Parallel machines scheduling with a deteriorating maintenance activity［J］. Journal of the Operational Research Society，2011，62（10）：1898-1902.

［4］Hall N G，Potts C N.Rescheduling for new orders［J］. Operations Research，2004，52（3）：440-453.

［5］Qi Xiangtong，Bard J F，Yu Gang.Disruption management for machine scheduling：The case of SPT schedules［J］.International Journal of Production Economics，2006，103（1）：166-184.

［6］Hall N G，Potts C N.Rescheduling for job unavailability［J］.Operations Research，2010，58（3）：746-755.

［7］Zhao Chuanli，Tang Hengyong.Single machine scheduling with past-sequence-dependent setup times and deteriorating jobs［J］.Computers&Industrial Engineering，2010，59（4）：663-666.

［8］Cheng T，Lee W C，Wu C C.Scheduling problems withdeteriorating jobs and learning effects including proportional setup times［J］.Computers&Industrial Engineering，2010，58（2SI）：326-331.

［9］Bahalke U，Yolmeh A M，Shahanaghi K.Meta-heuristics to solve single-machine scheduling problem with sequence-dependent setup time and deteriorating jobs［J］. International Journal of Advanced Manufacturing Technology，2010，50（5-8）：749-759.

［10］Ouelhadj D，Petrovic S.A survey of dynamic scheduling in manufacturing systems［J］.Journal of Scheduling，2009，12（4）：417-431.

［11］Gurel S，Korpeoglu E，Akturk M S.An anticipative scheduling approach with controllable processing times［J］.Computers&Operations Research，2010，37（6）：1002-1013.

［12］Ozlen M，Azizoglu M.Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria［J］.Journal of the Operational Research Society，2011，62（1）：152-164.

［13］Lee C Y，Leung J，Yu Gang.Two machine scheduling under disruptions with transportation considerations［J］.Journal of Scheduling，2006，9（1）：35-48.

［14］Yuan Jinjiang，Mu Yundong.Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption［J］.European Journal of Operational Research，2007，182（2）：936-944.

［15］Yuan Jinjiang，Mu Yundong，Lu Lingfa，et al.Rescheduling with release dates to minimize total sequence disruption under a limit on the makespan［J］.ASIAPacific Journal of Operational Research，2007，24（6）：789-796.

［16］Al-Hinai N，Elmekkawy T Y.Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm［J］.International Journal of Production Economics，2011，132（2）：279-291.

［17］Pinedo M L.Scheduling：Theory，algorithms，and systems［M］.New York：Springer Science+Business Media，2008.

［18］張明璽，李昆鵬.混合離散差分進(jìn)化算法在單機(jī)批處理調(diào)度中的應(yīng)用［J］.中國管理科學(xué)，2010，8（04）：114-123.

［19］李鐵克，蘇志雄.煉鋼連鑄生產(chǎn)調(diào)度問題的兩階段遺傳算法［J］.中國管理科學(xué)，2009，17（05）：68-74.

［20］程八一，陳華平，王栓獅.基于微粒群算法的單機(jī)不同尺寸工件批調(diào)度問題求解［J］.中國管理科學(xué)，2008，16（03）：84-88.

［21］Li Binbin，Wang Ling.A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，2007，37（3）：576-591.

［22］張超勇，董星，王曉娟，等.基于改進(jìn)非支配排序遺傳算法的多目標(biāo)柔性作業(yè)車間調(diào)度［J］.機(jī)械工程學(xué)報，2010，46（11）：156-164.

［23］Srinivas N，Deb K.Muiltiobjective optimization using nondominated sorting in genetic algorithms［J］.Evolutionary Computation，1994，2（3）：221-248.

［24］Deb K，Pratap A，Agarwal S，et al.A fast and elitist multiobjective genetic algorithm：NSGA-II［J］.IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.

［25］饒衛(wèi)振，金淳，黃英藝.求解TSP問題的最近鄰域與插入混合算法［J］.系統(tǒng)工程理論與實踐，2011，31（8）：1419-1428.

［26］羅辭勇，陳民鈾，張聰譽(yù).采用循環(huán)擁擠排序策略的改進(jìn)NSGA-Ⅱ算法［J］.控制與決策，2010，25（02）：227 -231.

［27］畢曉君，肖婧.基于自適應(yīng)差分進(jìn)化的多目標(biāo)進(jìn)化算法［J］.計算機(jī)集成制造系統(tǒng)，2011，17（12）：2660-2665.

［28］張美華，李愛平，徐立云.基于Pareto最優(yōu)的多企業(yè)協(xié)同計劃調(diào)度優(yōu)化［J］.中國機(jī)械工程，2012，23（05）：563-569.

［29］Hall N G，Posner M E.Generating experimental data for computational testing with machine scheduling applications［J］.Operations Research，2001，49（6）：854 -865.

Machine Scheduling Disruption Management with Sequence Dependent Setup Times

LIU Feng1，WANG Jian-jun1，RAO Wei-zhen1，2，YANG De-li1
（1.Institute of Systems Engineering，Dalian University of Technology，Dalian 116023，China；2.Colledge of Economics and Managemet，Shandong University of Science and Technology，Qingdao 266590，China）

In this paper，a disruption management problem on single machine scheduling with sequence dependent setup times 1｜sij｜Cmaxis studied.It is originated from practical situations where jobs come from different job families，and during the implementation of initial schedule the priority of certain job would besuddenly upgraded，causing disruption to the original plan.This makes it necessary to consider jobs'sequence deviation from original plan during rescheduling，which is calculated based on job i's relative position to job j in the revised schedule.In this paper，a bi-objective rescheduling model is built，considering both Cmaxand sequence deviation.In order to effectively solve the model，local search is combined with global search and a two-stage approach is designed.In stage 1 construction heuristic based on mixed Nearest Neighbor and Insertion is used to obtain good initial solutions for stage 2 to make extension search along the Pareto front.Computational study shows that the proposed approach outperforms the widely applied NSGA-II in both proximity and diversity metrics.And for decision-makers，better decision alternatives could be provided for the trade-off between production cost and deviation of disruption.The research sets an example for applying hybrid metaheuristic to deal with disruption in machine scheduling and computational results could serve as comparison for further studies of this problem.

rescheduling；sequence disruption；bi-criterion；Pareto front；NSGA-II

C931

：A

1003-207(2014)01-0045-10

2011-09-27；

2013-03-19

國家自然科學(xué)基金資助項目（71271039，70902033）；新世紀(jì)優(yōu)秀人才支持計劃資助項目（NCET-13-0082）；教育部“創(chuàng)新團(tuán)隊發(fā)展計劃”項目（IRT1214）

劉鋒（1985—），男（漢族），河北石家莊人，大連理工大學(xué)系統(tǒng)工程研究所博士研究生，研究方向：服務(wù)干擾管理、智能優(yōu)化算法設(shè)計.