劉春來， 王建軍， 趙傳立

(1.大連理工大學(xué) 系統(tǒng)工程研究所，遼寧 大連 116023; 2.沈陽(yáng)師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，遼寧 沈陽(yáng) 110034)

?

具有退化工件和工期窗口安排的排序問題

劉春來1， 王建軍1， 趙傳立2

(1.大連理工大學(xué) 系統(tǒng)工程研究所，遼寧 大連 116023; 2.沈陽(yáng)師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，遼寧 沈陽(yáng) 110034)

針對(duì)具有退化工件的排序模型，考慮了單機(jī)排序和兩臺(tái)機(jī)器流水作業(yè)的工期窗口安排問題，在這一模型中，工件的加工時(shí)間是與其開工時(shí)間和退化率有關(guān)的一個(gè)線性函數(shù)。目標(biāo)是找到一個(gè)最優(yōu)排序和確定工期窗口的開始時(shí)間及大小以便最小化所有工件的費(fèi)用函數(shù)，費(fèi)用函數(shù)由四部分組成：提前、延誤、工期窗口開始時(shí)間和工期窗口大小。對(duì)所研究的單機(jī)問題，詳細(xì)地討論了符合現(xiàn)實(shí)情況的幾種類型問題，并得到了問題的最優(yōu)解；對(duì)兩臺(tái)機(jī)器流水作業(yè)問題，給出了多項(xiàng)式算法。

排序；工期窗口；退化工件；提前-延誤

0 引言

大量排序問題的研究中都假定工件的加工時(shí)間是固定不變的常數(shù)，但在現(xiàn)實(shí)的環(huán)境中，機(jī)器的效率可能由于機(jī)器使用時(shí)間的增加而降低，從而導(dǎo)致工件的加工時(shí)間可能隨著開工時(shí)間的增加而增加，這種現(xiàn)象被稱之為退化現(xiàn)象，也稱為與開工時(shí)間相關(guān)的排序問題[1]。工件加工時(shí)間與其開工時(shí)間有關(guān)的排序模型在鋼鐵工業(yè)，塑料工業(yè)及醫(yī)療等方面都有著廣泛的應(yīng)用[2]。在這類模型中，工件的真實(shí)加工時(shí)間函數(shù)通常由基本加工時(shí)間、退化率和開工時(shí)間來決定。

加工時(shí)間與開工時(shí)間有關(guān)的排序問題由Gupta和Gupta[3]首先提出，他們研究了非線性加工時(shí)間極小化最大完工時(shí)間的單機(jī)排序問題，給出了一個(gè)啟發(fā)式算法并進(jìn)行了數(shù)值仿真；對(duì)于加工時(shí)間是線性的問題，給出了多項(xiàng)式算法。Browne和Yechiali[4]對(duì)有關(guān)隨機(jī)變量的單機(jī)排序問題進(jìn)行了研究，對(duì)目標(biāo)函數(shù)為極小化最大完工時(shí)間期望和極小化最大完工時(shí)間方差的問題給出了求解最優(yōu)排序的多項(xiàng)式算法。Mosheiov[5]考慮了具有簡(jiǎn)單線性退化的排序問題，證明了最大完工時(shí)間、加權(quán)總完工時(shí)間、最大延誤、誤工總數(shù)等經(jīng)典正則目標(biāo)函數(shù)都是多項(xiàng)式時(shí)間可解的。Gordon[6]等人討論了工件的加工時(shí)間既與其在排序中的位置有關(guān)，又與其開始加工時(shí)間有關(guān)的各種常見經(jīng)典目標(biāo)函數(shù)的單機(jī)排序問題。Mosheiov[7]討論了一個(gè)單機(jī)極小化總完工時(shí)間問題，證明了最優(yōu)排序具有V形性質(zhì)。Cheng[8]等人總結(jié)了加工時(shí)間與開工時(shí)間相關(guān)的排序問題的最新研究，同時(shí)也提出了一些尚未解決的問題。

另一方面，涉及工期窗口的排序問題也得到了深入的研究，所謂的工期窗口排序問題是指：供應(yīng)商與客戶商協(xié)商確定一段交貨期時(shí)間窗口，使得在這段交貨期時(shí)間內(nèi)完工的工件不受處罰，而在這段交貨期時(shí)間之前或之后(稱為提早或延誤)完工的工件受到相應(yīng)的處罰，對(duì)于這方面的相關(guān)研究可參見文獻(xiàn)[9～11]。有關(guān)退化工件的非正則目標(biāo)函數(shù)的排序問題也是目前研究的熱點(diǎn)。Wang[12]等人探討了具有線性退化工件的單機(jī)排序問題，目標(biāo)函數(shù)為極小化最大延遲的絕對(duì)值。對(duì)于共同工期是已給定的常量和待確定的未知變量的情況，證明了所研究的問題都是多項(xiàng)式時(shí)間可解的。Yang[13]等人研究了具有工件相關(guān)的老化效應(yīng)和有關(guān)工期窗口的惡化維修的排序問題，目標(biāo)是找到維修的最佳時(shí)間、工期窗口的開始和結(jié)束時(shí)間及其最優(yōu)工件順序以便極小化提前、延誤、工期窗口的開始時(shí)間和大小的總費(fèi)用，并對(duì)他們所研究的問題提出了多項(xiàng)式解法。Mosheiov和Sarig[14]研究一種關(guān)于工期窗口的極小最大化排序問題，討論了單機(jī)、平行機(jī)和流水作業(yè)機(jī)三種情況，對(duì)單機(jī)問題和兩臺(tái)機(jī)器的流水作業(yè)問題給出了多項(xiàng)式解法。

絕大多數(shù)文獻(xiàn)在研究涉及工期窗口排序問題時(shí)，都假定工件的加工時(shí)間是固定的常量或所研究的目標(biāo)函數(shù)是單目標(biāo)函數(shù)、提前/延誤與工期窗口的加權(quán)和等規(guī)則函數(shù)。本文在文獻(xiàn)[14]的基礎(chǔ)上考慮具有退化工件的排序問題，對(duì)單機(jī)和兩臺(tái)機(jī)器流水作業(yè)問題研究了最優(yōu)化所有工件最大費(fèi)用(由最差排序產(chǎn)生的處罰)的最小值這一問題，費(fèi)用函數(shù)由四個(gè)因子構(gòu)成：提前、延誤、工期窗口開始時(shí)間和工期窗口大小。同時(shí)，為了能夠更好地反映現(xiàn)實(shí)情況，詳細(xì)討論了單機(jī)問題中的幾種情形，分別得到了解決問題的最優(yōu)策略。對(duì)于兩臺(tái)機(jī)器流水作業(yè)問題，通過分析最優(yōu)解性質(zhì)和引入Repeated-Johnson算法，得到了工件最大費(fèi)用的最小值。對(duì)所研究的兩個(gè)問題，證明是多項(xiàng)式可解的且給出了相應(yīng)的多項(xiàng)式算法。

1 問題描述

假設(shè)N={J1,J2,……,Jn}表示需要排序的工件集，同參考文獻(xiàn)[12]一樣，我們假設(shè)所有工件在加工過程中都是不可中斷的且所有的工件在時(shí)刻t0>0時(shí)都已到達(dá)，且所有的工件具有一個(gè)共同的工期窗口。如果工件Jj的開工時(shí)間為sj，退化參數(shù)為αj，那么工件Jj的實(shí)際加工時(shí)間為：pj=αjsj，j=1,2,……,n,令d1和d2分別表示工期窗口的開始和結(jié)束時(shí)間，D=d2-d1表示工期窗口的規(guī)模大小，那么顯然有d2≥d1。處在工期窗口之中完工的工件稱為準(zhǔn)時(shí)工件，不進(jìn)行處罰；而在工期窗口開始時(shí)間之前或結(jié)束時(shí)間之后完工的工件要進(jìn)行相應(yīng)的處罰。

對(duì)于一個(gè)給定排序π=(J[1],J[2],…,J[n])，定義為C[j]為位于排序中第j個(gè)位置上工件的完工時(shí)間，令C[1]=Cmin表示確定排序中第一個(gè)(即最早)工件的完工時(shí)間，C[n]=Cmax表示確定排序中最后一個(gè)(即最晚)工件的完工時(shí)間。一個(gè)工件在d1時(shí)刻或之前完工的稱為提前，記為E[j]，表達(dá)式為E[j]=max{0,d1-C[j]}。一個(gè)工件在d2時(shí)刻或之后完工的稱為延誤，記為T[j]，表達(dá)式記為T[j]=max{0,C[j]-d2}。使用與文獻(xiàn)[14]中相同的目標(biāo)函數(shù)，本文的研究目標(biāo)就是找到一個(gè)排序和工期窗口以便極小化以下的最大費(fèi)用：

(1)

其中μ,β,γ,δ分別是提前、延誤、工期窗口開始時(shí)間和工期窗口大小的單位處罰費(fèi)用。

2 單機(jī)情況

2.1 工期窗口位置和大小均給定的情況

顯然，在這種情況下，最優(yōu)排序中相鄰的加工工件之間不會(huì)有空閑空間。在一個(gè)排序中，排在第一個(gè)位置的工件決定了最大提前的大小，排在最后的工件決定最大延誤的大小。當(dāng)工期窗口給定時(shí)，總費(fèi)用可以表示為：

(2)

定理1 對(duì)于工期窗口位置和大小給定的情況，將退化率最大的工件首先加工會(huì)得到最優(yōu)排序。

證明 令αl=max{αj:j=1,2,…,n}。那么對(duì)所有j=1,2,…,n，由(2)式可得：

(3)

下面我們考慮四種情況：

μ(d1-s(1+αl))+γd1+δD≤μ(d1-s(1+αj))+γd1+δD

基于以上的討論，(3)式對(duì)j=1,2,…,n都成立。證畢。

由定理1可知，總費(fèi)用可以通過下式代替：

(4)

其中αl=max{αj:j=1,2,…,n}。

2.2 工期窗口大小給定的情況

引理2 對(duì)于一個(gè)給定的排序π=(J[1],J[2],…,J[n])，可在以下三種情況中的一種得到最優(yōu)解：

證明 顯然d2≤Cmax，下面考慮兩種情形β≥γ和β<γ。

β≥γ的情況：繼續(xù)分兩種情況來考慮。如果D>Cmax-Cmin，那么有d1

Z(D)=β(Cmax-d1-D)+γd1+δD=(δ-β)D+(γ-β)Cmin+βCmin

如果D≤Cmax-Cmin，下面證明d1≥Cmin。假如d1

μ(d1-Cmin)+γd1+δD=β(Cmax-d1-D)+γd1+δD

Z(D)=β(Cmax-d1-D)+γd1+δD=(δ-β)D+(γ-β)t0+βCmax，證畢。

通過以上引理2的分析，對(duì)一給定的排序，能夠得到最優(yōu)工期窗口的開始時(shí)間。在情形(1)中，總費(fèi)用是一個(gè)常量并且與工件順序無關(guān)。在情形(2)和(3)中，當(dāng)最大化Cmin時(shí)，總費(fèi)用最小，即將退化率最大的工件首先加工。

2.3 工期窗口開始時(shí)間給定的情況

引理3 對(duì)于一個(gè)給定的排序π=(J[1],J[2],…,J[n])，可在以下兩種情況中的一種得到最優(yōu)解：

(1)工期窗口的大小為零，即D=0。

(2)工期窗口的大小為Cmax-d1，即D=Cmax-d1。

證明 將工期窗口的結(jié)束時(shí)間向右移動(dòng)Δ個(gè)時(shí)間單位(工期窗口的開始時(shí)間d1不變)，則總費(fèi)用的改變?chǔ)=Δδ-Δβ=Δ(δ-β)。如果β>δ，那么直到d2=Cmax的移動(dòng)都是可行的，即D=Cmax-d1?？傎M(fèi)用(有關(guān)d1的表達(dá)式)可表示為：

Z(d1)=μ(d1-Cmin)+γd1+δD=(μ+γ-δ)d1+δCmax-μCmin

如果β≤δ，那么工期窗口的結(jié)束時(shí)間向左移將會(huì)使總費(fèi)用減少。顯然，總費(fèi)用的改變?chǔ)=Δβ-Δδ=Δ(β-δ)<0。因此，工期窗口的結(jié)束時(shí)間向左移直到d2=d1，即D=0?？傎M(fèi)用(有關(guān)d1的表達(dá)式)可表示為：

Z(d1)=max{μ(d1-Cmin)+γd1,β(Cmax-d1)+γd1}，證畢。

通過以上引理3，對(duì)于一個(gè)給定的排序，能夠得到最優(yōu)工期窗口的結(jié)束時(shí)間。在情形(1)中，當(dāng)最大化Cmin，即將退化率最大的工件首先加工時(shí)，總費(fèi)用最小。在情形(2)中，最小總費(fèi)用可由max{μ(d1-Cmin)+γd1,β(Cmax-d1)+γd1}得到。

因?yàn)閐1-s(1+αl)≤d1-s(1+αj)，所以，將退化率最大的工件首先加工能使總費(fèi)用最小。

2.4 工期窗口位置和大小均是變量的情況

引理4 對(duì)于一個(gè)給定的排序π=(J[1],J[2],…,J[n])，可在以下四種情況中的一種得到最優(yōu)解：

證明 可參見文獻(xiàn)[14]中的引理1，方法類同。

通過引理4，能夠得到最小費(fèi)用。經(jīng)過計(jì)算，情況(1)和(4)的最小費(fèi)用分別為βCmax和δCmax。由于時(shí)間相關(guān)的極小化時(shí)間表長(zhǎng)問題與工件的排列順序無關(guān)，所以情況(1)和(4)中的最小費(fèi)用與工件的排列順序無關(guān)。對(duì)于情況(2)和(3)，通過計(jì)算得最小費(fèi)用分別為(μCmin(γ-β)+βCmax(μ+γ))/(μ+β)和δCmax+Cmin(γ-δ)。因?yàn)榍闆r(2)中β≥γ，情況(3)中δ≥γ，所以，當(dāng)最大化Cmin時(shí)費(fèi)用最小。顯然，將退化率最大的工件首先加工能夠最大化Cmin。由此，提出一個(gè)算法復(fù)雜性為O(nlogn)的與文獻(xiàn)[14]相似的算法。

算法1

如果β≥γ:

否則，退化率最大的工件在t0時(shí)開始加工；

如果β<γ：

3 兩臺(tái)機(jī)器流水作業(yè)問題

在兩臺(tái)機(jī)器流水作業(yè)排序問題中，有n個(gè)工件需要加工，每個(gè)工件Jj有兩道工序(T1j,T2j)，j=1,2,…,n。各個(gè)工件依次在兩臺(tái)機(jī)器上完成兩道工序，即每個(gè)工件先在機(jī)器一上加工然后在機(jī)器二上加工，工序T2j只能在工序T1j完工后才能開始。工序Tij的實(shí)際加工時(shí)間可表示為：

pij(t)=αijt，i=1,2；j=1,2,…,n

其中αij表示工序Tij的退化率，t>0表示工序Tij的開工時(shí)間。

對(duì)一個(gè)給定的排序π=(J[1],J[2],…,J[n])，令C[j]=C2[j](π)表示排在第二臺(tái)機(jī)器第j個(gè)位置上的工件的完工時(shí)間，相應(yīng)的E[j]表示工件的提前，T[j]表示工件的延誤。同時(shí)假設(shè)Cmin表示在第二臺(tái)機(jī)器上第一個(gè)(最早)加工工件的完工時(shí)間，Cmax表示在第二臺(tái)機(jī)器上最后一個(gè)(最晚)加工工件的完工時(shí)間。與單機(jī)問題相同，研究目標(biāo)是找到一個(gè)排序和工期窗口以便極小化以下的最大費(fèi)用：

引理5 對(duì)于問題F2|αijt|Cmax，最優(yōu)排序可由Johnson規(guī)則得到。

證明 見文獻(xiàn)[15]中定理5。

如果Cmin和Cmax是確定的，那么問題的求解過程與單機(jī)情況相似。因此，最優(yōu)解仍然是引理4中的四種情況中的一種，且最優(yōu)解與變量μ,β,γ和δ有關(guān)。

由引理4可知，對(duì)于情況(1)和(4)，產(chǎn)生的最小費(fèi)用分別為βCmax和δCmax。因此，通過引理5，極小化最大完工時(shí)間可以得到這兩種情況的最小費(fèi)用。另外，對(duì)情況(2)和(3)，經(jīng)計(jì)算最小費(fèi)用分別為(μCmin(γ-β)+βCmax(μ+γ))/(μ+β)和δCmax+Cmin(γ-δ) 。由于情況(2)中β≥γ，情況(3)中δ≥γ，所以，當(dāng)極小化Cmax同時(shí)極大化Cmin時(shí)，總費(fèi)用最小。顯然地，對(duì)不同的排序兩個(gè)因素的任意一個(gè)都可能產(chǎn)生最優(yōu)解。因此，我們使用一個(gè)策略保證得到最優(yōu)排序：將n個(gè)工件中的每一個(gè)安排在第一個(gè)位置一次，這樣就能得到所有可能的Cmin的值，然后通過對(duì)每種情況中剩余的n-1個(gè)工件應(yīng)用Johnson算法獲得最優(yōu)的Cmax值。當(dāng)然，對(duì)極小化最大完工時(shí)間的兩臺(tái)流水作業(yè)排序問題，最優(yōu)排序中在第二臺(tái)機(jī)器上加工的工件之間可能會(huì)出現(xiàn)空閑時(shí)間。因此，對(duì)于情況(2)和(3)，當(dāng)最大化Cmin時(shí)，將所有出現(xiàn)空閑時(shí)間工件向后移(避免工件之間的空閑時(shí)間)。定義一個(gè)Repeated-Johnson算法：確定第一個(gè)加工的工件(重復(fù)n個(gè)工件)，對(duì)剩下的n-1個(gè)工件使用Johnson算法?；谝陨系膯栴}分析，給出如下的算法：

算法2

如果β≥γ:

如果δ≤γ，應(yīng)用Johnson算法;

如果β<γ：

4 結(jié)論

本文主要考慮單機(jī)和兩臺(tái)機(jī)器流水作業(yè)問題的共同工期窗口安排和具有退化工件的排序問題，研究了所有工件最大費(fèi)用的最小值，推廣了已有文獻(xiàn)的結(jié)論，拓寬了問題的適應(yīng)性。工件的實(shí)際加工時(shí)間是其開工時(shí)間和退化率的線性函數(shù)，研究的非正則函數(shù)中包含四個(gè)因子：提前、延誤、工期窗口開始時(shí)間和工期窗口大小。對(duì)于單機(jī)排序問題，通過對(duì)所討論問題的模型逐步分析，得到解決問題的最優(yōu)策略和最優(yōu)解；對(duì)于兩臺(tái)機(jī)器流水作業(yè)問題，通過設(shè)計(jì)多項(xiàng)式算法得到了問題的最優(yōu)解。對(duì)于加工時(shí)間為更一般的與開工時(shí)間有關(guān)的函數(shù)表達(dá)式的排序問題可做進(jìn)一步研究，同時(shí)，將本節(jié)研究的單機(jī)加工環(huán)境換為平行機(jī)模型則問題變成NP-難的，可做進(jìn)一步詳細(xì)探討。

[1] Alidaee B, Womer N K. Scheduling with time dependent processing times: review and extensions[J]. Journal of the Operational Research Society, 1999, 7(50): 711-720.

[2] Gawiejnowicz S. Time-dependent scheduling[M]. Berlin : Springer, 2008.

[3] Gupta J N D, Gupta S K. Single facility scheduling with nonlinear processing times[J]. Computers and Industrial Engineering, 1988, 14(4): 387-393.

[4] Browne S, Yechiali U. Scheduling deteriorating jobs on a single processing[J]. Operations Research, 1990, 38(3): 495- 498.

[5] Mosheiov G. Scheduling jobs under simple linear deterioration[J]. Computers and Operations Research, 1994, 21(6): 653- 659.

[6] Gordon V S, Potts C N, Strusevich V A, Whitehead J D. Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation[J]. Journal of Scheduling, 2008, 11(5): 357-370.

[7] Mosheiov G. A note on scheduling deteriorating jobs[J]. Mathematical and Computer Modelling, 2005, 41(8-9): 883- 886.

[8] Cheng T C E, Ding Q, Lin B M T. A concise survey of scheduling with time-dependent processing times[J]. European Journal of Operational Research, 2004, 152 (1): 1-13.

[9] Cheng T C E. Optimal common due-date with limited completion time deviation[J]. Computers and Operations Research, 1988, 15(2): 91-96.

[10] Liman S D, Panwalker S S, Thongmee S. Common due window size and location determination in a single machine scheduling problem[J]. Journal of the Operational Research Society, 1998, 49(9): 1007-1010.

[11] Mosheiov G, Sarig A. A due-window assignment problem with position-dependent processing times[J]. Journal of the Operational Research Society, 2008, 59(7): 997-1003.

[12] Wang J B, Yang D L, Hsu C J. Single-machine scheduling to minimize absolute value in maximum lateness with deteriorating jobs[J]. Advanced Materials Research, 2011, 201-203: 1054-1060.

[13] Yang S J, Yang D L, Cheng T C E. Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance[J]. Computers and Operations Research, 2010, 37(8): 1510-1514.

[14] Mosheiov G, Sarig A. Minmax scheduling problems with a common due-window[J]. Computers and Operations Research, 2009, 36(6): 1886-1892.

[15] Zhao C L, Zhang Q L, Tang H Y. Scheduling problems under linear deterioration[J]. Acta Automatica Sinica, 2003, 29(4): 530-535.

Common Due-window Assignment and Scheduling Problems with Deteriorating Jobs

LIU Chun-lai1, WANG Jian-jun1, ZHAO Chuan-li2

(1.InstituteofSystemsEngineering,DalianUniversityofTechnology,Dalian116023,China; 2.SchoolofMathematicsandSystemsScience,ShenyangNormalUniversity,Shenyang110034,China)

This paper is devoted to a scheduling problem with simple linear deterioration, that is, the processing time of a job is a simple linear function of its starting time and its deterioration rate. We consider the common due-window assignment problem for the single machine and two machine flow shop. The goal is to schedule the jobs and the due-window so as to minimize the highest cost among all the jobs. The objective function contains four cost components: earliness, tardiness, due-window starting time and size. By analyzing the properties of the optimal schedule, we obtain the due-window starting time and size. For the single machine and two-machine flow shop problems, we present a polynomial time solution respectively. Moreover, some special cases of the single machine are also discussed in detail.

scheduling; due-window assignment; deteriorating jobs; earliness-tardiness

2013-11-09

國(guó)家自然科學(xué)基金資助項(xiàng)目(71271039；70902033)；教育部“新世紀(jì)優(yōu)秀人才支持計(jì)劃”項(xiàng)目(NCET-13- 0082)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(DUT14YQ211)

劉春來(1986-)，男，博士研究生，研究方向：排序理論與算法，干擾管理；王建軍(1977-)，男，副教授，博士，研究方向：干擾管理、電子商務(wù)與物流管理；趙傳立(1958-)，男，教授，博士，研究方向：組合最優(yōu)化。

O223

A

1007-3221(2015)04- 0116- 06