干擾管理在生產(chǎn)調(diào)度中的應(yīng)用綜述

唐海波，葉春明，馬慧民，吳 斌

（1.上海電機學(xué)院 商學(xué)院，上海 201306；2.上海理工大學(xué) 管理學(xué)院，上海 200093）

干擾管理在生產(chǎn)調(diào)度中的應(yīng)用綜述

唐海波1，葉春明2，馬慧民1，吳 斌1

（1.上海電機學(xué)院 商學(xué)院，上海 201306；2.上海理工大學(xué) 管理學(xué)院，上海 200093）

闡述了干擾管理在生產(chǎn)調(diào)度中的應(yīng)用的相關(guān)研究成果。介紹了干擾產(chǎn)生的源頭、干擾管理在生產(chǎn)調(diào)度中的表現(xiàn)形式、干擾管理在調(diào)度中的解決策略以及效率評價等一系列研究成果。界定了干擾管理在生產(chǎn)調(diào)度中的定義及其運作流程，給干擾管理在生產(chǎn)調(diào)度中進一步發(fā)展提供了借鑒。

干擾管理；生產(chǎn)調(diào)度；調(diào)度策略；調(diào)度目標(biāo)；預(yù)測反應(yīng)式調(diào)度

人類生活的客觀世界中存在的諸多不確定性，使人們處于一種變化的環(huán)境中。各種不確定性給人和事帶來不同程度的影響和干擾，使原先擬定好的處理步驟和計劃變得混亂甚至不可行，使整個系統(tǒng)變得不正常而陷入低效率的運行中。隨著人類認識世界運行規(guī)律的能力的提高，人們開始主動規(guī)避或在事件發(fā)生后積極采取措施降低并消除不確定事件的消極影響，這樣就產(chǎn)生了的干擾管理（Disruption Management），即當(dāng)不確定的干擾事件發(fā)生后，需要及時處理其對系統(tǒng)的影響，以盡可能小的代價盡快地恢復(fù)系統(tǒng)的正常運行。

干擾管理一經(jīng)提出，就很快在工業(yè)、醫(yī)療衛(wèi)生、公共安全、服務(wù)業(yè)等領(lǐng)域得到廣泛應(yīng)用。在學(xué)術(shù)界，干擾管理［1］3－5定義為在計劃開始階段，用優(yōu)化模型和求解算法得出一個好的運行計劃；計劃實施中，由于內(nèi)、外部不確定因素導(dǎo)致干擾事件的發(fā)生，使原計劃變得不可行，需要實時產(chǎn)生新計劃。新計劃要考慮到原來的優(yōu)化目標(biāo)，同時又要使干擾帶來的副作用最小化。也有學(xué)者認為干擾管理需要根據(jù)實際問題和干擾事件的性質(zhì)建立相應(yīng)的干擾管理模型，快速、及時地給出處理干擾事件的最優(yōu)調(diào)整方案；該調(diào)整方案是以原來的狀態(tài)為基礎(chǔ)，快速生成對系統(tǒng)擾動最小的調(diào)整方案，并適當(dāng)考慮了費用問題，但并非費用最省。

調(diào)度問題是將稀缺的資源分配給在一定時間內(nèi)的不同任務(wù)，其目的是優(yōu)化一個或多個目標(biāo)，屬于組合優(yōu)化問題，其中多數(shù)屬于NP難題。以往的研究大多集中在理想加工環(huán)境下的調(diào)度問題上，在生產(chǎn)過程中不考慮干擾的發(fā)生，而當(dāng)干擾出現(xiàn)時進行重新調(diào)度，忽視了對原調(diào)度性能的影響，對原調(diào)度性能產(chǎn)生較大的擾動。隨著制造業(yè)規(guī)模越來越龐大，系統(tǒng)中的動態(tài)不確定因素越來越多，對系統(tǒng)的性能指標(biāo)要求也越來越全面，需要采用干擾管理策略消除這些不確定因素的影響。學(xué)者Clausen等［2］首先提出了干擾管理，并用來應(yīng)對生產(chǎn)過程中的突發(fā)事件，將干擾限定在使變化回歸到最初計劃這一基本目標(biāo)之上，目標(biāo)是使整個系統(tǒng)的擾動最小。在此之前，許多學(xué)者的研究成果也涉及含有干擾管理理念的一些實質(zhì)性內(nèi)容。Norbis等［3］針對資源受約束的調(diào)度問題，在考慮諸如資源供應(yīng)變化、新工件的到達或交貨期及預(yù)計處理時間的改變等事件發(fā)生時，采用半動態(tài)的處理方法，制定基于靜態(tài)調(diào)度基礎(chǔ)上的互動的設(shè)置，提出一個多層次、多優(yōu)先級的啟發(fā)式算法以權(quán)衡調(diào)度的多種衡量目標(biāo)。Bean等［4］研究了運用預(yù)調(diào)度策略預(yù)先操作，當(dāng)生產(chǎn)調(diào)度中遇到干擾時，重新構(gòu)造部分調(diào)度用以產(chǎn)生匹配的原調(diào)度系統(tǒng)，求得給定條件下的最優(yōu)，實驗證明匹配調(diào)度方法的優(yōu)點，但未在產(chǎn)生的計劃調(diào)度中加入未來可能的干擾信息因素。Akturk等［5］采用匹配算法解決了Flow Shop調(diào)度環(huán)境下遇到的一個機器故障的問題。Abumaizar等［6］提出了一個在Job Shop調(diào)度環(huán)境下的算法，解決了遇到隨機擾動情況下調(diào)度的生成問題，并與完全重調(diào)度及右移調(diào)度進行性能上的比較，通過基準(zhǔn)生產(chǎn)調(diào)度算例驗證了采用針對性部分改變原調(diào)度的算法的性能優(yōu)于完全重新產(chǎn)生新的調(diào)度及右移調(diào)度的性能。Eric和Gunter［7－8］分別就以前學(xué)者的相關(guān)研究作了詳盡的綜述。

1 干擾源分析

在企業(yè)干擾管理方面，常見的事件可分為以下7種情況［1］31－50：生產(chǎn)環(huán)境的變化；不可預(yù)見的事件；系統(tǒng)參數(shù)的改變；資源獲得情況的改變；新的約束；系統(tǒng)表現(xiàn)的不確定性；新的考慮。作為企業(yè)核心的生產(chǎn)調(diào)度所面臨的干擾，均是與上述干擾事件相對應(yīng)的干擾源。這些干擾源會引起整個生產(chǎn)調(diào)度系統(tǒng)不穩(wěn)定，引發(fā)生產(chǎn)系統(tǒng)效率下降，促使管理者采取措施應(yīng)對干擾的發(fā)生。Vieira等［9］收集了最常見的干擾源：① 機器故障；② 緊迫工件到達；③工件加工時間改變及取消；④ 交貨期改變；⑤ 材料短缺或者到達延誤；⑥ 工件優(yōu)先權(quán)的改變；⑦質(zhì)量問題或者返工；⑧ 對加工工期估計不足和估計過剩；⑨ 工人曠工等。此外，還包括超時及加工過程中的分包、加工過程改變及重新安排工序、機器替換、用電受限、安裝時間以及設(shè)備批準(zhǔn)發(fā)放等干擾源。

干擾源形式多樣，涉及內(nèi)容廣泛，但筆者認為可根據(jù)干擾源的來源分為由生產(chǎn)系統(tǒng)內(nèi)部因素波動產(chǎn)生的干擾和由生產(chǎn)系統(tǒng)以外因素產(chǎn)生的干擾。生產(chǎn)系統(tǒng)內(nèi)部因素由機器、加工時間、加工程序、工件材料以及人員用工情況等構(gòu)成調(diào)度系統(tǒng)的因素。這些因素包括人、機器、工件以及相互之間的相互關(guān)系；生產(chǎn)系統(tǒng)以外的因素包含了生產(chǎn)系統(tǒng)外部不能由生產(chǎn)系統(tǒng)控制的因素，主要包括市場需求改變因素、能源控制、客戶原因等。干擾源的分類如表1所示。

表1 干擾源簡單分類表Table 1 Classification of interference sources

2 干擾管理在生產(chǎn)調(diào)度中應(yīng)用

生產(chǎn)調(diào)度問題基本上由機器數(shù)量、種類、環(huán)境、工件或任務(wù)的性質(zhì)及目標(biāo)值函數(shù)組成。機器數(shù)量、種類、環(huán)境有多種變化，任務(wù)或工件的約束更是錯綜復(fù)雜，再加上度量不同指標(biāo)的目標(biāo)函數(shù)，從而形成了種類繁多的生產(chǎn)調(diào)度模型。目前，學(xué)術(shù)界普遍采用Graham等［10］提出的三參數(shù)表達方法，即α，β，γ表示法，用以簡化一個調(diào)度問題的表示，其中，α表示機器的數(shù)量、類型和環(huán)境；β表示工件的加工性質(zhì)、加工要求和限制，資源的種類、數(shù)量和對加工影響等約束條件，它可同時包含多項；γ表示需要優(yōu)化的目標(biāo)函數(shù)。根據(jù)調(diào)度系統(tǒng)的機器的復(fù)雜度，可分為單機、多臺并行機、Flow Shop，Job Shop 4種類型。

2.1 單機情況

單機是生產(chǎn)調(diào)度中最簡單、最常見的調(diào)度方式，也是研究其他類型調(diào)度的基礎(chǔ)。Qi等［11］討論了生產(chǎn)調(diào)度系統(tǒng)中部分工件被處理后，一臺機器遭遇隨機或預(yù)期干擾時，通過更新原調(diào)度系統(tǒng)，以適應(yīng)干擾事件對調(diào)度帶來的變動。他們將干擾事件納入到更新后的調(diào)度目標(biāo)范圍內(nèi)，建立原調(diào)度和更新后調(diào)度之間的擾動費用偏差模型。模型的衡量標(biāo)準(zhǔn)有2個：① 原調(diào)度目標(biāo)函數(shù)；② 原調(diào)度目標(biāo)函數(shù)與更新后調(diào)度目標(biāo)函數(shù)的偏差。運用動態(tài)規(guī)劃和啟發(fā)式算法的方法對模型求解，找出在原調(diào)度目標(biāo)函數(shù)基礎(chǔ)上與更新后調(diào)度目標(biāo)函數(shù)偏差最小的最優(yōu)調(diào)度方案。引入先干擾管理和后干擾管理兩種不同的干擾管理策略，解決調(diào)度系統(tǒng)面臨機器故障和工件工期增減兩種干擾時，基于原調(diào)度的最優(yōu)分派調(diào)度規(guī)則SPT（the shortest processing time rule），通過修正SPT規(guī)則求得最優(yōu)調(diào)度方案。

（1）采用RS－SPT（右移SPT）最優(yōu)解決

3類調(diào)度；

（2）采用LS－SPT或 ORI－SPT（左移SPT或原先的SPT）最優(yōu)解決

3類調(diào)度；

（3）采用 TWO－SPT和 RS－SPT（雙SPT 和右移SPT）中表現(xiàn)最好的最優(yōu)解決

3類的調(diào)度；

（4）采 用 INS－SPT 或 ORI－RS－SPT（插 入SPT或原來的右移SPT）最優(yōu)解決

3類的調(diào)度。

其中，Δm為機器故障的干擾；pk±δ為第k個工件加工時間增加或減少的時間δ；pred－mgt和post－mgt分別為先干擾管理和后干擾管理；Di＝Ei＋Ti，其他均為標(biāo)準(zhǔn)標(biāo)識。

Lee等［12］研究了一個干擾事件在確切的時間點發(fā)生，且干擾以概率Pa持續(xù)a時間段的情況下，對單機上未完成工件（分為可恢復(fù)工件與不可恢復(fù)工件）的干擾管理，運用動態(tài)規(guī)劃方法求解目標(biāo)函數(shù)分別為最小化加權(quán)完工時間的期望與最小化最大延遲時間期望兩類調(diào)度問題。

Hall等［13］研究了在單機調(diào)度環(huán)境下，在新的工件到達時，通過限定新到達的工件位置變動數(shù)和推遲時間數(shù)及它們之和作為限定調(diào)度的因素，建立用最大延遲時間、加工總完成時間與前者加權(quán)作為目標(biāo)函數(shù)的調(diào)度模型。通過權(quán)衡原有工件的調(diào)度成本和插入新工件后的干擾成本，找出最優(yōu)調(diào)度方案。文獻［13］中還擴展研究了新工件重復(fù)到達這種多干擾因素下的調(diào)度模型。其解決的調(diào)度模型表示為

慕運動［14］在文獻［13］的基礎(chǔ)上，分別在加入相容工件（即在生產(chǎn)過程中，加工時間越長、交貨時間也越長的情形）及到達時間的限制情況下，進行了新工件到達對單機調(diào)度系統(tǒng)的干擾研究。Zhao等［15］則加入線性退化加工時間的工件限制，并將研究擴展到2個單機調(diào)度環(huán)境下，調(diào)度系統(tǒng)面臨一組新工件到達的干擾，運用多項式算法尋找最小總完工時間的最優(yōu)調(diào)度方案。Yuan等［16］加入了工件到達時間限制，研究了目標(biāo)函數(shù)為最大工件完工時間的情況，用多項式算法解決

這些調(diào)度問題。由于加入了工件調(diào)度時間，故必須考慮到機器空閑時間，這增加了問題的復(fù)雜性。

Leus等［17］研究了單機系統(tǒng)遇到單工件擾動時的復(fù)雜性問題，證明了目標(biāo)函數(shù)為初始加工時間偏移期望的單機擾動問題的復(fù)雜性是普通的NP－h(huán)ard；此外，還證明了附加了不等的準(zhǔn)備時間限制及帶優(yōu)先級限制的單機擾動問題的復(fù)雜性是強NP－h(huán)ard。Peter等［18］提出了一種使用實時信息的框架來改善調(diào)度決策。通過將實時信息反饋給調(diào)度決策系統(tǒng)，以效用和穩(wěn)定性能來權(quán)衡遭到擾動修訂后的調(diào)度和按原計劃執(zhí)行的靜態(tài)調(diào)度，并用實例闡明提出的框架體系如何在單機調(diào)度中利用實時信息選擇應(yīng)對干擾的策略。Francisco等［19］研究了單機情況下，加入共同的最后完工期的限制，目標(biāo)函數(shù)是使計劃調(diào)度工件開始時間和實際工件開始時間的偏差最小，采用兩種啟發(fā)式演算法求解單工件發(fā)生干擾時調(diào)度最優(yōu)的問題。

2.2 平行機情況

平行機可被看作是雙單機環(huán)境。在單機調(diào)度環(huán)境下的研究成果可以比較容易擴展到平行機環(huán)境中。Qi等［11］將應(yīng)用結(jié)果擴展到平行機環(huán)境中，采用干擾管理修改分派規(guī)制SPT，應(yīng)對雙機調(diào)度中單機器遭遇機器故障和單工件加工時間增減的干擾。Lee等［20］研究了雙機調(diào)度情形下，遭遇意外的干擾事件，考慮剩余未完成工件的處理問題。根據(jù)實際情況提出2種處理方法：① 將未完成的工件安排到其他機器上，此時需要額外的運輸時間和費用；② 等待受干擾的機器恢復(fù)后繼續(xù)對工件進行處理。針對上述解決方案，建立了目標(biāo)函數(shù)：使初始調(diào)度的費用函數(shù)、可能的運輸費用及與原調(diào)度偏離而產(chǎn)生的干擾費用總和最小的數(shù)學(xué)模型，最后通過多項式算法和偽多項式算法求出最優(yōu)調(diào)度方案。Lee等［21］在文獻［12］的基礎(chǔ)上，將干擾管理推廣到平行機的應(yīng)用中，提供偽多項式時間算法尋找在持續(xù)一段時間內(nèi)機器全部不能使用時平行機調(diào)度系統(tǒng)的最優(yōu)。Leus等［17］還證明了平行機調(diào)度環(huán)境下單工件干擾問題復(fù)雜度屬于強 NP－h(huán)ard。

Petrovic等［22］提出針對平行機調(diào)度系統(tǒng)遇到不確定干擾時的一種新的以模糊邏輯為基礎(chǔ)的決策支持系統(tǒng)。他們將此應(yīng)用于陶器廠的實際生產(chǎn)調(diào)度中，提出一個預(yù)測反應(yīng)調(diào)度模型，分兩步對系統(tǒng)進行調(diào)度：首先建立一個具有吸收干擾的預(yù)測調(diào)度方案，當(dāng)干擾事件產(chǎn)生的影響過大時，采用重調(diào)度的反應(yīng)式策略方案。在甄別干擾強度并決定調(diào)度決策時，依靠使用標(biāo)準(zhǔn)模糊集和二級模糊集描述原材料短缺的干擾源（主要表現(xiàn)為原材料的短缺數(shù)及持續(xù)時間）。生產(chǎn)實驗證明了預(yù)測生產(chǎn)調(diào)度策略的有效性以及采用模糊推理生成適當(dāng)?shù)恼{(diào)度策略安排的合理性。Duenas等［23］在此基礎(chǔ)上，繼續(xù)研究了預(yù)測反應(yīng)式調(diào)度策略的應(yīng)用。

Vieira［24］等針對并行機系統(tǒng)中，不同類型的工件在動態(tài)到達且具有不同的安裝時間的情況下，提出了新的分析模型用以預(yù)測3種重調(diào)度的執(zhí)行質(zhì)量和效率，平衡不同的衡量方法。Barua等［25］研究了模擬半導(dǎo)體晶片設(shè)施的生產(chǎn)調(diào)度系統(tǒng)遭遇隨機的機器故障的干擾時，通過對幾種分派規(guī)則與他們提出的全局調(diào)度算法應(yīng)對干擾影響的性能比較，分析了在不同的干擾層次下，不同調(diào)度策略的優(yōu)缺點，尋找在特定環(huán)境下能使目標(biāo)函數(shù)為最大、加工延遲時間最小的調(diào)度策略方案。

2.3 Flow Shop及Job Shop情況

由于Flow Shop及Job Shop的調(diào)度環(huán)境較為復(fù)雜，干擾管理帶來的影響也會非常復(fù)雜。Abumaizar［6］等提出了生產(chǎn)調(diào)度中Job Shop遇到多個干擾源時的解決方案。Lee等［26］研究了雙機器Flow Shop環(huán)境中，一臺機器不可用的干擾情況，采用偽多項式的動態(tài)規(guī)劃算法解決問題，證明這種干擾問題屬于NP－h(huán)ard；還分別給出兩臺機器上出現(xiàn)干擾問題時的最壞情況誤差界，得出在雙機器Flow Shop的不同單機之間發(fā)生干擾時不能互相替換的結(jié)論。Akturk等［27］提出一個調(diào)度策略和匹配時間點，部分修改原先的Flow Shop調(diào)度以匹配目前的生產(chǎn)計劃狀況，并通過設(shè)計一個反饋機制提高調(diào)度的質(zhì)量和穩(wěn)定。

Mehta［28］等認為，Job Shop調(diào)度中的干擾會使工期延長或使基于原來的生產(chǎn)計劃的調(diào)度不可行，因此提出了預(yù)測型調(diào)度用于吸收干擾保持良好的調(diào)度性能而不影響生產(chǎn)的外部活動（如材料采購、機器的預(yù)防性維護等）。他們提出的預(yù)測型調(diào)度將空閑時間插入調(diào)度中，用以吸收機器故障帶來的影響，而空閑時間的插入數(shù)量和位置取決于機器故障、修理分布以及預(yù)測型調(diào)度結(jié)構(gòu)，至于干擾對原調(diào)度計劃的影響可以通過測量工件的總完工時間在原計劃調(diào)度和預(yù)測型調(diào)度之間的偏移得出。Shafaei等［29－30］研究了在動態(tài)Job Shop環(huán)境下，以成本為性能測量工具，尋找最優(yōu)調(diào)度規(guī)則，研究重新調(diào)度間隔對性能的影響以及調(diào)度規(guī)則的健壯性問題。

Ihsan［31］等在柔性制造系統(tǒng)（Flexible Manufacture System，F(xiàn)MS）調(diào)度環(huán)境下，為應(yīng)對機器故障及加工時間改變的干擾，分別研究了在線調(diào)度和離線調(diào)度，并研究了重調(diào)度頻率和其他調(diào)度參數(shù)之間的關(guān)系。Sanjay等［32］在FMS調(diào)度環(huán)境下，建立了一個以知識為基礎(chǔ)的智能決策系統(tǒng)，以應(yīng)對諸如機器故障、產(chǎn)量變化及緊急工件等干擾情況，通過實驗結(jié)果的分析識別顯著的影響因素以及它們之間的相互關(guān)系。

3 干擾管理的調(diào)度策略

由于考慮了開始調(diào)度后不確定干擾的影響，故干擾管理中的調(diào)度策略不僅要快速響應(yīng)變化，還要保持良好的調(diào)度性能。文獻［33］中總結(jié)了動態(tài)調(diào)度策略中有兩類調(diào)度策略符合干擾管理的要求，它們根據(jù)是否對處理未來可能的干擾因素產(chǎn)生影響進行預(yù)防性準(zhǔn)備，分為完全反應(yīng)式和預(yù)測反應(yīng)式調(diào)度策略。

3.1 完全反應(yīng)式調(diào)度

完全反應(yīng)式調(diào)度是根據(jù)在決策時刻的可得信息決定采用某種策略來調(diào)度工件，一般采用分派規(guī)則或其他的啟發(fā)式方法來對等待加工的工件按照優(yōu)先權(quán)順序排隊。當(dāng)調(diào)度系統(tǒng)遭遇干擾時，通過反饋方式將信息傳送給調(diào)度決策機制，然后由調(diào)度決策機制決定調(diào)度規(guī)則。實質(zhì)上這是一種在線調(diào)度方式，其處理過程是當(dāng)機器空閑時，從已經(jīng)按分派規(guī)則以某種指標(biāo)排好順序的排隊工件中選擇一個執(zhí)行。通常，分派規(guī)則以加工時間和交貨期為依據(jù)，信息處理量少，計算量很小，反應(yīng)迅速。當(dāng)生產(chǎn)系統(tǒng)遭遇干擾時，調(diào)度決策的變動基于生產(chǎn)調(diào)度系統(tǒng)的當(dāng)前狀態(tài)，故完全反應(yīng)式調(diào)度與實時信息獲取密切相關(guān)。文獻［18］中建立了使用實時信息來應(yīng)對生產(chǎn)中干擾的一般性框架，并根據(jù)實時信息選擇合適的調(diào)度規(guī)則，通過在不同干擾因素時的表現(xiàn)決定調(diào)度規(guī)則的選擇。Sun等［34］引入一個動態(tài)反應(yīng)式調(diào)度策略，針對不同的干擾狀況，采用不同的調(diào)度規(guī)則最優(yōu)應(yīng)對。由于完全反應(yīng)式調(diào)度策略完全依賴于反饋機制的性能，而當(dāng)反饋機制不能反映調(diào)度系統(tǒng)面臨的狀態(tài)時，整個調(diào)度系統(tǒng)的性能就會受到很大的影響。

3.2 預(yù)測反應(yīng)式調(diào)度

預(yù)測反應(yīng)式調(diào)度是干擾管理在調(diào)度中的常用策略［11，22－23］，它可分成2個步驟：① 不考慮生產(chǎn)調(diào)度系統(tǒng)未來的干擾事件，只根據(jù)當(dāng)前生產(chǎn)目標(biāo)生成最優(yōu)的預(yù)調(diào)度規(guī)則；② 在遭遇干擾時更新調(diào)度響應(yīng)干擾以改善調(diào)度性能。該方法的關(guān)鍵在于判斷是否需要對干擾進行調(diào)度和采用何種方式進行調(diào)度。Yamamoto等［35］提出了一個三階段策略管理干擾給調(diào)度系統(tǒng)帶來的影響：① 計劃階段。根據(jù)所有可獲得的生產(chǎn)信息在新的調(diào)度周期開始前生成一個預(yù)調(diào)度，從而為給定時段內(nèi)的生產(chǎn)提供必要的信息。② 控制階段。每當(dāng)有新的工序開始加工或完成時，對比實際調(diào)度與初始調(diào)度之間的差別。③ 調(diào)整調(diào)度階段。考慮到系統(tǒng)的干擾現(xiàn)狀修改原調(diào)度，如新產(chǎn)品到達、機器故障等干擾事件的發(fā)生。

Vieira等［9］將預(yù)測反應(yīng)式調(diào)度策略分為3類調(diào)度方式：周期性、事件驅(qū)動與混合決策。周期性調(diào)度以滾動時域為基礎(chǔ)，周期性地給任務(wù)分配資源并執(zhí)行調(diào)度。很多工業(yè)過程中的調(diào)度都是周期性的，特別是在無法獲取調(diào)度系統(tǒng)狀態(tài)實時監(jiān)測數(shù)據(jù)的情況下，生產(chǎn)管理人員根據(jù)需要采集控制系統(tǒng)的所有可得信息來周期性地生成調(diào)度，并執(zhí)行到下一個計劃時段的到來，期間不做任何修改。周期性調(diào)度比連續(xù)調(diào)度具有更好的調(diào)度穩(wěn)定性，但是當(dāng)系統(tǒng)狀態(tài)遭遇到干擾時，這種調(diào)度決策可能無法保持良好的性能。

對事件驅(qū)動調(diào)度而言，調(diào)度系統(tǒng)可以重復(fù)執(zhí)行或針對單個事件的發(fā)生進行調(diào)整。這是克服干擾對生產(chǎn) 調(diào) 度 影 響 的 主 要 方 法［11－13，22－23］。 針 對 干擾事件的驅(qū)動，Vieira等［36］提出了新到達的等待工件數(shù)目達到一定閾值引發(fā)調(diào)度的事件驅(qū)動。Bierwirth等［37］研究了一旦新工件到達就觸發(fā)重調(diào)度的情況。對于較大的調(diào)度系統(tǒng)而言，干擾因素會很多，系統(tǒng)可能一直處于重復(fù)驅(qū)動狀態(tài)，因此，系統(tǒng)的穩(wěn)定性無法得到保障。如何找到對干擾的可控管理和必需更新原有調(diào)度之間的閾值是事件驅(qū)動型調(diào)度的難點。

混合調(diào)度融合了前兩種調(diào)度。在沒有特定干擾事件發(fā)生時，周期性地調(diào)整調(diào)度；當(dāng)特定事件發(fā)生時，引發(fā)針對性調(diào)度修改及重新調(diào)度。通常，引發(fā)調(diào)度的特定事件包括上文所列舉的干擾源，但這些干擾源并不一定能引發(fā)調(diào)度的干擾管理或重新調(diào)度，還要取決于干擾對生產(chǎn)調(diào)度產(chǎn)生的沖擊大小。Church等［38］提出當(dāng)每個新的周期時刻到來或重大干擾發(fā)生時更新原調(diào)度，結(jié)果表明，混合調(diào)度決策比單一的周期調(diào)度和連續(xù)調(diào)度取得的效果更好。

4 干擾管理在調(diào)度中的評價指標(biāo)

評價調(diào)度性能的指標(biāo)有很多，但適用于干擾管理的主要有兩類：調(diào)度的穩(wěn)定性和調(diào)度的成本。Qi等［12］采用與初始調(diào)度的偏差作為干擾管理的穩(wěn)定性指標(biāo)，偏差最小即調(diào)度性能改變最小，那么穩(wěn)定性也就越好。Hall等［13］提出的限定新到達的工件位置變動數(shù)、推遲時間數(shù)及它們之和的限制也可以作為干擾中調(diào)度的穩(wěn)定性的衡量指標(biāo)。此外，Wu等［39］提出了兩種描述調(diào)度變化對系統(tǒng)性能影響的非正則評價指標(biāo)：新調(diào)度與原調(diào)度開始時間的絕對偏差；新調(diào)度與原調(diào)度之間順序的差異。這兩種非正則評價指標(biāo)也可作為調(diào)度的穩(wěn)定性的衡量標(biāo)準(zhǔn)。

調(diào)度成本的衡量方式較多樣，除標(biāo)準(zhǔn)的以時間為成本的衡量方式外，還有綜合成本，即包括時間、材料成本、庫存成本等因素的成本。Shafaei等［29］采用了包括調(diào)度前的費用及調(diào)度運行中的費用加上可能延時的費用組成了一個綜合成本，以衡量系統(tǒng)存在干擾時的調(diào)度規(guī)則的優(yōu)劣。

5 結(jié)論和展望

通過對干擾管理在調(diào)度中的應(yīng)用綜述可見：①干擾管理的應(yīng)用是動態(tài)調(diào)度方法中的一種。② 干擾管理在調(diào)度中的應(yīng)用，其方法與重調(diào)度的部分方法相仿，但有所區(qū)別。③ 性能測量上，采用變動后的調(diào)度與原計劃調(diào)度的衡量值的偏移量作為方法的評判標(biāo)準(zhǔn)，有助于找到對整個調(diào)度系統(tǒng)干擾沖擊最小的調(diào)整方案。

近幾年來，干擾管理的研究進展較快，但在生產(chǎn)調(diào)度領(lǐng)域的應(yīng)用并不多，筆者認為可以在3個方面進行研究：① 分析各種干擾源對生產(chǎn)調(diào)度系統(tǒng)的深層次的影響，并根據(jù)相同的影響的內(nèi)在特征進行歸類；② 研究干擾管理與重調(diào)度的關(guān)系，區(qū)分在何種干擾影響下，采用何種反應(yīng)方式將非常關(guān)鍵，即找到區(qū)分干擾管理與重調(diào)度的閥值；③進一步健全和豐富干擾管理在調(diào)度中特有的建模方法、算法以及評價體系。

［1］ Yu Gang，Qi Xiangtong.Disruption Management：Framework，Models and Applications［M］.Singapore：World Scientific Publishing Co.，2004.

［2］ Clausen J，Larsen J，Larsen A，et al.Disruption management：Operations research between planning and execution［J］.OR／MS，2001 ，28（5）：40－43.

［3］ Norbis M I，Smith J M.A multi－objective multilevel heristic for dynamic resource constrained scheduling problems［J］.European Journal of Operational Research，1988，33（1）：30－41.

［4］ Bean J C，Birge J R，Mittenthal J，et al.Matchup scheduling with multiple resources，release dates and disruptions［J］.Operations Research，1991，39（3）：470－483.

［5］ Akturk M S，Gorgulu E.Match－up scheduling under a machine breakdown［J］.European Journal of Operational Research，1999，112（1）：81－97.

［6］ Abumaizar R J，Svestka J A.Rescheduling job shops under random disruptions［J］.International Journal Production Research，1997，35 （7）：2065－2082.

［7］ Sanlavillel E，Schmidt G.Machine scheduling with availability constraints［J］.Acta Informatica 1998，35（9）：795－811.

［8］ Schmidt G.Scheduling with limited machine availability［J］.European Journal of Operational Research 2000，121（1）：1－15.

［9］ Vieira G E，Herrmann J W，Lin E.Rescheduling manufacturing systems：A framework of strategies，policies，and methods［J］.Journal of Scheduling 2003，6（1）：39－62.

［10］ Graham R L，Lawler E L，Lenstra J K，et al.Optimization and approximation in deterministic sequencing scheduling：A survey［J］.Annals of Discrete Mathematics，1979，5：287－326.

［11］ Qi Xiangtong，Bard J F，Yu Gang.Disruption management for machine scheduling：the case of SPT schedules［J］.International of Production Ecnomics，2006，103（1）：166－184.

［12］ Lee C Y，Yu Gang.Single machine scheduling under potential disruption［J］.Operations Research Letters，2007，35（4）：541－548.

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

［14］ 慕運動.關(guān)于重新排序問題的研究［D］.鄭州：鄭州大學(xué)，2007.

［15］ Zhao Chuanli，Tang Hengyong.Rescheduling problems with deteriorating jobs under disruptions［J］.Applied Mathematical Modelling，2010，34（1）：238－243.

［16］ 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.

［17］ Leus R，Herroelen W.The complexity of machine scheduling for stability with a single disrupted job［J］.Operations Research Letters，2005，33（2）：151－156.

［18］ Cowling P，Johansson M.Using real time information for effective dynamic scheduling［J］.European Journal of Operational Research，2002，139（2）：230－244.

［19］ Ballestin F，Leus R.Meta－h(huán)euristics for stable scheduling on a single machine［J］.Computer ＆Operations Research，2008，35（7）：2175－2192.

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

［21］ Lee C Y，Yu Gang.Parallel－machine scheduling under potential disruption［J］.Optimiaztion Letters，2008，2（1）：27－37.

［22］ Petrovic D，Duenas A.A fuzzy logic based production schdeduling／rescheduling in the presence of uncertain disruptions［J］.Fuzzy Sets and Systems，2006，157（16）：2273－2285.

［23］ Duenas A，Petrovic D.An approach to predictive reactive scheduling of parallel machines subject to disruptions［J］.Annal Operation Research，2008，159（1）：65－82.

［24］ Vieira G E，Herrmann J W，Lin E.Predicting the performance of rescheduling strategies for parallel machine systems［J］.Journal of Manufacturing Systems，2000，19（4）：256－266.

［25］ Barua A，Raghavan N，Upasani A，et al.Implementing global factory schedules in the face of stochastic disruptions［J］.International Journal of Production Research，2005，43（4）：793－818.

［26］ Lee C Y.Minimizing the makespan in the two－machine flowshop scheduling problem with an availability constraint［J］.Operations Research Letters，1997，20（13）：129－139.

［27］ Akturk M S，Gorgulu E.Match－up scheduling under a machine breakdown［J］.European Journal of Operational Research，1999，112（1）：81－97.

［28］ Mehta S V，Uzsoy R M.Predictable scheduling of a job shop subject to breakdowns［J］.IEEE Transcations on Robotics and Automation，1998，14（3）：365－378.

［29］ Shafaei R，Brunn P.Workshop scheduling using practical（inaccurate）data.Part 1：The performance of heuristic scheduling rules in a dynamic job shop environment using a rolling time horizon approach［J］.International Journal of Production Research，1999，37（17）：3913－3925.

［30］ Shafaei R，Brunn P.Workshop scheduling using practical（inaccurate）data.Part 2：An investigation of the robustness of scheduling rules in a dynamic and stochastic environment［J］.International Journal of Production Research，1999，37 （18）：4105－4117.

［31］ Sabuncuoglu I，Karabuk S.Rescheduling frequency in an FMS with uncertain processing times and unreliable machines［J］.Journal of Manufacturing Systems，1999，18（4）：268－283.

［32］ Jain S，F(xiàn)oley W J.Impact of interruptions on schedule execution in flexible manufacturing systems［J］.International Journal of Flexible Manufacturing Systems，2002，14（4）：319－344.

［33］ Aytug H，Lawley M A，Mckay K，et al.Executing production schedules in the face of uncertainties：A review and some future directions［J］.European Journal of Operational Research，2005，16（1）：86－110.

［34］ Sun J，Xue D.A dynamic reactive scheduling mechanism for responding to changes of production orders and manufacturing resources［J］.Computers in Industry，2001，46（2）：189－207.

［35］ Yamamoto M，N of S Y.Scheduling／rescheduling in the manufacturing operating system environment［J］.In temational Joumal of Production Research，1985，23（4）：705－722.

［36］ Vieira G E，Herrmann J W，Lin E.Analytical models to predict the performance of a single－machine system under periodic and event－driven rescheduling strategies［J］.International Journal of Production Research，2000，38（8）：1899－1915.

［37］ Bierwirth C，Mattfeld D C.Production scheduling and rescheduling with genetic algorithms［J］.Evolutionary Computation，1999，7（1）：1－17.

［38］ Church L K，Uzsoy R.Analysis of periodic and event－driven rescheduling policies in dynamic shops［J］.International Journal of Computer Integrated Manufacturing，1992，5（3）：153－163.

［39］ Wu S D，Storer R H，Chang P C.One－machine rescheduling heuristics with efficiency and stability as criteria［J］.Computers and Operations Research，1993，20（1）：1－14.

Review of Disruption Management in Production Scheduling

TANG Haibo1，YE Chunming2，MA Huimin1，WU Bin1
（1.School of Business，Shanghai DianJi University，Shanghai 201306，China；2.Business School，University of Shanghai for Science and Technology，Shanghai 20093，China）

This paper summarizes the research related to disruption management in production scheduling by reviewing source of disruption，and presentation，solution strategy and efficiency evaluation of disruption management in production scheduling.The definition of disruption management in production scheduling and operation of process are discussed.Further development on disruption management in production scheduling is proposed.

disruption management；production scheduling；scheduling strategy；scheduling objective；predict reactive scheduling

F 273

A

2095－0020（2012）03－0189－08

2012－06－15

教育部高等學(xué)校博士點基金項目資助（20093120110008）；教育部人文社會科學(xué)規(guī)劃基金項目資助（10YJA630187）；上海市自然科學(xué)基金項目資助（10ZR1412300）；上海電機學(xué)院重點學(xué)科資助（10XKJ01）

唐海波（1976－），男，講師，博士，專業(yè)方向為工業(yè)工程、生產(chǎn)調(diào)度及智能算法，E－mail：chthb＠163.com