許 尉，趙玉芳，岳雅娟

（沈陽師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，沈陽 110034）

0 引 言

在很多實(shí)際生產(chǎn)中，工件一般在處理機(jī)上加工后，若干個(gè)放在一起，形成一批，用車等工具運(yùn)走，轉(zhuǎn)交到客戶手中，才算加工完。把這個(gè)時(shí)間稱為這批工件的交貨期，這樣的問題成為批運(yùn)輸問題。在這個(gè)問題中，既要考慮工件的加工順序，還要決定如何分批，使目標(biāo)函數(shù)達(dá)到最優(yōu)，所以這個(gè)問題變得更為復(fù)雜。批運(yùn)輸問題是Cheng等［1］首次提出的，對于單機(jī)、目標(biāo)函數(shù)為總權(quán)提前懲罰與運(yùn)輸費(fèi)用之和問題，他們證明了這個(gè)問題是一般意義NP－難的。Cheng等［2］進(jìn)一步給出了此問題的一個(gè)動(dòng)態(tài)規(guī)劃算法，當(dāng)批數(shù)有一個(gè)固定的上界時(shí)，這個(gè)算法是擬多項(xiàng)式的。對于極小化批運(yùn)輸費(fèi)用與工件的提早懲罰之和的單機(jī)分批排序問題，Cheng等［3］給出了這個(gè)問題與平行機(jī)排序問題的關(guān)系，從而把此問題歸類于平行機(jī)問題。對于目標(biāo)函數(shù)是總加權(quán)提早與平均批運(yùn)輸時(shí)間之和問題，Cheng等［4］證明是強(qiáng)NP－難的。Hermann等［5］考慮的是所有工件有一個(gè)公共工期的單機(jī)批運(yùn)輸問題，對于總提早及延誤懲罰與誤工工件的運(yùn)輸費(fèi)用之和問題，給出了擬多項(xiàng)式動(dòng)態(tài)規(guī)劃算法。當(dāng)公共工期是一個(gè)決策變量時(shí)，Chen［6］給出了這個(gè)問題是多項(xiàng)式可解的。對于極小化總加權(quán)提早及延誤與誤工工件運(yùn)輸費(fèi)用之和的單機(jī)批運(yùn)輸問題，Yun［7］證明是強(qiáng)NP－難的。Ji等［8］討論了在單機(jī)生產(chǎn)環(huán)境下的批運(yùn)輸排序問題，總加權(quán)流水時(shí)間與運(yùn)輸費(fèi)用之和的問題是強(qiáng)NP－難的；當(dāng)批數(shù)有一個(gè)上界時(shí)，該問題變?yōu)橐话阋饬xNP－難的。Wang等［9］研究了平行機(jī)生產(chǎn)環(huán)境下的批運(yùn)輸排序問題，對于總流水時(shí)間與運(yùn)輸費(fèi)用之和問題，證明了一般情況下是強(qiáng)NP－難的，并給出了一個(gè)動(dòng)態(tài)規(guī)劃算法。

機(jī)器由于維修或故障等原因會(huì)導(dǎo)致在某段時(shí)間內(nèi)不可用，從而影響工件的加工過程，這種現(xiàn)象在排序問題中被稱之為機(jī)器可用性限制問題。Lee［10］研究了機(jī)器具有可用性限制的排序問題，討論了極小化加權(quán)總完工時(shí)間的單機(jī)及平行機(jī)排序問題，指出這2個(gè)問題都是NP－難的，給出啟發(fā)式算法，并分析了誤差界。對于不可用區(qū)間是已知的情況，Lee［11］考慮了2臺(tái)機(jī)器的流水作業(yè)排序問題，證明了時(shí)間表長問題是NP－難的，且給出了擬多項(xiàng)式動(dòng)態(tài)規(guī)劃算法。Lee［12］進(jìn)一步分別對可恢復(fù)和不可恢復(fù)的情況進(jìn)行了討論，分析了問題的復(fù)雜性，給出了擬多項(xiàng)式動(dòng)態(tài)規(guī)劃算法，并且對給出的啟發(fā)式算法進(jìn)行了誤差界分析。Chen［13］研究了帶有有限個(gè)不可用區(qū)間且工件是不可恢復(fù)的單機(jī)排序問題，對于極小化總流水時(shí)間問題，給出了分枝定界算法。Kacem等［14］研究帶有一個(gè)固定的不可用區(qū)間限制且工件是不可恢復(fù)的排序問題，目標(biāo)函數(shù)為總加權(quán)完工時(shí)間。對于該問題他們給出了一個(gè)全多項(xiàng)式時(shí)間近似算法（FPTAS）。對于同時(shí)帶有學(xué)習(xí)、惡化效應(yīng)及可用性限制問題，趙玉芳等［15］給出了加權(quán)總完工時(shí)間擬多項(xiàng)式動(dòng)態(tài)規(guī)劃算法。Zhao等［16］研究帶有速度維修的兩臺(tái)平行機(jī)的排序問題，當(dāng)目標(biāo)函數(shù)為總完工時(shí)間時(shí)給出多項(xiàng)式時(shí)間算法。Wang等［17］研究了機(jī)器帶有速度維修單機(jī)工期分配排序問題，對于極小化總提早、總延誤和共同的流余量費(fèi)用問題給出多項(xiàng)式時(shí)間算法。Wang等［18］研究每臺(tái)機(jī)器都帶有惡化維修的排序問題，討論了極小化完工時(shí)間的絕對差值總和和等待時(shí)間的絕對值差值總和問題，并證明出它們是多項(xiàng)式時(shí)間可解的。Wang等［19］研究帶有一個(gè)惡化維修的平行機(jī)排序問題，他們給出目標(biāo)函數(shù)為總完工時(shí)間的多項(xiàng)式時(shí)間算法。

本文將批運(yùn)輸問題與機(jī)器的可用性限制結(jié)合在一起，并且運(yùn)輸費(fèi)用與批數(shù)有關(guān)，這個(gè)問題到目前為止還沒有人研究過。該問題不僅對實(shí)際生產(chǎn)具有指導(dǎo)意義，而且能夠豐富生產(chǎn)物流調(diào)度優(yōu)化理論，具有一定的理論價(jià)值。

1 問題描述

其中h表示帶有不可用區(qū)間限制的問題；bd表示批運(yùn)輸問題；U為批數(shù)R的上界。

2 問題1，h｜bd，R≤U｜（ ∑Fi＋α（R））

對于工件是不可恢復(fù)的極小化總完工時(shí)間的單機(jī)排序問題，Adiri等［21］指出其問題是NP－難的。那么對于目標(biāo)函數(shù)是總流水時(shí)間的問題，至少為NP－難的。故可得到下面結(jié)論。

對于單機(jī)帶有不可用區(qū)間目標(biāo)函數(shù)為

引 理 1 問 題 1，h｜bd，R≤U｜（∑Fi＋α（R）） 存在一個(gè)最優(yōu)解π＊＝〈B1，…，BR〉滿足

1）在T1前和T2后的工件分別按SPT規(guī)則排列；

圖1 問題1，h｜bd，R≤U｜ （∑Fi＋α（R））的例圖

2）Bl包含所有在（Dl－1，Dl］之間完工的工件。

其他批的完工時(shí)間不變，則有＝；由pi＞pj可知，＜，其余批不變。即第l批前的工件流水時(shí)間不變，第l批的工件的流水時(shí)間減少，第l批后的工件流水時(shí)間也不變。從而G（π＊）＞G（π′），所以與假設(shè)π＊為最優(yōu)序列矛盾。于是，存在一個(gè)最優(yōu)序列π＊，使得T1前的工件按SPT規(guī)則排列。同理可證在T2后的工件也滿足SPT規(guī)則排列。從而存在一個(gè)最優(yōu)解π＊滿足在T1前和T2后的工件分別按SPT規(guī)則排列。

下面用反證法證明2）。不失一般性，設(shè)最優(yōu)序列π＊中工件的加工順序?yàn)镴［1］，J［2］，…，J［n］，其中J［j］表示π＊中第j個(gè)加工的工件。Bl批的交貨期為，則＜…＜＜…＜。假設(shè)存在一個(gè)工件J［j］滿足＜≤且不在Bl批中加工，由于工件J［j］在Bl批之前沒有完工，則有＞。若把工件J［j］放在Bl批中，設(shè)為新序列π′，其他工件的加工順序與所在批不變，則有＝，，從而G（π＊）＞G（π′），與π＊為最優(yōu)排序矛盾。在其他批中的工件按照同樣的討論，可以證明存在一個(gè)最優(yōu)排列，使得所有批都是由一些連續(xù)完工的工件組成的。在任意的最優(yōu)排列中，因?yàn)樗性贒l處完工的工件，都可以被分到Bl中，l＝1，…，R。Bl應(yīng)包含在（Dl－1，Dl］完工的所有工件。

由于同批中的所有工件的流水時(shí)間相同，可以得到下面的結(jié)論。

引理2 對于問題1，h｜bd，R≤U｜ （∑Fi＋α（R）） 任何一個(gè)最優(yōu)序列，每一批內(nèi)的工件加工順序是任意的。所以＞。又因?yàn)?/p>

1）當(dāng)工件Jj排在［0，T1］區(qū)間內(nèi)，有

其中Fj＝｛Dl｜Dl－1＜t1≤Dl，D0＝0，l＝1，…，R｝；

2）當(dāng)工件Jj排在T2后，有

其中Fj＝｛Dl｜Dl－1＜t2＋T2≤Dl，D0＝0，l＝1，…，R｝。

由以上分析可得動(dòng)態(tài)規(guī)劃算法如下：

在下述動(dòng)態(tài)規(guī)劃算法中，設(shè)

算法DP1：

1）把工件按SPT序編號(hào)，使p1≤p2…≤pn；

3）按遞歸方程：

其中j＝0，…，n，t1＝0，…，T1，t2＝0，…，P，Dl＝Dl－1＋1，…，T2＋P，l＝1，…，R，D0＝0；

4）G＊＝min｛HR（n，t1，t2，D1，…，DR）＋α（R）｝，利用反向追蹤得到最優(yōu)排序及分批，R＝1，…，U。

引理3 動(dòng)態(tài)規(guī)劃算法DP1的時(shí)間復(fù)雜性為O（nU2T1（T2＋P）U）。

證明 在狀態(tài)（j，t1，t2，D1，…，DR）下HR（j，t1，t2，D1，…，DR）中j的取值為1，2，…，n；t1的取值為0到T1，則t2在t1取定之后便可確定；D1到DR可取到的最大值都為T2＋P，R＝1，…，U；從而遞推關(guān)系式的不同狀態(tài)R＝1，…，U至多有nT1（T2＋P）U。對于每個(gè)狀態(tài)，遞推關(guān)系式的右邊可以在O（U）時(shí)間內(nèi)被計(jì)算。因此，整個(gè)的計(jì)算復(fù)雜性為O（nU2T1（T2＋P）U）。

3 問題P2，h｜bd，R≤U｜ （∑Fi＋α（R））

王國慶等［9］已經(jīng)證明出問題P2｜bd，R≤U｜ （∑Fi＋α（R）） 為NP－難的，在此基礎(chǔ)上加入一個(gè)不可用區(qū)間，可得下面結(jié)論。

定理2 問題P2，h｜bd，R≤U｜ （∑Fi＋α（R）） 至少是NP－難的。

引理4 問題P2，h｜bd，R≤U｜ （∑Fi＋α（R）） 存在一個(gè)最優(yōu)解π＊＝〈B1，…，BR〉滿足

1）在M1上的T1前和T2后與M2上加工的工件分別按SPT規(guī)則排列；

2）Bl批中包含所有在（Dl－1，Dl］之間完工的工件，l＝1，…，R。

其他批的完工時(shí)間不變，則有＝；由pi＞pj可知，＜其余批不變，第l批前的工件流水時(shí)間不變，第l批的工件的流水時(shí)間減少，第l批后的工件流水時(shí)間也不變。從而G（π＊）＞G（π′），所以與假設(shè)π＊為最優(yōu)序列矛盾。綜上所述，可以證明出存在一個(gè)最優(yōu)解使得在M1上的T1前和T2后與M2上加工的工件分別按SPT規(guī)則排列。

2）同引理1中2）的證明。

而對于2臺(tái)平行機(jī)的情況下，機(jī)器由于維修或故障，會(huì)導(dǎo)致機(jī)器在一段時(shí)間內(nèi)不可用，在這種機(jī)器受限的情況下，假設(shè)只有1臺(tái)機(jī)器受限。那么把問題劃分為2類，一類是機(jī)器中途維修；另一類是機(jī)器中途損壞，即懂某一刻開始一直不可用。具體描述如下：

3.1 機(jī)器中途維修

圖2 問題3.1的實(shí)例

對于第一類情況（如圖2所示）。

由引理4可知，對于問題P2，h｜bd，R≤U｜（∑Fi＋α（R）） 的第一類情況，存在最優(yōu)排序，在M1上的T1前和T2后與M2上的工件的加工順序都按SPT排列。那么將工件分成3部分，分別在M1上的T1前和T2后與M2上，使每一部分工件都按SPT排列，從而得到最優(yōu)排序。據(jù)此，可以建立求解這個(gè)問題的動(dòng)態(tài)規(guī)劃算法。

在下述動(dòng)態(tài)規(guī)劃算法中，假設(shè)工件J1…Jj已排完，定義HR（j，t1，t2，t3，D1，…，DR）為已排列工件J1到Jj的最小總流水時(shí)間，使得在M1上T1前的總加工時(shí)間為t1（t1＜T1），在M1上T2后總加工時(shí)間為t2，則當(dāng)前在T2后最后一個(gè)工件的完工時(shí)間為t2＋T2，在M2上工件的總加工時(shí)間為t3，Bl的交貨期為Dl，l＝1，…，R。于是，工件J1…Jj的總流水時(shí)間分以下3種情況：

1）當(dāng)工件Jj排在M1上的［0，T1］區(qū)間內(nèi)，有

其中Fj＝｛Dl｜Dl－1＜t1≤Dl，D0＝0，l＝1，…，R｝；

2）當(dāng)工件Jj排在M1上的T2后，有

其中Fj＝｛Dl｜Dl－1＜t2＋T2≤Dl，D0＝0，l＝1，…，R｝；

3）當(dāng)工件Jj排在M2上，有

其中Fj＝｛Dl｜Dl－1＜t3≤Dl，D0＝0，l＝1，…，R｝。

由以上分析可得動(dòng)態(tài)規(guī)劃算法如下：

算法DP2：

1）把工件按SPT序編號(hào)，使p1≤p2…≤pn；

3）按遞歸方程：

其中j＝0，…，n，t1＝0，…，T1，t2＝0，…，P，t3＝0，…，P，Dl＝Dl－1＋1，…，T2＋P，l＝1，…，R，D0＝0；

4）G＊＝min｛HR（n，t1，t2，t3，D1，…，DR）＋α（R）｝，利用反向追蹤得到最優(yōu)排序及分批R＝1，…，U。

引理5 動(dòng)態(tài)規(guī)劃算法DP2的時(shí)間復(fù)雜性為O（nT1PU2（T2＋P）U）。

證明 在狀態(tài)（j，t1，t2，t3，D1，…，DR）下HR（j，t1，t2，t3，D1，…，DR）中j的取值為1，2，…，n；t1的取值為0到T1，而t2的取值為0到P，從而t3便可被確定下來；D1到DR可取到的最大值都為T2＋P，R＝1，…，U；從而遞推關(guān)系式的不同狀態(tài)至多有nT1P（T2＋P）U。對于每個(gè)狀態(tài)下Fj可以在O（U）時(shí)間內(nèi)被計(jì)算。因此，整個(gè)的計(jì)算復(fù)雜性為O（nU2T1（T2＋P）U）。

3.2 機(jī)器中途損壞

圖3 問題3.2的實(shí)例

對于第二類情況（如圖3所示）。

由引理4可知，對于問題P2，h｜bd，R≤U｜（∑Fi＋α（R）） 的第二類情況，存在最優(yōu)排序，在M1上的T1前與M2上的工件的加工順序都按SPT排列。那么可以將工件分成2部分，分別在M1上的T1前和M2上，使每一部分工件都按SPT排列，從而得到最優(yōu)排序。據(jù)此，可以建立求解這個(gè)問題的動(dòng)態(tài)規(guī)劃算法。

在下述動(dòng)態(tài)規(guī)劃算法中，假設(shè)工件J1…Jj已排完，定義HR（j，t1，t2，D1，…，DR）為已排列工件J1到Jj的最小總流水時(shí)間，使得在M1上T1前的總加工時(shí)間為t1（t1＜T1），在M2上工件的總加工時(shí)間為t2，Bl的交貨期為Dl，l＝1，…，R。于是，工件J1，…，Jj的總流水時(shí)間分以下兩種情況：

1）當(dāng)工件Jj排在M1上的［0，T1］區(qū)間內(nèi)，有

其中Fj＝｛Dl｜Dl－1＜t1≤Dl，D0＝0，l＝1，…，R｝；

2）當(dāng)工件Jj排在M2上，有

其中Fj＝｛Dl｜Dl－1＜t3≤Dl，D0＝0，l＝1，…，R｝。

由以上分析可得動(dòng)態(tài)規(guī)劃算法DP3如下：

1）把工件按SPT序編號(hào)，使p1≤p2…≤pn；

3）按遞歸方程：

其中j＝0，…，n，t1＝0，…，T1，t2＝0，…，P，Dl＝Dl－1＋1，…，T2＋P，l＝1，…，R，D0＝0；

4）G＊＝min｛HR（n，t1，t2，D1，…，DR）＋α（R）｝，利用反向追蹤得到最優(yōu)排序及分批，R＝1，…，U。

引理6 動(dòng)態(tài)規(guī)劃算法DP3的時(shí)間復(fù)雜性為O（nT1U2PU）。

證明 在狀態(tài)（j，t1，t2，D1，…，DR）下HR（j，t1，t2，D1，…，DR）中j的取值為1，2，…，n；t1的取值為0到T1，則t2在t1取定之后便可確定；D1到DR可取到的最大值都為P，R＝1，…，U；從而遞推關(guān)系式的不同狀態(tài)R＝1，…，U至多有nT1PU。對于每個(gè)狀態(tài)，遞推關(guān)系式的右邊可以在O（U）時(shí)間內(nèi)被計(jì)算。因此，整個(gè)的計(jì)算復(fù)雜性為O（nT1U2PU）。

4 結(jié) 論

本文研究了單機(jī)和2臺(tái)平行機(jī)帶有不可用區(qū)間的批運(yùn)輸問題，其中機(jī)器有可用性的限制。通過分析，證明了此類問題至少是NP－難的。為此給出了此類問題的擬多項(xiàng)式動(dòng)態(tài)規(guī)劃算法，并給出了時(shí)間復(fù)雜性及相應(yīng)的數(shù)值例子。為了進(jìn)一步的研究，需要值得考慮的是單機(jī)及平行機(jī)情況下是否是強(qiáng)NP－難的。對于這兩種情況是否能找到一個(gè)FPTAS方案。

［1］CHENG T C E，KAHLBACHER H G.Scheduling with delivery and earliness penalties［J］.Asia－Pacific J Oper Res，1993，10（2）：145－152.

［2］CHENG T C E，GORDON V S.Batch delivery scheduling on a single machine［J］.J Oper Res Soc，1994，45（10）：1211－1215.

［3］CHENG T C E，GORDON V S，KOVALYOV M Y.Single machine scheduling with batch deliveries［J］.Eur J Oper Res，1996，94（2）：277－283.

［4］CHENG T C E，KOVALYOV M Y，Lin B M T.Single machine scheduling with batch delivery and job earliness penalties［J］.SIAM J Optim，1997，7（2）：547－559.

［5］HERMANM J W，LEE C Y.On scheduling to minimize earliness－tardiness and batch delivery costs with a common due date［J］.Eur J Oper Res，1993，70（3）：272－288.

［6］CHEN Zhilong.Scheduling and common due date assignment with earliness－tardiness penalties and batch delivery costs［J］.Eur J Oper Res，1996，93（1）：49－60.

［7］YUAN Jinjiang.A note on the complexity of single－machine scheduling with a common due date，earliness－tardiness，and batch delivery costs［J］.Eur J Oper Res，1996，94（1）：203－205.

［8］JI Min，HE Yong，CHENG T C E.Batch delivery scheduling with batch delivery cost on a single machine［J］.Eur J Oper Res，2007，176（2）：745－755.

［9］WANG Guoqing，CHENG T C E.Parallel machine scheduling with batch delivery costs［J］.Int J Prod Econ，2000，68（2）：177－183.

［10］LEE C Y.Machine scheduling with an availability constraint［J］.J Global Optim，1996，9（3／4）：395－416.

［11］LEE C Y.Minimizing the makespan in the two－machine flowshop scheduling problem with an availability constraint［J］.Oper Res Lett，1997，20（3）：129－139.

［12］LEE C Y.Two－machine flowshop scheduling with availability constraints［J］.Eur J Oper Res，1999，114（2）：420－429.

［13］CHEN W J.Minimizing total flow time in the single－machine scheduling problem with periodic maintenance［J］.J Oper Res Soc，2006，57：410－415.

［14］KACEM I，HAOUARI M.Fully polynomial time approximation scheme for the weighted flow－time minimization on a single machine with a fixed non－availability interval［J］.Comput Indust Eng，2009，56（4）：1708－1712.

［15］崔苗苗，趙玉芳，王松麗.機(jī)器具有可用性限制的加權(quán)總完工時(shí)間問題［J］.沈陽師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，30（2）：157－163.

［16］ZHAO Chuanli，TANG Hengyong，CHENG Congdian.Two－parallel machines scheduling with rate－modifying activities to minimize total completion time［J］.Eur J Oper Res，2009，198（1）：354－357.

［17］WANG Xiaoyuan，WANG Mingzheng.Single machine common flow allowance scheduling with rate－modifying activities［J］.Comput Indust Eng，2010，59（4）：898－902.

［18］WANG Jibo，WEI Caimin.Parallel machines scheduling with a deteriorating maintenance activity and total absolute differences penalties［J］.Appl Math Comput，2011，217（20）：8093－8099.

［19］WANG J J，WANG J B，LIU F.Parallel machines scheduling with a deteriorating maintenance activity［J］.J Oper Res Soc，2011，62：1898－1902.

［20］GRAHAM R L，LAWLER E L，LENSTRA J K，et al.Optimization and approximation in deterministic sequencing and scheduling：A survey［M］.Amesterdam：North－Hollard，1979，5：287－326.

［21］ADIRI I，BRUNO J，F(xiàn)ROSTIG E，et al.Single machine flow－time scheduling with a single breakdown［J］.Acta Inform，1989，26（7）：679－696.