帶有退化、拒絕和不可用區(qū)間的恒速機排序問題

富曉雙，趙玉芳，田 野

(1.沈陽師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，遼寧 沈陽 110034；2.北京市第五中學(xué)通州校區(qū)，北京 101100)

0 引言

在大多數(shù)經(jīng)典的排序問題中，假設(shè)工件的加工時間是常數(shù).然而，在實際的生產(chǎn)過程中，當(dāng)機器連續(xù)加工工件時，可能會出現(xiàn)退化現(xiàn)象，即工件在排序中的開始加工時間越晚，它的實際加工時間越長，例如鋼鐵生產(chǎn)、消防、資源分配等.Jatinder N.D.Gupta和Sushil K.Gupta[1],Browne和Yechiali[2]分別提出了退化工件的概念，工件j的實際加工時間為aj+bjt,bj>0,aj是工件j的基本加工時間，bj是退化率，t是工件j的開始加工時間，對于最大完工時間的問題，他們證明了工件按aj/bj不減順序排序可以得到最優(yōu)解.Mosheiov[3]研究了帶有簡單線性退化的單機排序問題，工件j的實際加工時間為pj=αjt,αj是退化率，t>0是工件j的開始加工時間，目標(biāo)函數(shù)分別為最大完工時間、流程時間、總延誤、延誤工件數(shù)等，證明了這些問題都是多項式時間可解的.Bachman等[4]研究了帶有退化工件的單機排序問題，目標(biāo)為極小化總加權(quán)完工時間，證明了這個問題是NP-難的.王吉波等[5]研究了具有惡化效應(yīng)和可控加工時間的單機排序問題，目標(biāo)是確定工件的最優(yōu)排序、最優(yōu)資源分配和共同工期(松弛工期)，使所有工件的排序費用(包括提前時間、延誤時間、共同工期(松弛工期))和資源的消耗費用的線性加權(quán)和最小,證明了此問題可以在多項式時間內(nèi)求解.Ji和Cheng[6]研究了帶有退化工件的平行機排序問題，目標(biāo)為極小化總完工時間，對于這個NP-難問題，提出了一個FPTAS.此后，帶有退化工件的問題受到了越來越廣泛的關(guān)注.

在大多數(shù)的排序問題中，通常假設(shè)所有工件都必須在機器上加工，然而在實際的生產(chǎn)過程中，由于資源有限或考慮經(jīng)濟效益，決策者可能會選擇這些工件中的一個子集來加工，而可能對未被加工的工件產(chǎn)生一些懲罰，即拒絕懲罰.Bartal等[7]首先提出了帶有拒絕的排序問題，目標(biāo)為極小化接受工件的最大完工時間與拒絕工件的總懲罰之和.對于m臺平行機的情況，考慮離線問題：當(dāng)m固定時，提出了一個FPTAS；當(dāng)m任意時，提出了一個多項式時間近似策略(PTAS).Zhang等[8]研究了帶有拒絕的平行機排序問題，目標(biāo)為極小化總加權(quán)完工時間與拒絕工件總懲罰之和，給出了一個偽多項式時間的動態(tài)規(guī)劃算法和一個FPTAS.Li和Yuan[9]討論了帶有退化工件和拒絕的同速機排序問題，含3個目標(biāo)函數(shù)，分別為接受工件的最大完工時間與拒絕工件的總拒絕懲罰之和,接受工件的總加權(quán)完工時間與拒絕工件的總拒絕懲罰之和，以及接受工件的總完工時間與拒絕工件的總拒絕懲罰之和.對于前兩個目標(biāo)，當(dāng)機器的數(shù)量固定時，分別提出兩個FPTAS.對于后一個目標(biāo)，當(dāng)所有工件的退化率相同時，提出了時間復(fù)雜性為O(n2)的動態(tài)規(guī)劃算法.Wu和Luo[10]研究了帶有退化工件和拒絕的恒速機排序問題，其中工件的加工時間是它開始加工時間的簡單的線性函數(shù)，目標(biāo)是極小化接受工件的總完工時間與拒絕工件的總懲罰之和，給出了一個FPTAS.

在經(jīng)典的排序問題中，經(jīng)常假設(shè)機器一直可用.然而在許多實際情況中，由于機器發(fā)生故障或者維護期間無法加工工件，即產(chǎn)生了機器的不可用區(qū)間.Ji等[11]考慮了帶有簡單線性退化工件和不可用區(qū)間的單機排序問題，目標(biāo)分別是極小化最大完工時間和總完工時間，證明了這兩個問題都是NP-難的，并且分別提出偽多項式時間最優(yōu)算法.此外，對于最大完工時間問題，提出一個FPTAS；對于總完工時間問題，提出了一種啟發(fā)式算法.Zhao和Tang[12]研究了帶有退化工件和不可用區(qū)間的平行機排序問題，目標(biāo)是極小化總加權(quán)完工時間，提出了一個動態(tài)規(guī)劃算法，對于其中一臺機器上有一個不可用區(qū)間的特殊情況，給出了一個FPTAS.閆力君[13]研究了帶有退化工件、拒絕和不可用區(qū)間的兩臺同速機排序問題，其中工件的加工時間為開始加工時間的簡單的線性遞增函數(shù)，目標(biāo)為極小化接受工件的總加權(quán)完工時間與拒絕工件的總懲罰之和，對于這個NP-難問題，提出了一個FPTAS.

筆者考慮帶有退化工件、拒絕及第一臺機器帶有一個固定的不可用區(qū)間的兩臺恒速機排序問題,目標(biāo)是極小化接受工件的總完工時間與拒絕工件的總拒絕懲罰之和.對于這個NP-難問題，給出了一個FPTAS.

1 問題描述

2 修改目標(biāo)函數(shù)

1)在機器M1上不可用區(qū)間T1之前工件的完工時間為：

……

……

2)在機器M1上不可用區(qū)間T2之后工件的完工時間為：

……

……

3)在機器M2上工件的完工時間為：

C[2,1]=t0+p[2,1]=t0+b[2,1]t0/s=t0(1+b[2,1]/s),

……

……

(1)

3 FPTAS

Ji和Cheng[6]說明了Pm|pj=αjsj,rj=t0|∑Cj是NP-難的，因此問題(1)至少是NP-難的.當(dāng)不考慮拒絕時，對于Pm|pj=αjsj,rj=t0|∑Cj，每臺機器上的工件按{αj}不減順序排序是最優(yōu)的.因此有以下引理：

下面介紹變量xj(j=1,2,…,n),如果工件Jj在機器M1的T1之前加工，令xj=1；如果工件Jj在機器M1的T2之后加工，令xj=2；如果工件Jj在機器M2上加工，令xj=3；如果工件Jj被拒絕，令xj=0.令X為所有向量x=(x1,x2,…,xn)的集合，其中xj∈{0,1,2,3},j=1,2,…,n,下面定義X上的初始和遞歸函數(shù)：

如果工件Jj被拒絕，則有:

gj(x)=10jkgj-1(x)+10jkej,xj=0;gj(x)=10kgj-1(x),xj≠0.

min{F(x)|x∈X}.

下面介紹由Kovalyov和Kubiak[15]給出的過程劃分(A,h,δ),A?X,h(x)是X上的一個非負(fù)整數(shù)函數(shù),且0<δ≤1,下面的描述給出劃分(A,h,δ)的細(xì)節(jié).

過程劃分(A,h,δ):

以上過程劃分(A,h,δ)需要O(|A|log|A|)時間，下面的過程劃分(A,h,δ)的主要性質(zhì)將在FPTAS中使用.

引理3[15]kh≤logh(x|A|)/δ+2，這里h(x|A|)≥1,0<δ≤1.

對于問題(1)的FPTAS的正式描述在下面給出.

算法Aε：

步驟二(產(chǎn)生集合Y1,Y2,…,Yn) 對集合Yj-1中的每個向量的第j個分量添加k(k=0,1,2,3)，產(chǎn)生新的4個向量，來組成新的向量集Y′j，對于每個x∈Y′j，計算如下：

步驟三(求解) 選擇向量x0∈Yn,滿足

F(x0)=min{F(x)|x∈Yn}=min{gn(x)+fn(x)|x∈Yn}.

定理1 對于問題(1)，算法Aε在O(n9L6/ε5)時間內(nèi)找到一個解x0∈X，使得F(x0)≤(1+ε)F(x*).

|fj(x*[j])-fj(x(c1,c2,c3,d,e))|≤δfj(x*[j]),

且 |gj(x*[j])-gj(x(c1,c2,c3,d,e))|≤δgj(x*[j])成立.

令δ1=δ，考慮

因此，有:

(2)

(3)

也就是:

(4)

(5)

(6)

(7)

通過式(2)和式(6),有:

(δ+δ1(1+δ))fj+1(x*[j+1]).

類似地，有:

|gj+1(x*[j+1])-gj+1(x(a1,a2,a3,b,c))|≤(δ+δ1(1+δ))gj+1(x*[j+1]).

令δk=δ+δk-1(1+δ),k=2,3,…,n-j+1,有:

|fj+1(x*[j+1])-fj+1(x(a1,a2,a3,b,c))|≤δ2fj+1(x*[j+1]),|gj+1(x*[j+1])-gj+1(x(a1,a2,a3,b,c))|≤δ2gj+1(x*[j+1]).

對j+2,j+3,…,n重復(fù)論證，有x′∈Yn,使得:

|fn(x′)-fn(x*)|≤δn-j+1fn(x*),|gn(x′)-gn(x*)|≤δn-j+1gn(x*).

又通過引理4，有

因此，可以得到:

fn(x′)≤(1+δn-j+1)fn(x*)≤(1+ε)fn(x*),gn(x′)≤(1+δn-j+1)gn(x*)≤(1+ε)gn(x*).

綜上所述,有

F(x′)=gn(x′)+fn(x′)≤(1+ε)F(x*).

因此，在算法Aε的第三步中，向量x0被選擇滿足F(x0)≤(x′)≤(1+ε)F(x*).

kC1≤2(n+1)log(T1)/ε+2≤2nL/ε+2，kC2≤2(n+1)log(T2(Bmax)n)/ε+2≤2n2L/ε+2，kC3≤2(n+1)log(t0(Bmax)n)/ε+2≤2n2L/ε+2，kf≤2(n+1)log(10nkt0n(Bmax)n)/ε+2≤2n2L/ε+2，kg≤2(n+1)log(10nknemax)/ε+2≤2nL/ε+2.

4 結(jié)論

筆者研究的是帶有退化工件、拒絕和一個固定的不可用區(qū)間的兩臺恒速機排序問題.目標(biāo)是極小化接受工件的總完工時間與拒絕工件的總懲罰之和.首先根據(jù)Kovalyov和Kubiak[15]提出的過程劃分的要求，對目標(biāo)函數(shù)進行了修改，然后說明該問題是NP-難的，進而利用過程劃分的方法給出了一個FPTAS,最后確定了其時間復(fù)雜性為O(n9L6/ε5).由于機器帶有不可用區(qū)間以及拒絕懲罰同時存在的現(xiàn)象很普遍，因此，進一步研究機器帶有不可用區(qū)間以及拒絕懲罰的排序問題具有廣泛的應(yīng)用價值和實際意義.對于具有其他退化效應(yīng)的函數(shù)問題以及機器具有不可用區(qū)間的其他種類機器的排序問題，還有待進一步研究.