安裝時間與次序相關的生產調度干擾管理研究

劉 鋒，王建軍，饒衛振，2，楊德禮

（1.大連理工大學系統工程研究所，遼寧大連116023；2.山東科技大學經濟管理學院，山東青島266590）

安裝時間與次序相關的生產調度干擾管理研究

劉 鋒1，王建軍1，饒衛振1，2，楊德禮1

（1.大連理工大學系統工程研究所，遼寧大連116023；2.山東科技大學經濟管理學院，山東青島266590）

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

1 引言

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

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

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

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

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

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

2 問題描述

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

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

圖1 重置0時刻

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

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

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

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

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

3 問題求解

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

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

混合算法主要分兩階段進行：

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

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

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

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

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

在給出混合算法的流程之后，對其計算復雜性進行分析。混合算法的階段1是構建型的啟發式方法，階段2是基于種群進化的啟發式方法。

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

圖2 混合算法流程

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

令插入算法（insertion，IN）完成第k步構造的計算量記為Ω（k）。第k步首先從其他n-1個工件中判斷出n-k個未加工工件，然后計算當前工件分別插入當前k-1個位置使目標增加的程度（i插入j、h之間，增加為：sji+sih-sjh+η·Dji+η·Dihη·Djh），在k-1個增加值中最小值對應的位置即為待插入工件的最佳插入位置，最后更新加工時間表完成第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處取得。由于算法復雜度僅由計算量多項式的最高次確定，所以第一階段的算法復雜度為O（n2）。

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

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

4 數值試驗

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

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

4.1 有效前沿指標

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

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

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

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

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

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

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

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

4.2 算例參數

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

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

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

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

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

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

4.3 算例結果對比

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

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

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

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

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

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

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

圖3 有效前沿對比

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

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

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

為從雙目標優化角度量化算法有效性，將“綜合初始解的混合算法”分別與四種方法進行對比：單純NSGA-II，coef等于0.5，1，2時單獨構成初始種群的混合算法。

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

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

雖然“綜合初始解后的混合算法”在反映有效解集多樣性的ONVG和TS上要稍劣于NSGA-II以及coef=0.5時的混合算法，但混合算法在指標（2 -4）的表現均優于NSGA-II，這說明混合算法相比之下具有更好的收斂性。混合算法求得了有效前沿更能收斂于最優有效前沿。此外從指標（6）也可以看出“綜合初始解后的混合算法”平均質量更優。另外，由圖3和圖4可以看出干擾事件發生之后，問題（1）的原目標和擾動目標之間存在相互制約關系，只能通過增大其中一個目標來改進另外一個。面對突發性干擾事件決策者如果只考慮原目標進行重排序，就會產生較大的擾動費用從而使得新計劃可行性比較低。因此，決策者需要根據自身情況在原目標和擾動目標之間進行權衡。綜上，混合算法可以求得問題（1）質量比較好的有效前沿，可以比較有效地解決具有安裝時間的工件次序擾動問題。

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

表1 原目標和擾動目標權衡決策對比

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

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

表2 數值運算結果對比分析

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

5 結語

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

第一，考慮新的擾動度量方式，比如和工件的具體完工時間相關的目標；第二，并行機生產環境下協同考慮生產和運輸的干擾管理問題等；第三，本文算

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

［1］唐立新，黃琳.調整時間與順序相關的flowshop調度的精確算法［J］.系統工程學報，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］.中國管理科學，2010，8（04）：114-123.

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

［20］程八一，陳華平，王栓獅.基于微粒群算法的單機不同尺寸工件批調度問題求解［J］.中國管理科學，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］.機械工程學報，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］饒衛振，金淳，黃英藝.求解TSP問題的最近鄰域與插入混合算法［J］.系統工程理論與實踐，2011，31（8）：1419-1428.

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

［27］畢曉君，肖婧.基于自適應差分進化的多目標進化算法［J］.計算機集成制造系統，2011，17（12）：2660-2665.

［28］張美華，李愛平，徐立云.基于Pareto最優的多企業協同計劃調度優化［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

國家自然科學基金資助項目（71271039，70902033）；新世紀優秀人才支持計劃資助項目（NCET-13-0082）；教育部“創新團隊發展計劃”項目（IRT1214）

劉鋒（1985—），男（漢族），河北石家莊人，大連理工大學系統工程研究所博士研究生，研究方向：服務干擾管理、智能優化算法設計.