陳　娟

(重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，重慶 401331)

在傳統(tǒng)的排序研究中，一般認(rèn)為工件的加工時間是固定不變的常數(shù)，但是在實(shí)際工業(yè)生產(chǎn)中，比如鋼鐵生產(chǎn)、救助資源分配等問題中，工件越靠后加工，加工時間越長，這就是所熟知的退化效應(yīng).關(guān)于工件退化問題，已經(jīng)有很多研究，其中Mosheiov[1]考慮了線性模型pj(t)=αjt，并證明了最大完工時間、總完工時間、總加權(quán)完工時間、最大延誤時間等問題是多項(xiàng)式時間可解的.Bachman等[2]證明了模型pj(t)=aj+αjt極小化最大延誤問題是NP難的.Wang等[3]考慮了工件同時帶有退化效應(yīng)和學(xué)習(xí)效應(yīng)的單機(jī)排序問題，并用啟發(fā)式算法給出了目標(biāo)函數(shù)為總完工時間問題的解法.

同時，在鋼鐵工業(yè)加工過程中，鋼鐵由于在加工完成后，溫度極高，不能馬上運(yùn)送給客戶，需要一些時間冷卻，因此工件的等待時間會對工件的總完工時間造成影響.電子元件生產(chǎn)過程中也存在類似的影響.針對這種現(xiàn)象，Koulamas等[4]提出將這種不利影響看作是與工件排序有關(guān)的送出時間，為了分析方便，通常假設(shè)送出時間與工件的等待時間成正比例，他們就最大完工時間、總完工時間、最大延誤時間和延誤工件個數(shù)問題，分別給出了最優(yōu)排序規(guī)則.Yin等[5]考慮了成比例線性退化的序列相關(guān)送出時間的單機(jī)排序問題，證明了最大完工時間等問題是多項(xiàng)式可解的，并分析了其他幾個目標(biāo)設(shè)計(jì)啟發(fā)式算法的最差性能比.

筆者考慮帶有退化效應(yīng)和序列相關(guān)送出時間的單機(jī)排序問題，通過把基本加工時間最大的工件放在最后加工得到極小化最大完工時間問題的最優(yōu)排序，證明SPT序?qū)τ跇O小化總完工時間問題是最優(yōu)排序，就基本加工時間和權(quán)重相反一致情形證得WSPT序?qū)τ跇O小化總加權(quán)完工時間是最優(yōu)排序，就工期和基本加工時間一致情形，證明EDD序?qū)τ跇O小化最大延誤問題是最優(yōu)排序.

1　模型描述與符號介紹

Jj第j個工件，其中j=1,2,...,n.

pj工件Jj的基本加工時間,其中j=1,2,...,n.

b工件Jj的退化率，其中j=1,2,...,n.

a正常數(shù).

t所有工件在t時刻可以加工.

n工件的個數(shù).

dj工件Jj的工期.

wj工件Jj的權(quán).

Cj工件Jj的完工時間.

Lmax工件的最大延誤時間.

Cmax工件的最大完工時間.

Cj(S)排序S中的工件Jj的完工時間.

C[j](S)排序S中第j個位置上的工件的完工時間.

q[j]排在第j個位置工件的序列相關(guān)送出時間.

假設(shè)有n個獨(dú)立的工件，用集合表示為J={J1,J2,J3,…,Jn},放在一臺機(jī)器上加工，n個工件無優(yōu)先加工權(quán)，并且在0時刻都可加工，所有工件在加工過程中不允許中斷，一臺機(jī)器也不能同時加工兩個或兩個以上的工件，工件Jj的實(shí)際加工時間表示為：

(1)

為了敘述方便，把方程(1)記為LD.如前所述的送出時間，通常假設(shè)送出時間與工件的等待時間成正比例，排在第j個位置工件的序列相關(guān)送出時間可表示為：

j=2,3,…,n.

第一個工件的完工時間

第j個位置上工件的完工時間：

用∑Cj、∑wjCj、Lmax分別表示總完工時間、加權(quán)總完工時間、最大延誤時間，本文研究的問題用三參數(shù)表示法[6]表示如下：

1|LD,qpsd|Cmax

1|LD,qpsd|∑Cj

1|LD,qpsd|∑wjCj

1|LD,qpsd|Lmax

2　主要結(jié)論

定理1對于問題1|LD,qpsd|Cmax，只要滿足p[n]=max{p1,p2,…,pn}的排序即為最優(yōu)排序.

證因?yàn)?/p>

推論1對于問題1|LD,qpsd|Cmax，按照上述算法得到的最優(yōu)排序，其計(jì)算復(fù)雜性是O(n).

證因?yàn)橹恍枰页鰊個工件中基本加工時間最大的工件，所以其計(jì)算復(fù)雜度為O(n).

上面證明了任何一種p[n]=max{p1,p2,…,pn}的排序?qū)τ趩栴}1|LD,qpsd|Cmax都是最優(yōu)的.接下來研究總完工時間問題.

定理2對于問題1|LD,qpsd|∑Cj，將所有工件按照基本加工時間非減(即：SPT原則)順序排列可得到最優(yōu)排序.

證假設(shè)存在一個最優(yōu)排序S=(π1,Ji,Jj,π2)，其中工件Ji和Jj分別在兩個相鄰的位置，π1和π2是部分排序并且可能為空，假定π1中有r-1個工件，因此工件Jj和Ji分別在第r個和r+1個位置上，并且假定pipj，而通過交換工件Jj和Ji的位置得到另一個排序S'=(π1,Jj,Ji,π2)，為了證明排序S的總完工時間不大于排序S'，實(shí)際只需證明Ci(S)+Cj(S)Ci(S')+Cj(S')和Cj(S)Ci(S')，而

Ci(S)=

Cj(S')=

因?yàn)閜ipj，容易看出Cj(S)Ci(S')，Ci(S)Cj(S')，因此得Ci(S)+Cj(S)Ci(S')+Cj(S')，定理得證.

推論2對于問題1|LD,qpsd|∑Cj，按照SPT規(guī)則得到的最優(yōu)排序，其計(jì)算復(fù)雜度為O(nlogn).

證因?yàn)槭前凑誗PT規(guī)則排列，因此計(jì)算復(fù)雜度為O(nlogn)[7].

定理2用SPT規(guī)則解決極小化總完工時間問題，定理3則通過添加一個限制條件，解決了總加權(quán)完工時間的問題.

定理3對于問題1|LD,qpsd|∑wjCj，當(dāng)任意工件Ji和Jj滿足pipj并且wi≥wj時，則工件按照(即WSPT規(guī)則)能得到最優(yōu)排序.

wjCj(S')+wiCi(S')-wiCi(S)-wjCj(S)

≥wjCi(S)+wiCj(S)-wiCi(S)-wjCj(S)

=(wi-wj)(Cj(S)-Ci(S)),

因?yàn)閣i≥wj，(wi-wj)(Cj(S)-Ci(S))≥0，定理得證.

通過增加一個限制條件，用WSPT規(guī)則解決了問題1|LD,qpsd|∑wjCj. 接下來就是關(guān)于極小化最大延誤的問題.

定理4對于問題1|LD,qpsd|Lmax，當(dāng)任意工件Ji和Jj滿足當(dāng)pipj，didj時，則工件按照dj非減的順序(即EDD原則)可得到最優(yōu)排序.

證基于定理2的證明，進(jìn)一步假設(shè)排序S滿足didj,并且

Cj(S)Ci(S') ，Ci(S)Cj(S')和Cl(S)=Cl(S')

其中l(wèi)≠i和j, 只需證max{Li(S),Lj(S)}max{Li(S'),Lj(S')}. 由Lj的定義可得：

Li(S)=Ci(S)-di

Lj(S)=Cj(S)-dj

Li(S')=Ci(S')-di

Lj(S')=Cj(S')-dj

因?yàn)閐idj，并且Ci(S)Cj(S)Ci(S')，所以Lj(S)Li(S')，Li(S)Li(S'),從而得max{Li(S),Lj(S)}max{Li(S'),Lj(S')}，定理得證.

3　結(jié)語

本文考慮帶有退化效應(yīng)和序列相關(guān)送出時間的單機(jī)排序問題，通過把基本加工時間最大的工件放在最后加工得到了極小化最大完工時間問題的最優(yōu)排序，并給出了其計(jì)算復(fù)雜度O(n)，證明了SPT序?qū)τ跇O小化總完工時間問題是最優(yōu)排序，給出了計(jì)算復(fù)雜度O(nlogn)，就基本加工時間和權(quán)重相反一致情形證得WSPT序?qū)τ跇O小化總加權(quán)完工時間是最優(yōu)排序，就工期和基本加工時間一致情形，證明了EDD序?qū)τ跇O小化最大延誤問題是最優(yōu)排序.今后主要是考慮通過找到最優(yōu)交貨期窗口的位置，交貨期窗口的大小和一個最優(yōu)排序，使成本函數(shù)

的取值最小.

參考文獻(xiàn)：

[1]G Mosheiov.Scheduling jobs under simple linear deterioration[J]. Computers & Operations Research, 1994,21: 653-659.

[2] A Bachman, A Janiak, M Y Kovalyov. Minimizing the total weighted completion time of deteriorating jobs[J]. Information Processing Letters, 2002,81: 81-84.

[3] Wang J B,Wang M Z,Ji P. Single machine total completion time minimizationsched- uling with a time-dependent learning effect and deteriorating jobs[J]. International Journal of Systems Science, 2012, 43:861-868.

[4]Koulamas C,Kyparisis G J. Single-machine scheduling with past-sequence-dependent delivery times[J]. International Journal of Prodution Economics, 2010, 126:264-266.

[5] Yin Y Q, Cheng T C E, Xu J Y, et al. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration[J]. Journal of Industral and Management Optimizati- on, 2013, 9(2):323-339.

[6] Graham R L, Lawler E L, Lenstra J K,et al. Optimization andappr-oximation in deterministic sequencing and scheduling: A survey[J]. Annals of Discrete Math- ematics, 1979, 5:287-326.

[7]Pinedo M L. Scheduling : Theory, Algorithms and Systems[M]. NJ: Prentice-Hall, Englewood Cliffs, 1995:28-31.