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

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

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

?

名家綜述

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

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

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

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

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

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

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

1　問題描述

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

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

(1)

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

pij(t)=aij+bijt ，

(2)

下面我們給出一些概念。

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

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

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

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

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

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

M1>M2>…>Mh

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

M1Mh+1>…>Mi

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

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

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

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

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

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

2.1兩臺機器情況

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

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

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

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

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

2.2三臺機器情況

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

Wang等[26]研究了三臺機器的流水作業(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，都是多項式時間可解的，并對一般問題F3|pij(t)=bijt|Cmax，給出了分支定界算法和一個啟發(fā)式算法。

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

Wang和Wang[28]研究了三臺機器的流水作業(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都是多項式時間可解的，并對一般問題F3|pij(t)=bij(A+Bt)|Cmax給出了分支定界算法和一個啟發(fā)式算法。

2.3m臺機器情況

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

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

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

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}。他們對機器滿足優(yōu)勢關(guān)系的特殊情況(即β∈{idm,ddm,idm-ddm,ddm-idm})，分別給出了多項式時間算法。

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

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}。他們對一些工件不等待情況、機器無空閑情況和一般(沒有工件不等待和機器無空閑限制)情況(即問題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})，分別給出了多項式時間算法。

Sun等[37]研究了所有工件的基本加工時間都相等的流水作業(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})，分別給出了多項式時間算法。

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

Yin和Kang[39]研究了m臺機器的流水作業(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臺機器具有優(yōu)勢關(guān)系。他們對這幾種特殊情況分別給出了多項式時間算法，同時他們對一般情況給出了(即問題Fm|pij(t)=bij(A+Bt)|Cmax)一個啟發(fā)式算法。

表1　時間表長目標函數(shù)Cmax

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

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

3.1兩臺機器情況

Wang等[40]和Shiau等[41]分別研究了具有2臺機器的問題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)是多項式時間可解的，同時對一般問題F2|pij(t)=bijt|∑Cj)，給出了分支定界算法和1個啟發(fā)式算法。Shiau等[41]對問題F2|pij(t)=bijt|∑Cj給出了分支定界算法、3個啟發(fā)式算法和一個模擬退火算法來求解這個問題。

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

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

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

3.2m臺機器情況

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

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

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

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}。他們對一些工件不等待情況、機器無空閑情況和一般(沒有工件不等待和機器無空閑限制)情況(即問題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})，分別給出了多項式時間算法。

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

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

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

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

4.1兩臺機器情況

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

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

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

4.2m臺機器情況

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

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

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

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

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

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

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

5　結(jié)論及展望

具有依賴開工時間惡化工件的流水作業(yè)排序問題是一類很有意義的排序問題，相關(guān)的研究已經(jīng)有了一些成果(可參見表1-3)。目標函數(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ù)，研究使最大完工時間、(加權(quán))總完工時間極小化問題，這些問題大多數(shù)是NP-難的，對這些問題如何設(shè)計求解算法，得到一般性結(jié)論。

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

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

[7]劉鵬,周曉曄,衣娜.帶有減少線性惡化效應(yīng)的雙代理調(diào)度問題[J].系統(tǒng)工程學(xué)報,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]趙傳立,張慶靈,唐恒永.一類線性加工時間單機調(diào)度問題[J].自動化學(xué)報,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]王吉波,劉璐,許揚濤,等.具有惡化工件的不同工期指派問題研究[J].沈陽航空航天大學(xué)學(xué)報,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]趙傳立,張慶靈,唐恒永.具有線性惡化加工時間的調(diào)度問題[J].自動化學(xué)報,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]趙傳立,張慶靈,唐恒永.加工時間依賴開工時間的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)勢機器和惡化工件的流水作業(yè)排序問題[J].系統(tǒng)管理學(xué)報,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é)任編輯：陳素清英文審校：劉勇進)

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é)基金(項目編號：61403260；71471120)

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

O223；C934

A

10.3969/j.issn.2095-1248.2016.03.001