劉春來, 王建軍

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

0 引言

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

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

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

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

1 問題描述

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

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

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

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

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

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

(3)

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

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

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

證明考慮一個最優(yōu)排序σ，在此最優(yōu)排序中兩個相鄰工件Jk和Jj，Jk在Jj前一個位置加工且αk≥αj，假設(shè)Jk的開始加工時間為t1，處在最優(yōu)排序的第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的結(jié)論，下面給出求解問題(1)的一個動態(tài)規(guī)劃算法：

將n個工件按SDR規(guī)則重新排序，即α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時刻后的最后一個工件。

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

動態(tài)規(guī)劃算法如下：

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

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

在目標(biāo)函數(shù)中存在真實(shí)提前時間這一問題下，需要對α≥β和α<β兩種情況分別進(jìn)行考慮。

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

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

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

證明考慮一個最優(yōu)排序σ，在此最優(yōu)排序中兩個相鄰工件Jk和Jj，Jk在Jj前一個位置加工且αk≥αj，假設(shè)Jk的開始加工時間為t1，處在最優(yōu)排序的第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的結(jié)論，建立解決問題1|Δm,αjsjar-1,pred-mgt|αΣCj+βΣEj的一個動態(tài)規(guī)劃算法：

動態(tài)規(guī)劃算法如下：

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

當(dāng)α<β時，在最優(yōu)排序中相鄰工件間可能出現(xiàn)空閑時間，所以引理3和定理2中的最優(yōu)性條件不再成立，本文不做探討，后續(xù)對其進(jìn)行研究。

4 數(shù)值算例

針對本文所構(gòu)建的動態(tài)規(guī)劃算法，使用MATLAB開發(fā)語言，在MATLAB R2012b 8.0.0.783版本環(huán)境下實(shí)現(xiàn)。

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

經(jīng)過運(yùn)算得到問題一的最優(yōu)目標(biāo)函數(shù)值fmin=549.76，根據(jù)遞歸過程計(jì)算出的數(shù)值通過逆向追蹤法得出工件的加工順序?yàn)閇4,5,1,2,3,6,7,8]，其中工件J4,J5排在中斷前加工，J1,J2,J3,J6,J7,J8排在中斷后加工(見表2)。

經(jīng)過運(yùn)算得到問題二的最優(yōu)目標(biāo)函數(shù)值fmin=288.52,根據(jù)遞歸過程計(jì)算出的數(shù)值通過逆向追蹤法得出工件的加工順序?yàn)閇4,5,1,2,3,6,7,8]，其中工件J4,J5排在中斷前加工，J1,J2,J3,J6,J7,J8排在中斷后加工(見表3)。

表1 工件相關(guān)參數(shù)

表2 動態(tài)規(guī)劃迭代結(jié)果(問題一)

表3 動態(tài)規(guī)劃迭代結(jié)果(問題二)

5 結(jié)論

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