王吉波,郭苗苗,劉　桓,李　琳,王　丹

(1.沈陽航空航天大學(xué) 經(jīng)濟(jì)與管理學(xué)院,沈陽 110136; 2.沈陽航空航天大學(xué) 理學(xué)院,沈陽 110136;3.遼寧省體育學(xué)校 教務(wù)科,沈陽 110179; 4.沈陽航空航天大學(xué) 計(jì)算機(jī)學(xué)院,沈陽 110136)

?

名家綜述

具有依賴開工時(shí)間惡化工件的流水作業(yè)排序問題研究綜述

王吉波1,2,郭苗苗1,劉桓3,李琳2,王丹4

(1.沈陽航空航天大學(xué) 經(jīng)濟(jì)與管理學(xué)院,沈陽 110136; 2.沈陽航空航天大學(xué) 理學(xué)院,沈陽 110136;3.遼寧省體育學(xué)校 教務(wù)科,沈陽 110179; 4.沈陽航空航天大學(xué) 計(jì)算機(jī)學(xué)院,沈陽 110136)

具有惡化工件的排序問題是制造業(yè)、運(yùn)籌學(xué)、管理科學(xué)與工程中的一類重要問題，在鋼鐵工業(yè)、塑料工業(yè)、軍事以及醫(yī)療等方面有著廣泛的應(yīng)用。分析了帶有依賴開工時(shí)間惡化工件的流水作業(yè)排序問題的特點(diǎn)，目標(biāo)函數(shù)主要包括時(shí)間表長、總完工時(shí)間、總加權(quán)完工時(shí)間、最大延誤、總延誤時(shí)間等。然后就帶有依賴開工時(shí)間惡化工件流水作業(yè)排序問題進(jìn)行了全面的綜述，并指出了存在的不足和許多尚未解決的問題。最后，提出了具有惡化工件的流水作業(yè)排序工作進(jìn)一步研究的問題。

排序；流水作業(yè)；惡化工件

二十世紀(jì)初，全球制造業(yè)迅速發(fā)展，很多企業(yè)面臨著一個(gè)共同的問題，即如何統(tǒng)籌安排各部門的生產(chǎn)從而在現(xiàn)有的生產(chǎn)條件下獲得最大的產(chǎn)出，排序(又稱調(diào)度、排程或時(shí)間表)理論應(yīng)運(yùn)而生。排序問題是一類重要的組合最優(yōu)化問題，早期源于機(jī)器制造業(yè)，現(xiàn)在已逐漸發(fā)展成為運(yùn)籌學(xué)、控制科學(xué)、管理科學(xué)與工程、系統(tǒng)科學(xué)和計(jì)算機(jī)科學(xué)等多個(gè)學(xué)科領(lǐng)域的交叉學(xué)科，它在生產(chǎn)作業(yè)安排、工程進(jìn)度的控制、制造業(yè)工廠的最優(yōu)設(shè)計(jì)等方面有著深刻的實(shí)際背景和廣闊的應(yīng)用前景(唐恒永和趙傳立[1]，唐國春等[2]，Pinedo[3]，Gawiejnowicz[4]，唐國春[5-6])。

在經(jīng)典的排序問題中，通常假設(shè)工件的加工時(shí)間為常數(shù)。但在某些實(shí)際問題中，工件的加工時(shí)間可能與工件的開工時(shí)間有關(guān)，由此產(chǎn)生具有惡化工件(deteriorating job)的排序問題，即工件的加工時(shí)間隨著開工時(shí)間的延后而增大，這類問題在鋼鐵工業(yè)、塑料工業(yè)、軍事、醫(yī)療及物流和供應(yīng)鏈管理等方面有著廣泛的應(yīng)用。如在軍事方面，當(dāng)天氣漸漸變壞或者天色漸漸變黑時(shí)，目標(biāo)探測開始的時(shí)間越晚則所花費(fèi)的時(shí)間就越長；在消防工程中，救火的開始時(shí)間一旦被耽擱，火勢就會(huì)難以控制，這樣救火的時(shí)間將會(huì)變長，所付出的代價(jià)也會(huì)變大。再比如，在鋼鐵制造企業(yè)的連鑄-軋制生產(chǎn)過程中，煉鋼的基本單元是爐次，它是指同一座轉(zhuǎn)爐一次共同冶煉的鋼水。在煉鋼的連鑄階段，高溫熔融鋼水在連鑄機(jī)底部連續(xù)凝固成鋼坯。當(dāng)?shù)却龝r(shí)間增加時(shí)(即加工開始時(shí)間延后)，在連鑄機(jī)上加工的爐次的溫度將會(huì)降低，從而造成爐次加工時(shí)間的惡化(劉鵬等[7])。近幾年，關(guān)于惡化工件的問題得到了越來越多的關(guān)注，也取得了很多的研究成果(Gupta和Gupta[8]，Browne和Yechiali[9]，Mosheiov[10]，趙傳立等[11]，Wang等[12]，Wang等[13]，王吉波等[14])。在另一方面，流水作業(yè)排序廣泛存在于工業(yè)生產(chǎn)中，它是許多實(shí)際流水線生產(chǎn)排序問題的簡化模型(Framinan等[15]，Ruiz 和 Maroto[16]，Emmons和Vairaktarakis[17]，F(xiàn)ernandez-Viagas和Framinan[18])。具有惡化工件的流水作業(yè)排序問題大多數(shù)是NP-難問題，同時(shí)由于依賴開工時(shí)間的流水作業(yè)排序問題有著深刻的實(shí)際背景與廣闊的應(yīng)用前景，因此，深入研究依賴開工時(shí)間的流水作業(yè)排序問題，對于排序理論的發(fā)展與實(shí)際問題的解決都具有重要的意義。本文介紹了具有依賴開工時(shí)間惡化工件的流水作業(yè)排序問題，總結(jié)了相關(guān)研究的成果和特點(diǎn)，重點(diǎn)綜述了具有正則目標(biāo)函數(shù)的流水作業(yè)排序問題。最后，指出了存在的不足及進(jìn)一步研究的問題和方向。

1　問題描述

具有依賴開工時(shí)間惡化工件流水作業(yè)排序問題可描述為：設(shè)有n個(gè)工件N={J1,J2,…,Jn}依次要在m臺(tái)機(jī)器M={M1,M2,…,Mm}上進(jìn)行加工，在任何時(shí)刻一臺(tái)機(jī)器只能加工一個(gè)工件，工件加工過程不允許中斷，在每臺(tái)機(jī)器上工件的加工順序相同，即排列排序(permutation scheduling)。工件Jj在機(jī)器Mi上的工序記為Oij，一般惡化函數(shù)假定工序Oij的實(shí)際加工時(shí)間為

pij(t)=aij+fij(t)，

(1)

其中aij≥0為工序Oij的基本加工時(shí)間，fij(t)為工序Oij的任意非負(fù)函數(shù)，i=1,2,…,m，j=1,2,…,n,t為工序Oij的開始加工時(shí)間。如果fij(t)=bijt，則得一般線性惡化函數(shù)，即工序Oij的實(shí)際加工時(shí)間為

pij(t)=aij+bijt ，

(2)

下面我們給出一些概念。

優(yōu)勢機(jī)：對于機(jī)器Mr和Mk，如果max{arj∶1≤j≤n}≤min{akj∶1≤j≤n}(或max{brj∶1≤j≤n}≤min{bkj∶1≤j≤n})，則稱機(jī)器Mk優(yōu)于機(jī)器Mr，可以簡寫為Mk>Mr。這樣我們可以定義系列優(yōu)勢機(jī)器：

(a)機(jī)器M1，M2，…，Mm組成遞增列優(yōu)勢機(jī)(idm)，即M1

(b)機(jī)器M1,M2,…,Mm組成遞減列優(yōu)勢機(jī)(ddm)，即M1>M2>…>Mm；

(c)機(jī)器M1,M2,…,Mm組成遞增-遞減列優(yōu)勢機(jī)(idm-ddm)，即

M1Mh+1>…>Mm，其中1≤h≤m；

(d)機(jī)器M1,M2,…,Mm組成遞減-遞增列優(yōu)勢機(jī)(ddm-idm)，即

M1>M2>…>Mh

(e)機(jī)器M1,M2,…,Mm組成遞增-遞減-遞增列優(yōu)勢機(jī)(idm-ddm-idm)，即

M1Mh+1>…>Mi

(f)機(jī)器M1,M2,…,Mm組成遞減-遞增-遞減列優(yōu)勢機(jī)(ddm-idm-ddm)，即

M1>M2>…>MhMi+1>…>Mm，其中1≤h≤i≤m。

機(jī)器無空閑(no-idle)：加工工件的機(jī)器不允許在兩個(gè)相鄰的工件間有空閑。

工件不等待(no-wait)：被加工的工件不允許在兩臺(tái)相鄰的機(jī)器間等待。

2　最小化時(shí)間表長目標(biāo)函數(shù)

本節(jié)主要考慮目標(biāo)函數(shù)為時(shí)間表長(makespan)的排序問題，時(shí)間表長也稱加工時(shí)間全長或最大完工時(shí)間，代表著機(jī)器使用效率的高低。

2.1兩臺(tái)機(jī)器情況

Kononov和Gawiejnowicz[19]證明了問題F2|pij(t)=aij+bijt|Cmax是強(qiáng)NP-難的。

Kononov[20]與Mosheiov[21]同時(shí)應(yīng)用Johnson算法(Johnson[22])證明了問題F2|pij(t)=bijt|Cmax能夠在O(nlogn)時(shí)間內(nèi)解決，并給出了求解算法。

趙傳立等[23]證明了問題F2|pij(t)=bij(A+Bt)|Cmax能夠應(yīng)用Johnson算法在O(nlogn)時(shí)間內(nèi)解決，并給出了求解算法。

Lee等[24]研究了所有工件的惡化率都相等的具有2臺(tái)機(jī)器的問題F2|pij(t)|=aij+bt|Cmax，他們給出了分支定界算法和3個(gè)啟發(fā)式算法來求解這個(gè)問題。

Zhao和Tang[25]研究了具有2臺(tái)機(jī)器的問題F2|pij(t)=bijt,chains|Cmax，其中chains表示工件間具有鏈優(yōu)先約束。他們證明了對一種機(jī)器獨(dú)立的鏈優(yōu)先約束(type 1鏈優(yōu)先約束)問題是多項(xiàng)式時(shí)間可解的，同時(shí)他們證明了對另一種機(jī)器獨(dú)立的鏈優(yōu)先約束(type 2鏈優(yōu)先約束)問題是NP-難的。

2.2三臺(tái)機(jī)器情況

Kononov[20]研究了具有簡單線性惡化的3臺(tái)機(jī)器的流水作業(yè)的排序問題，證明了問題F3|pij(t)=bijt|Cmax是強(qiáng)NP-難的。同樣，Mosheiov[21]證明了問題F3|pij(t)=bijt|Cmax是一般NP-難的。對于問題F3|pij(t)=bijt|Cmax，即使在第一臺(tái)機(jī)器M1與第三臺(tái)機(jī)器M3的惡化率相同，即bi1=bi3=b，也很難提出近似算法。Kononov和Gawiejnowicz[19]研究了問題F3|pij(t)=bijt,bi1=bi3=b|Cmax，結(jié)果表明：除了在P=NP的情況下，不存在最壞情況界為常數(shù)的多項(xiàng)式時(shí)間近似算法。

Wang等[26]研究了三臺(tái)機(jī)器的流水作業(yè)排序問題F3|pij(t)=bijt|Cmax，他們證明一些特殊情況，即問題F3|pij(t)=bijt,M1>M2|Cmax，F(xiàn)3|pij(t)=bijt,M3>M2|Cmax，F(xiàn)3|pij(t)=bijt,M2>M1|Cmax，F(xiàn)3|pij(t)=bijt,M2>M3|Cmax，都是多項(xiàng)式時(shí)間可解的，并對一般問題F3|pij(t)=bijt|Cmax，給出了分支定界算法和一個(gè)啟發(fā)式算法。

Wang和Wang[27]研究了三臺(tái)機(jī)器的流水作業(yè)排序問題F3|pij(t)=aij+bt|Cmax，他們給出一些優(yōu)勢性質(zhì)和下界，從而給出了分支定界算法。為了克服分支定界算法慢的特性，他們也提出了二個(gè)啟發(fā)式算法，并用數(shù)值算例說明了分支定界算法處理的問題規(guī)模和啟發(fā)式算法的效果。

Wang和Wang[28]研究了三臺(tái)機(jī)器的流水作業(yè)排序問題F3|pij(t)=bij(A+Bt)|Cmax，他們證明一些特殊情況，即問題F3|pij(t)=bij(A+Bt),M1>M2|Cmax，F(xiàn)3|pij(t)=bij(A+Bt),M3>M2|Cmax，F(xiàn)3|pij(t)=bij(A+Bt),M2>M1|Cmax，F(xiàn)3|pij(t)=bij(A+Bt),M2>M3|Cmax都是多項(xiàng)式時(shí)間可解的，并對一般問題F3|pij(t)=bij(A+Bt)|Cmax給出了分支定界算法和一個(gè)啟發(fā)式算法。

2.3m臺(tái)機(jī)器情況

趙傳立等[23]研究了m臺(tái)機(jī)器的流水作業(yè)排序問題Fm|pij(t)=bij(A+Bt)|Cmax，證明了當(dāng)所有工件在每臺(tái)機(jī)器上的惡化率都相等時(shí)(即bij=bj,j=1,2,…,n)，問題Fm|pij(t)=bij(A+Bt),bij=bj|Cmax是獨(dú)立于工件排列順序的，即任意排序都是最優(yōu)排序。

趙傳立等[30]研究了m臺(tái)機(jī)器的流水作業(yè)排序問題Fm|pij(t)=bijt,β|Cmax，其中β∈{idm,ddm,idm-ddm}。他們對這三種特殊情況分別給出了多項(xiàng)式時(shí)間算法。

Wang和Xia[31]研究了m臺(tái)機(jī)器的流水作業(yè)排序問題Fm|pij(t)=bijt，β|Cmax，其中β∈{idm,ddm,idm-ddm,ddm-idm}。他們對一些工件不等待(no-wait)情況、機(jī)器無空閑(no-idle)情況和一般(沒有工件不等待和機(jī)器無空閑限制)情況(即Fm|pij(t)=bijt，no-wait,β|Cmax，其中β∈{idm,ddm,idm-ddm}，和Fm|pij(t)=bijt,no-idle,β|Cmax，其中β∈{idm,ddm,idm-ddm,ddm-idm})，分別給出了多項(xiàng)式時(shí)間算法。

Wang和Xia[32]研究了與Wang和Xia[31]類似的問題，只是Wang和Xia[31]研究的是成比例惡化函數(shù)(即aij=kbij)。對問題Fm|pij(t)=kbij+bijt,β|Cmax，其中β∈{idm,ddm,idm-ddm,ddm-idm}得到了與Wang和Xia[31]類似的結(jié)論。

Cheng等[33]研究了問題Fm|pij(t)=aij+bt,no-idle，β|Cmax,其中β∈{idm,ddm,idm-ddm,ddm-idm}。他們對機(jī)器滿足優(yōu)勢關(guān)系的特殊情況(即β∈{idm,ddm,idm-ddm,ddm-idm})，分別給出了多項(xiàng)式時(shí)間算法。

潘明和趙傳立[34]研究了問題Fm|pij(t)=aij+bt,no-idle，β|Cmax，其中機(jī)器滿足優(yōu)勢關(guān)系β∈{idm-ddm-idm，ddm-idm-ddm}。他們對這兩種特殊情況分別給出了多項(xiàng)式時(shí)間算法。

Sun等[35]研究了同Cheng等[33]一樣的問題(即問題Fm|pij(t)=aij+bt,no-idle，β|Cmax，其中β∈{idm，ddm，idm-ddm，ddm-idm})，他們用反例說明了Cheng等[33]中的一些結(jié)論是不正確的，并給出了修正過的相關(guān)結(jié)論。

Ng等[36]研究了問題Fm|pij(t)=aij+bt,β|Cmax，其中β∈{idm,ddm,idm-ddm,ddm-idm,no-wait,no-idle}。他們對一些工件不等待情況、機(jī)器無空閑情況和一般(沒有工件不等待和機(jī)器無空閑限制)情況(即問題Fm|pij(t)=aij+bt,β|Cmax，其中β∈{idm,ddm,idm-ddm}，F(xiàn)m|pij(t)=aij+bt,no-wait,β|Cmax，其中β∈{idm,ddm,idm-ddm}，和Fm|pij(t)=aij+bt,no-idle,β|Cmax，其中β∈{idm,ddm,idm-ddm,ddm-idm})，分別給出了多項(xiàng)式時(shí)間算法。

Sun等[37]研究了所有工件的基本加工時(shí)間都相等的流水作業(yè)排序問題Fm|pij(t)=a+bijt,β|Cmax，其中β∈{idm,ddm,idm-ddm,ddm-idm,no-wait,no-idle}。他們對一些特殊情況(即問題Fm|pij(t)=a+bijt,β|Cmax，其中β∈{idm,ddm,idm-ddm}，F(xiàn)m|pij(t)=a+bijt,no-wait,β|Cmax，其中β∈{idm,ddm,idm-ddm}，和Fm|pij(t)=a+bijt,no-idle,β|Cmax，其中β∈{idm,ddm,idm-ddm,ddm-idm})，分別給出了多項(xiàng)式時(shí)間算法。

Wang[38]研究了m臺(tái)機(jī)器的流水作業(yè)排序問題Fm|pij(t)=bijt,β|Cmax，其中β∈{M1>M2>…>Mm-1,M2>…>Mm-1>Mm,M1…>Mm-1,M2<……>Mm-1>Mm},即m-1臺(tái)機(jī)器具有優(yōu)勢關(guān)系。他們對這幾種特殊情況分別給出了多項(xiàng)式時(shí)間算法。

Yin和Kang[39]研究了m臺(tái)機(jī)器的流水作業(yè)排序問題Fm|pij(t)=bij(A+Bt),β|Cmax，其中β∈{M1>M2>…>Mm-1,M2>…>Mm-1>Mm,M1…>Mm-1,M2<……>Mm-1>Mm}，即m-1臺(tái)機(jī)器具有優(yōu)勢關(guān)系。他們對這幾種特殊情況分別給出了多項(xiàng)式時(shí)間算法，同時(shí)他們對一般情況給出了(即問題Fm|pij(t)=bij(A+Bt)|Cmax)一個(gè)啟發(fā)式算法。

表1　時(shí)間表長目標(biāo)函數(shù)Cmax

3　最小化總完工時(shí)間目標(biāo)函數(shù)

本節(jié)主要考慮目標(biāo)函數(shù)為總完工時(shí)間(也稱完工時(shí)間和)的排序問題，總完工時(shí)間代表著所有工件的加工時(shí)間成本。

3.1兩臺(tái)機(jī)器情況

Wang等[40]和Shiau等[41]分別研究了具有2臺(tái)機(jī)器的問題F2|pij(t)=bijt|∑Cj，Wang等[40]證明了問題F2|pij(t)=bijt|∑Cj的一些特殊情況(即問題F2|pij(t)=bijt,b2j=b|∑Cj，F(xiàn)2|pij(t)=bijt,M1M2|∑Cj，F(xiàn)2|pij(t)=bijt,b1j=b2j|∑Cj)是多項(xiàng)式時(shí)間可解的，同時(shí)對一般問題F2|pij(t)=bijt|∑Cj)，給出了分支定界算法和1個(gè)啟發(fā)式算法。Shiau等[41]對問題F2|pij(t)=bijt|∑Cj給出了分支定界算法、3個(gè)啟發(fā)式算法和一個(gè)模擬退火算法來求解這個(gè)問題。

Wu和Lee[42]研究了所有工件的惡化率都相等的具有2臺(tái)機(jī)器的問題F2|pij(t)=aij+bt|∑Cj，此問題是NP-難得，他們給出了分支定界算法和3個(gè)啟發(fā)式算法及一個(gè)改進(jìn)算法來求解這個(gè)問題。

Ng等[43]研究了問題F2|pij(t)=bij(A+Bt)|∑Cj，此問題是NP-難得，他們給出了一些優(yōu)勢性質(zhì)，4個(gè)下界和一個(gè)啟發(fā)式算法作為上界，從而可用分支定界算法來求解這個(gè)問題，數(shù)值模擬說明了分支定界算法能在合理的時(shí)間內(nèi)處理n=15的規(guī)模問題。

Cheng等[44]研究了具有2臺(tái)機(jī)器的雙目標(biāo)問題，即問題F2|pij(t)=bijt|Fh(∑Cj|Cmax)，其中Fh(∑Cj|Cmax)表示在Cmax極小的條件下求∑Cj最小。對這個(gè)問題，Cheng等[44]給出了一個(gè)混合整數(shù)規(guī)劃模型，并提出了2個(gè)啟發(fā)式算法和分支定界算法。

3.2m臺(tái)機(jī)器情況

趙傳立等[23]研究了m臺(tái)機(jī)器的流水作業(yè)排序問題Fm|pij(t)=bij(A+Bt)|∑Cj，證明了問題Fm|pij(t)=bij(A+Bt),bij=bj|∑Cj能夠在O(nlogn)時(shí)間內(nèi)解決，即把工件按照惡化率bj非增的順序排列得最優(yōu)排序。

Cheng等[33]研究了問題Fm|pij(t)=aij+bt,no-idle,β|∑Cj，其中β∈{idm,ddm,idm-ddm,ddm-idm}。他們對機(jī)器滿足優(yōu)勢關(guān)系的特殊情況(即β∈{idm,ddm,idm-ddm,ddm-idm})，分別給出了多項(xiàng)式時(shí)間算法。

潘明和趙傳立[34]研究了問題Fm|pij(t)=aij+bt,no-idle,β|∑Cj，其中機(jī)器滿足優(yōu)勢關(guān)系β∈{idm-ddm-idm,ddm-idm-ddm}。他們對這兩種特殊情況分別給出了多項(xiàng)式時(shí)間算法。

Sun等[35]研究了同Cheng等[33]一樣的問題(即問題Fm|pij(t)=aij+bt,no-idle,β|∑Cj，其中β∈{idm,ddm,idm-ddm,ddm-idm})，他們用反例說明了Cheng等[33]中的一些結(jié)論是不正確的，并給出了修正過的相關(guān)結(jié)論。

Ng等[36]研究了問題Fm|pij(t)=aij+bt,β|∑Cj，其中β∈{idm,ddm,idm-ddm,ddm-idm,no-wait,no-idle}。他們對一些工件不等待情況、機(jī)器無空閑情況和一般(沒有工件不等待和機(jī)器無空閑限制)情況(即問題Fm|pij(t)=aij+bt,β|∑Cj，其中β∈{idm,ddm,idm-ddm}，F(xiàn)m|pij(t)=aij+bt,no-wait,β|∑Cj，其中β∈{idm,ddm,idm-ddm}，和Fm|pij(t)=aij+bt,no-idle,β|∑Cj，其中β∈{idm,ddm,idm-ddm,ddm-idm})，分別給出了多項(xiàng)式時(shí)間算法。

Lee等[45]研究了每臺(tái)機(jī)器的惡化率不同的排序問題Fm|pij(t)=aij+bit|∑Cj，他們給出了分支定界算法和多種啟發(fā)式算法來求解這個(gè)問題，并對這些算法進(jìn)行了比較。

4　極小化其它目標(biāo)函數(shù)

本節(jié)主要考慮一些其它的目標(biāo)函數(shù)，包括最大延遲(遲后)時(shí)間、加權(quán)總完工時(shí)間、最大費(fèi)用、總延誤時(shí)間。

表2　總完工時(shí)間目標(biāo)函數(shù)∑Cj

4.1兩臺(tái)機(jī)器情況

Kononov[20]證明了問題F2|pij(t)=bijt|Lmax是強(qiáng)NP-難的。

Yang和Wang[46]研究了具有2臺(tái)機(jī)器的問題F2|pij(t)=bijt|∑wjCj，他們證明了一些特殊情況(包括問題F2|pij(t)=bijt,M1M2|∑wjCj)是多項(xiàng)式時(shí)間可解的。同時(shí)他們對一般情況，給出了一個(gè)分支定界算法和1個(gè)啟發(fā)式算法，并給出了數(shù)值模擬。

Bank等[47]研究了具有2臺(tái)機(jī)器的問題F2|pij(t)=bij(A+Bt)|∑Tj，他們給出了分支定界算法，計(jì)算結(jié)果表明，分支定界算法比較有效。

4.2m臺(tái)機(jī)器情況

趙傳立等[23]研究了m臺(tái)機(jī)器的流水作業(yè)排序問題Fm|pij(t)=bij(A+Bt)|hmax，證明了問題Fm|pij(t)=bij(A+Bt),bij=bj|hmax能夠在O(nlogn)時(shí)間內(nèi)解決。他們還證明了當(dāng)hmax=Lmax時(shí)，最優(yōu)排序能夠通過EDD規(guī)則(即時(shí)把工件按照工期dj非增的順序排列)得到。

趙傳立等[30]研究了m臺(tái)機(jī)器的流水作業(yè)排序問題Fm|pij(t)=bijt,idm|∑wjCj和Fm|pij(t)=bijt,idm|Lmax。他們對這兩個(gè)問題分別給出了多項(xiàng)式時(shí)間算法。

Wang和Xia[31]研究了m臺(tái)機(jī)器的流水作業(yè)排序問題Fm|pij(t)=bijt,β|γ，其中β∈{idm,ddm,idm-ddm,ddm-idm}，γ∈{Lmax,Tmax,∑wjCj}。他們對一些工件不等待(no-wait)情況、機(jī)器無空閑(no-idle)情況和一般(沒有工件不等待和機(jī)器無空閑限制)情況(即Fm|pij(t)=bijt,β|∑wjCj，其中β∈{ddm,idm-ddm}，F(xiàn)m|pij(t)=bijt,no-wait,β|∑wjCj，其中β∈{idm,ddm,idm-ddm}，F(xiàn)m|pij(t)=bijt,no-idle,β|∑wjCj，其中β∈{idm,ddm,idm-ddm,ddm-idm}，F(xiàn)m|pij(t)=bijt,no-wait,idm|Lmax和Fm|pij(t)=bijt,no-idle，β|Lmax，其中β∈{idm,ddm,idm-ddm,ddm-idm})，分別給出了多項(xiàng)式時(shí)間算法。

Wang和Xia[32]研究了與Wang和Xia[31]類似的問題，只是Wang和Xia[32]研究的是成比例惡化函數(shù)(即aij-kbij)。

Lee等[48]研究了問題Fm|pij(t)=aij+bit|∑Tj，他們給出了分支定界算法和模擬退化算法、粒子群優(yōu)化算法兩種啟發(fā)式算法來求解這個(gè)問題，并對這些算法進(jìn)行了比較，比較結(jié)果表明：當(dāng)工件規(guī)模較小時(shí),由于兩種啟發(fā)式算法的執(zhí)行時(shí)間都不到一分鐘，沒有誰更占主導(dǎo)性地位，兩種算法都比較適用；對于大規(guī)模的工作,模擬退化算法在精確性和執(zhí)行時(shí)間上占有很大的優(yōu)勢。

Bank等[49]研究了問題Fm|pij(t)=bij(A+Bt)|∑Tj，他們給出了粒子群算法和模擬退火算法，計(jì)算結(jié)果表明，具有局部搜索的粒子群算法優(yōu)于模擬退火算法。

表3　其他目標(biāo)函數(shù)

5　結(jié)論及展望

具有依賴開工時(shí)間惡化工件的流水作業(yè)排序問題是一類很有意義的排序問題，相關(guān)的研究已經(jīng)有了一些成果(可參見表1-3)。目標(biāo)函數(shù)主要包括最流行的Cmax和∑Cj，和一些不太流行的∑wjCj，∑Tj，Tmax和Lmax。所用的方法包括復(fù)雜性分析、啟發(fā)式算法、分支定界法、模擬退化算法、粒子群優(yōu)化算法等。除了本文提到的研究，下面的一些問題仍然沒有被解決，值得研究，比如：

(1)已有研究的成果都是假定惡化(縮短)函數(shù)為簡單或特殊的線性函數(shù)，然而對于一般線性函數(shù)(即pij(t)=aij+bijt)或非線性函數(shù)，研究的結(jié)果很少。因此，對于一般的線性函數(shù)(即pij(t)=aij+bijt)或非線性函數(shù)，研究使最大完工時(shí)間、(加權(quán))總完工時(shí)間極小化問題，這些問題大多數(shù)是NP-難的，對這些問題如何設(shè)計(jì)求解算法，得到一般性結(jié)論。

(2)根據(jù)上面的研究綜述，大多數(shù)的研究是單目標(biāo)問題，對于多目標(biāo)問題結(jié)果卻很少(除了文獻(xiàn)Cheng等[44])。因此，探討多目標(biāo)問題的計(jì)算復(fù)雜性及求解算法，特別是研究雙目標(biāo)函數(shù)的四種組合，即對于目標(biāo)γ1和γ2，研究λγ1+(1-λ)γ2極小化問題(P1問題)；研究在γ1≤Υ(γ2≤K)條件下極小化γ2(γ1)問題(P2(P3)問題)；研究(γ1,γ2)的Pareto-最優(yōu)解集合問題(假如不存在另一個(gè)排序π′滿足γ1(π′)≤γ1(π)和γ2(π′)≤γ2(π)，且其中至少一個(gè)不等式嚴(yán)格成立，則排序π是Pareto-最優(yōu)解，簡記為P4問題)。

[1]唐恒永,趙傳立.排序引論[M].北京:科學(xué)出版社,2002.

[2]唐國春,張峰,羅守成,等.現(xiàn)代排序論[M].上海:上海科學(xué)普及出版社,2003.

[3]PINEDO M L.Scheduling:Theory,Algorithms,and Systems[M].3rd ed.New York:Springer-Verlag New York Inc,2008.

[4]GAWIEJNOWICZ S.Time-Dependent Scheduling[M].Berlin:Springer,2008.

[5]唐國春.關(guān)于Scheduling中文譯名的注記[J].系統(tǒng)管理學(xué)報(bào),2010,19(6):713-716.

[6]唐國春.排序論基本概念綜述[J].重慶師范大學(xué)學(xué)報(bào),2012,29(4):1-11.

[7]劉鵬,周曉曄,衣娜.帶有減少線性惡化效應(yīng)的雙代理調(diào)度問題[J].系統(tǒng)工程學(xué)報(bào),2011,26(3):387-392.

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

[9]BROWNE S,YECHIALI U.Scheduling deteriorating jobs on a single processor[J].Operations Research,1990,38(3):495-498.

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

[11]趙傳立,張慶靈,唐恒永.一類線性加工時(shí)間單機(jī)調(diào)度問題[J].自動(dòng)化學(xué)報(bào),2003,29(05):703-708.

[12]WANG J B,WANG J J,JI P.Scheduling jobs with chain precedence constraints and deteriorating jobs[J].Journal of the Operational Research Society,2011,62(9):1765-1770.

[13]WANG J B,HUANG X,WU Y B,et al.Group scheduling with independent setup times,ready times,and deteriorating job processing times[J].International Journal of Advanced Manufacturing Technology,2011,60(5-8):643-649.

[14]王吉波,劉璐,許揚(yáng)濤,等.具有惡化工件的不同工期指派問題研究[J].沈陽航空航天大學(xué)學(xué)報(bào),2013,30(5):83-87.

[15]FRAMINAN J,GUPTA J,LEISTEN R.A review and classification of heuristics for permutation flow-shop scheduling with makespan objective[J].Journal of the Operational Research Society,2004,55(12):1243-1255.

[16]RUIZ R,MAROTO C.A comprehensive review and evaluation of permutation flowshop heuristics[J].European Journal of Operational Research,2005,165(2):479-494.

[17]EMMONS H,VAIRAKARAKIS G.Flow shop scheduling-theoretical results,algorithms and applications[M].Berlin:Springer,2013.

[18]FERNANDEZ-VIAGAS V,FRAMINAN J M.NEH-based heuristics for the permutation flowshop scheduling problem to minimise total tardiness[J].Computers & Operations Research,2015,60(C):27-36.

[19]KONONOV A,GAWIEJNOWICZ S.NP-hard cases in scheduling deteriorating jobs on dedicated machines[J].Journal of the Operational Research Society,2001,52(6):708-717.

[20]KONONOV A.Combinatorial complexity of scheduling jobs with simple linear deterioration[J].Discrete Analysis and Operations Research,1996,3(2):15-32.

[21]MOSHEIOV G.Complexity analysis of job-shop scheduling with deteriorating jobs[J].Discrete Applied Mathematics,2002,117(1-3):195-209.

[22]JOHNSON S M.Optimal two and three stage production schedules with setup times included[J].Naval Research Logistics Quarterly,1954,1(1):61-68.

[23]趙傳立,張慶靈,唐恒永.具有線性惡化加工時(shí)間的調(diào)度問題[J].自動(dòng)化學(xué)報(bào),2003,29(04):531-535.

[24]LEE W C,WU C C,WEN C C,et al.A two-machine flowshop makespan scheduling problem with deteriorating jobs[J].Computers & Industrial Engineering,2008,54(4):737-749.

[25]ZHAO C,TANG H.Two-machine flow shop scheduling with deteriorating jobs and chain precedence constraints[J].International Journal of Production Economics,2012,136(1):131-136.

[26]WANG L,SUN L Y,SUN L H,et al.On three-machine flow shop scheduling with deteriorating jobs[J].International Journal of Production Economics,2010,125(1):185-189.

[27]WANG J B,WANG M Z.Minimizing makespan in three-machine flow shops with deteriorating jobs[J].Computers & Operations Research,2013,40(2):547-557.

[28]WANG J B,WANG M Z.Makespan minimization on three-machine flow shop with deteriorating jobs[J].Asia-Pacific Journal of Operational Research,2013,30(6):1350022-1-1350022-14.

[29]MELNIKOV O I,SHAFRANSKY Y M.Parametric problem in scheduling theory[J].Cybernetics,1979,15(3):352-357.

[30]趙傳立,張慶靈,唐恒永.加工時(shí)間依賴開工時(shí)間的Flow Shop調(diào)度問題[J].系統(tǒng)工程與電子技術(shù),2003,25(3):292-294.

[31]WANG J B,XIA Z Q.Flow shop scheduling with deteriorating jobs under dominating machines[J].Omega,2006,34(4):327-336.

[32]WANG J B,XIA Z Q.Flow shop scheduling problems with deteriorating jobs under dominating machines[J].Journal of the Operational Research Society,2006,57(2):220-226+7.

[33]CHENG M,SUN S,HE L.Flow shop scheduling problems with deteriorating jobs on no-idle dominant machines[J].European Journal of Operational Research,2007,183(1):115-124.

[34]潘明,趙傳立.具有優(yōu)勢機(jī)器和惡化工件的流水作業(yè)排序問題[J].系統(tǒng)管理學(xué)報(bào),2008,17(6):686-692.

[35]SUN L H,SUN L Y,CUI K,et al.A note on flow shop scheduling problems with deteriorating jobs on no-idle dominant machines[J].European Journal of Operational Research,2010,200(1):309-311.

[36]NG C T,WANG J B,CHENG T C E,et al.Flowshop scheduling of deteriorating jobs on dominating machines[J].Computers & Industrial Engineering,2011,61(3):647-654.

[37]SUN L H,SUN L Y,WANG M Z,et al.Flow shop makespan minimization scheduling with deteriorating jobs under dominating machines[J].International Journal of Production Economics,2012,138(1):195-200.

[38]WANG J B.Flow shop scheduling with deteriorating jobs under dominating machines to minimize makespan[J].International Journal of Advanced Manufacturing Technology,2010,48(5):719-723.

[39]YIN N,KANG L.Minimizing makespan in permutation flow shop scheduling with proportional deterioration[J].Asia-Pacific Journal of Operational Research,2015,32(6):1550050-01-1550050-12.

[40]WANG J B,NG C T,CHENG T C E,et al.Minimizing total completion time in a two-machine flow shop with deteriorating jobs[J].Applied Mathematics and Computation,2006,180(1):185-193.

[41]SHIAU Y R,LEE W C,WU C C,et al.Two-machine flowshop scheduling to minimize mean flow time under simple linear deterioration[J].International Journal of Advanced Manufacturing Technology,2007(34):774-782.

[42]WU C C,LEE W C.Two-machine flowshop scheduling to minimize mean flow time under linear deterioration[J].International Journal of Production Economics,2006,103(2):572-584.

[43]NG C T,WANG J B,CHENG T C E,et al.A branch-and-bound algorithm for solving a two-machine flow shop problem with deteriorating jobs[J].Computers and Operations Research,2010,37(1):83-90.

[44]CHENG M,TADIKAMALLA P R,SHANG J,et al.Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs[J].European Journal of Operational Research,2014,234(3):650-657.

[45]LEE W C,WU C C,CHUNG Y H,et al.Minimizing the total completion time in permutation flow shop with machine-dependent job deterioration rates[J].Computers and Operations Research,2009,36(6):2111-2121.

[46]YANG S H,WANG J B.Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration[J].Applied Mathematics and Computation,2011,217(9):4819-4826.

[47]BANK M,FATEMI GHOMI SMT,JOLAI F,et al.Two-machine flow shop total tardiness scheduling problem with deteriorating jobs[J].Applied Mathematical Modelling,2012,36(11):5418-5426.

[48]LEE W C,YEH W C,CHUNG Y H.Total tardiness minimization in permutation flowshop with deterioration consideration[J].Applied Mathematical Modelling,2014(38):3081-3092.

[49]BANK M,FATEMI GHOMI SMT,JOLAI F,et al.Application of particle swarm optimization and simulated annealing algorithms in flow shop scheduling problem under linear deterioration[J].Advances in Engineering Software,2012,47(1):1-6.

(責(zé)任編輯：陳素清英文審校：劉勇進(jìn))

Survey on flow shop scheduling problems with start time dependent deteriorating jobs

WANG Ji-bo1,2,GUO Miao-miao1,LIU Huan3，LI Lin2,WANG Dan4

(1.College of Economics and Management,Shenyang Aerospace University,Shenyang 110136,China;2.College of Science,Shenyang Aerospace University,Shenyang 110136,China;3.Department of Educational Administration,Liaoning Sports School,Shenyang 110179,China;4.College of Computer Science,Shenyang Aerospace University,Shenyang 110136,China)

Scheduling with deteriorating jobs is important in manufacturing,operations research,and management science and engineering,and it is widely used in such fields as iron and steel,plastic,military and medical industries.This paper introduced the characteristics of the flow shop scheduling with start-time dependent deteriorating jobs whose objectives functions mainly included the make-span,total completion time,total weighted completion time,maximum lateness and total tardiness.Then it gived an overall survey on the scheduling,and points out the existing drawback and many problems to be solved.Finally,further relative researches were suggested.

scheduling;flow shop;deteriorating job

2095-1248(2016)03-0001-10

2016-04-11

國家自然科學(xué)基金(項(xiàng)目編號(hào)：61403260；71471120)

王吉波(1975-),男,遼寧沈陽人，教授,博士后，博士生導(dǎo)師，主要研究方向：生產(chǎn)計(jì)劃與排序，E-mail：wangjibo75@163.com。

O223；C934

A

10.3969/j.issn.2095-1248.2016.03.001