具有學習和退化效應的單機干擾管理問題

劉春來, 王建軍

(1.杭州電子科技大學 管理學院,浙江 杭州 310018; 2.大連理工大學 管理與經濟學部,遼寧 大連 116023)

0 引言

大量排序問題的研究中都假定工件的加工時間是一個常數，加工機器在整個加工過程中總是高效運行的；但在現實的環境中，工件的加工時間可能由于工人學習、退化等因素發生改變，機器的效率可能由于機器使用時間的過長而降低或出現故障。Browne和Yechiali[1]提出了具有退化工件的排序問題，也稱為與開工時間有關的排序問題，這一模型已在鋼鐵工業、塑料工業、醫療行業及森林滅火等方面有許多應用[2～4]，受到了越來越多的實踐者和學者關注。Gawiejnowicz[5]在其《Time-dependent Scheduling》一書中對這一領域的相關術語和研究做了詳細地介紹和探討。Cheng[6]等人對加工時間與開工時間相關的排序問題的相關研究成果進行了總結，同時也進一步提出了一些具有挑戰性的且尚未解決的難題。Biskup[7]首先將學習效應這一概念應用于排序問題中，證明了具有學習效應的單機極小化最大完工時間和總完工時間問題是多項式可解的，并且在文獻[8]中總結了當前有關表示學習效應的不同函數類型，同時指出了未來研究發展的方向。

近年來，針對實際生產過程中面臨的管理問題，同時考慮具有退化工件和學習效應的排序模型引發了工業界和學術界的廣泛關注。Lee[9]對同時具有退化工件和學習效應的單機排序問題研究了兩種加工時間的模型，并且在多項式時間內得到了問題的最優解。Wang和Guo[10]討論了同時具有退化工件和學習效應的單機工期安排問題，構造了一個多項式時間算法解決所研究的問題。對于這方面的研究大多限定在單機問題上，更多有關退化和學習的模型可參考文獻[11,12]。

在客觀現實世界中，不確定性事件的發生是不可避免的，這就會對事先制定好的計劃造成干擾。機器出現故障(維修)導致一段時間不可用就是其中的一類問題。在經典排序模型下，機器一段時間不可用問題得到了廣泛地研究，具體讀者可參見文獻[13～15]。Ji[16]等考慮了一個具有簡單線性退化工件的單機排序問題，首次將工件加工時間退化現象引入到機器可用性約束問題中。馬英[17]等研究了機器帶有一個不可用區間限制和工件加工時間退化的單機最大完工時間問題，提出了一種動態規劃算法以得到最優解。Zhang和Luo[18]研究了具有退化工件且機器可用性限制下的平行機排序問題，提出了解決問題的一個近似多項式時間算法。

然而，大多數的重排序問題都集中于在新的環境下仍然考慮原目標如何最優，而本文的干擾排序模型既考慮了原目標又衡量了干擾事件造成的擾動。Qi[19]首先提出了干擾環境下機器排序干擾管理這一概念，并且研究了機器排序中常出現的幾種干擾基本類型。劉鋒[20,21]等人對單機干擾管理的幾個模型進行了深入研究，Lee[22]，Tang[23]對平行機干擾管理做了許多有意義的工作。胡祥培[24]等人對干擾管理的模型及其算法研究等做了分析綜述。對于更詳細的內容可參考文獻[25,26]。Zhao和Tang[27]第一次嘗試把干擾管理問題引入工件加工時間可變的新型排序模型中，對于具有簡單線性退化的問題作了分析和探討，但對于更復雜的或者更具有現實意義的新模型還沒有涉及。除了文獻[27]其它有關干擾管理的文獻都是考慮加工時間為常數的情況，本文探討在可預見性機器擾動環境下，工件加工時間既與開工時間有關又與其所在排序中的位置相關的單機排序問題。可預見性擾動是指當加工原始制定好的工件排序時獲得干擾因素將會在未來某個時刻發生這一信息，得知干擾將會發生這一信息后，管理者會及時對原始排序進行調整。根據干擾度量函數的不同研究了兩個問題，第一個問題的目標函數是總完工時間與總誤工時間的加權和；第二個問題的目標函數是總完工時間與總提前時間的加權和。對于所研究的問題，首先證明了最優排序具有的性質，然后建立了相應的動態規劃算法，并分析了算法的計算復雜度。

1 問題描述

假設N={J1,J2,…,Jm}表示需要排序加工的工件集，所有工件在加工過程中都是不可中斷的且在時刻t0>0都已到達，工件的實際加工時間是既與其開始加工時間又與其所在加工位置有關的函數。在本文中，定義αj表示工件Jj的惡化率且αj>0，sj表示工件Jj在機器上的開始加工時間，a表示工件的學習率且0

在工件的加工過程中，由于干擾事件的發生，導致原排序可能不再是最優排序，需要快速調整加工方案以便在兼顧原最優目標情況下降低干擾事件造成的影響。在可預見性擾動模型下，管理者一旦得知相關的擾動信息，則立即將未加工的工件(假設個數為n，n≤m)從1到n重新標號并且重置此時刻為0，本文后面涉及的工件序號都是對未加工工件而言的。令ΔM表示機器發生中斷干擾，即當干擾發生時機器會有一段時間不可用，機器這段不可用時間記為[ta,tb](ta≥min{αjt0},1≤j≤n)，當機器中斷結束后，學習效應將重新開始。

本文考慮兩個涉及機器干擾的單機排序問題，第一個問題的目標函數是極小化總完工時間與總延誤時間的加權和，第二個問題的目標函數是極小化總完工時間與總提前時間的加權和。沿用文獻Qi[19]中的目標函數，使用三參數表示法問題可記為：

1|Δm,αjsjar-1,pred-mgt|αΣCj+βΣTj

(1)

1|Δm,αjsjar-1,pred-mgt|αΣCj+βΣEj

(2)

其中α,β≥0。

2 問題1|Δm,αjsjar-1,pred-mgt|αΣCj+βΣTj

考慮到極小化總完工時間的單機排序問題1|Δm,αjsj,pred-mgt|ΣCj是NP-困難的(文獻[16])，而這一問題又是本文所研究問題的特殊情形(a=1,α=1,β=0)。因此，本文所研究的問題(1)和(2)都是NP-困難的。

引理1對問題1|pjr=αjsjar-1|Cmax，給定排序π=[J[1],…,J[n]]，工件J[1]的開工時間為t≥t0，那么。

(3)

證明對于任意給定的一個排序π，安排在第一個位置上加工的工件的實際加工時間為p[1]=α[1]t，完工時間為C[1]=t+p[1]=t(1+α[1])；相似地，可得

引理2[12]對于問題1|pjr=αjsjar-1|ΣCj，按照工件惡化率αj的非減序排列可得問題的最優排序(SDR規則)。

定理1對于問題1|Δm,αjsjar-1,pred-mgt|αΣCj+βΣTj，存在一個最優解決方案使得排在ta時刻前的工件按SDR規則排列，排在tb時刻后的工件按SDR規則排列。

證明考慮一個最優排序σ，在此最優排序中兩個相鄰工件Jk和Jj，Jk在Jj前一個位置加工且αk≥αj，假設Jk的開始加工時間為t1，處在最優排序的第k個位置，那么有

Ck=t1+αkt1ak-1

Cj=Ck+αjCkak=t1+(αk+αja+αkαjak)t1ak-1

交換工件Jk和Jj的位置得到一個新的排序σ′，在新排序中σ′，有

由此可得

(4)

=(αj+αka-αk+αkαjak)t1ak-1

由此可得

(5)

(6)

(7)

基于定理1的結論，下面給出求解問題(1)的一個動態規劃算法：

將n個工件按SDR規則重新排序，即α1≤α2≤…≤αn，由定理1可知，工件J1一定是排在ta時刻前的第一個工件，或tb時刻后的第一個工件。如果工件J1是排在ta時刻前的第一個工件，那么工件J2一定是排在ta時刻前的第二個工件或者tb時刻后的第一個工件；如果工件J1是排在tb時刻后的第一個工件，那么工件J2一定是排在ta時刻前的第一個工件或者tb時刻后的第二個工件。由此，對一個給定的工件集σi=[J1,J2,…,Ji]，(i=1,2,…,n)，工件Ji一定是排在ta時刻前的最后一個工件或者tb時刻后的最后一個工件。

假設x表示排在ta時刻前的工件的加工時間表長，y表示排在tb時刻后的工件的加工時間和，r表示排在ta時刻前工件的個數(排在tb時刻后的工件個數為i-r且tb時刻后工件的學習效應重新開始)，(i,x,y,r)表示工件集σi所對應的狀態，f(i,x,y,r)表示在狀態(i,x,y,r)下對應的目標函數值。

動態規劃算法如下：

(3)最優值為min{f(n,x,y,r)}

3 問題 1|Δm,αjsjar-1,pred-mgt|αΣCj+βΣEj

在目標函數中存在真實提前時間這一問題下，需要對α≥β和α<β兩種情況分別進行考慮。

引理3對于問題1|Δm,αjsjar-1,pred-mgt|αΣCj+βΣEj，當α≥β時，存在最優排序滿足相鄰工件間沒有空閑時間。

證明考慮最優排序σ=[J[1],…,J[n]]，如果工件J[i]前存在空閑時間，那么向前移動工件J[i]直到工件J[i-1]和工件J[i]之間沒有空閑，假設工件J[i]向前移動了Δt個時間單位，那么完工時間減少α[j]Δtai-1了，提前的時間量最多增加α[j]Δtai-1，由于α≥β，所以向前移動工件消除相鄰工件間的空閑時間，總目標函數值不會增加。

定理2對于問題1|Δm,αjsjar-1,pred-mgt|αΣCj+βΣEj，當α≥β時，存在一個最優方案使得排在ta時刻前的工件按SDR規則排列，排在tb時刻后的工件按SDR規則排列。

證明考慮一個最優排序σ，在此最優排序中兩個相鄰工件Jk和Jj，Jk在Jj前一個位置加工且αk≥αj，假設Jk的開始加工時間為t1，處在最優排序的第k個位置，那么有

Ck=t1+αkt1ak-1

Cj=Ck+αjCkak=t1+(αk+αja+αkαjak)t1ak-1

交換工件Jk和Jj的位置得到一個新的排序σ′，在新排序σ′中，有

由(4)式可得

(8)

由此可得

(9)

≤(αk-αJ)t1ak-1

(10)

基于以上兩種情況可得

(11)

基于定理2的結論，建立解決問題1|Δm,αjsjar-1,pred-mgt|αΣCj+βΣEj的一個動態規劃算法：

動態規劃算法如下：

(3)最后，min{g(n,x,y,r)}就是所求的最優值。

當α<β時，在最優排序中相鄰工件間可能出現空閑時間，所以引理3和定理2中的最優性條件不再成立，本文不做探討，后續對其進行研究。

4 數值算例

針對本文所構建的動態規劃算法，使用MATLAB開發語言，在MATLAB R2012b 8.0.0.783版本環境下實現。

假定有8個未加工的工件，對應的惡化率和初始最優排序時工件的實際加工時間見表1，重置的開始加工時間t1=1，學習率a=0.6，中斷的起始時刻ta=9，結束時刻tb=15，加權因子分別為α=0.5，β=0.5。表2和表3中的二維向量(f,ξ)，其中f表示當前狀態下對應的目標函數值，ξ={0,1}分別表示當前狀態下工件Jj排在中斷前或中斷后的最后位置，表中涉及的數據均保留兩位小數。

經過運算得到問題一的最優目標函數值fmin=549.76，根據遞歸過程計算出的數值通過逆向追蹤法得出工件的加工順序為[4,5,1,2,3,6,7,8]，其中工件J4,J5排在中斷前加工，J1,J2,J3,J6,J7,J8排在中斷后加工(見表2)。

經過運算得到問題二的最優目標函數值fmin=288.52,根據遞歸過程計算出的數值通過逆向追蹤法得出工件的加工順序為[4,5,1,2,3,6,7,8]，其中工件J4,J5排在中斷前加工，J1,J2,J3,J6,J7,J8排在中斷后加工(見表3)。

表1 工件相關參數

表2 動態規劃迭代結果(問題一)

表3 動態規劃迭代結果(問題二)

5 結論

在客觀現實世界中，不確定性事件的發生總是不可避免的。面對干擾事件引發的影響，如何使系統盡快恢復使干擾產生的擾動盡量減少是決策者需要考慮的重要問題。本文考慮了在可預見性機器擾動環境下，工件實際加工時間既與開工時間有關又與其所在排序中的位置相關的單機排序問題，可預見性擾動是指當加工原始制定好的工件排序時獲得干擾因素將會在未來某個時刻發生這一信息，同時在得知干擾將會發生這一信息后，會及時對原始排序進行調整。考慮兩種不同的測量擾動大小的優化問題，第一個問題的目標函數是極小化總完工時間和總誤工時間的加權和；第二個問題的目標函數是極小化總完工時間和總提前時間的加權和。最后，分別得到了解決問題的動態規劃算法。對本文沒做探討的情況α<β可進一步的研究，且可考慮在干擾環境下的平行機或流水車間作業問題。