帶時間延遲的極小化總完工時間的單機排序問題

胡覺亮，王煥男，蔣義偉

（浙江理工大學(xué)理學(xué)院，杭州310018）

帶時間延遲的極小化總完工時間的單機排序問題

胡覺亮，王煥男，蔣義偉

（浙江理工大學(xué)理學(xué)院，杭州310018）

研究工件帶有兩道工序的單臺機排序問題。在該問題中，工件的第一道工序先于第二道工序加工，并且第二道工序的開工時間與第一道工序的完工時間至少間隔一定的延遲時間，目標(biāo)是極小化所有工件的總完工時間。文章考慮所有工件相同且兩道工序的加工時間均為單位時間的情形。通過引入k-連續(xù)加工的概念和分析最優(yōu)解的性質(zhì)，根據(jù)延遲時間的大小，分別設(shè)計了兩個算法并證明了算法所得的排序為最優(yōu)排序。

單臺機；時間延遲；總完工時間；算法設(shè)計與分析；最優(yōu)排序

0 引 言

本文主要研究帶延遲時間的單機排序問題。每個工件Jj有兩道工序aj和bj，第一道工序先于第二道工序加工，第一道工序的完工時間與第二道工序的開工時間之間至少存在lj個單位時間延遲，也就是說第二道工序至少等待lj個單位時間才能開工。此類問題在一些產(chǎn)品制造工藝流程、布匹印染和服裝訂單的生產(chǎn)中有重要的應(yīng)用背景。對于帶有延遲的排序問題，主要分為兩類，一類是工件Jj前后兩道工序的延遲時間恰好為lj，本文稱之為精確延遲排序；另一類是兩道工序間的延遲時間至少為lj，稱之為至少延遲排序。

關(guān)于精確延遲的排序問題，Orman等［1］證明了單臺機的一些特殊情況是多項式可解的，并證明即便所有工序的加工時間相同，該問題還是強NP-難的。Leung等［2］利用貪婪算法研究延遲非增的情形，給出了問題F2｜，aj=a，bj=b，a≥b｜∑Cj的最優(yōu)排序，并對問題F2｜，aj=a，bj=b，a＜b｜∑Cj給出了一個2-近似算法。Ageev等［3］分別研究了單臺機和兩臺流水作業(yè)機器問題的一些近似算法。Ageev等［4］給出了問題1｜exact lj，aj=bj=1｜Cmax的一個7/4-近似算法，并證明界不可改進，同時給出了問題F2｜exact lj，aj=bj=1｜Cmax的一個3/2-近似算法，Yu等［5］證明了上述兩個問題是強NP-難的。Huo等［6］和Glascock等［7］研究了問題F2｜exact lj｜∑Cj的計算復(fù)雜性并給出相應(yīng)的啟發(fā)式算法。

關(guān)于至少延遲的排序問題，Kern等［8］證明了以極小化最大完工時間為目標(biāo)的單臺機排序在解不限于排列排序的情況下是NP-難的。而對于兩臺流水作業(yè)排序問題F2｜lj｜C（max），Dell’Amico［9］給出了該問題的一個2-近似算法，并提出了一個禁忌搜索算法。若兩道工序的加工時間相同時，Dell’Amico等［10］證明了問題F2｜lj，aj=bj｜Cmax是強NP-難的，Johnson［11］和Mitten［12］證明該問題存在最優(yōu)排列排序（permutation schedule）。若兩道工序加工時間相同且延遲時間lj∈｛0，l｝時，Yu［13］證明了問題F2｜lj∈｛0，l｝，aj=bj｜Cmax是強NP-難的。進一步，即使兩道工序的加工時間均為單位時間，Yu［5］證明了問題F2｜lj，aj=bj=1｜Cmax也是強NP-難的。

對上述研究綜述進行匯總后，如表1所示。

表1 帶有至少（精確）延遲時間的單機和兩臺機流水作業(yè)排序

本文研究的問題屬于至少延遲排序。由上述結(jié)果可以看出，此類問題主要研究單臺機和兩臺機的流水作業(yè)問題，且均以極小化最大完工時間為目標(biāo)。然而，在很多實際問題中，最大完工時間只能體現(xiàn)局部最優(yōu)性，為了考慮全局的優(yōu)劣，通常需要考慮總完工時間這一目標(biāo)函數(shù)。例如，在服裝訂單的問題上，總的完工時間越小說明每個訂單的平均等待時間越小，從而體現(xiàn)了全局的最優(yōu)性。

因此，本文考慮目標(biāo)為極小化總完工時間的至少延誤問題，即1｜l，aj=bj=1｜∑Cj，其中l(wèi)j= l表示所有工件的延遲時間相同并且假定所有工序的加工時間均為單位時間，即aj=bj=1。Cj表示工件Jj的完工時間。

若延遲時間大于工序的加工時間，即l＞1。不妨假設(shè)l=q，這里q為不超過l的最大整數(shù)，顯然第一道工序的后面可直接安排q個其他工件的工序而不影響該工件的完工，故只需考慮在此之后的延遲時間段l-q是否需要考慮安排其他工件的工序即可。注意到l-q＜1，因此本文主要考慮延遲時間小于工序加工時間的情形，即0≤l＜1。根據(jù)l的大小分別對）和）給出了最優(yōu)排序。

1 預(yù)備結(jié)果

本節(jié)主要給出相關(guān)的定義以及一些初步的結(jié)論。

定義1.1 將k個工件的第一道工序連續(xù)加工，緊接著按照第一道工序的加工順序連續(xù)加工這k個工件的第二道工序，我們稱之為k-連續(xù)加工（如圖1所示）。

圖1 k-連續(xù)加工

定義1.2 若同一個工件的兩道工序之間不存在其他工件的工序，稱這種工件的加工方式為單獨加工。

引理1.1 最優(yōu)排序中，只存在單獨加工和2-連續(xù)加工這兩種加工方式，即不存在k（k≥3）-連續(xù)加工。

證明：由圖1可知，l-連續(xù)加工的各個工件的完工時間是一個等差數(shù)列，不難得到第一個工件的完工時間C1=k+1，第k個工件的完工時間，故所有的完工時間為

若存在k（k≥3）-連續(xù)加工，可以將這些工件按照2-連續(xù)加工或者單獨加工得到更好的排序，從而得出結(jié)論。下面分別根據(jù)k的奇偶性對這k個工件進行重新排序。

若k為偶數(shù)，即必有k≥4，則將這些工件進行2-連續(xù)加工，即有個2-連續(xù)。不難得出這k個工件的完工時間如下：第一個工件與第二個工件的總完工時間為3+4=7；第三個工件與第四個工件的總完工時間為7+8=15；第k-1個工件與第k個工件的總完工時間為4k-1。由等差數(shù)列的求和可知，這k個工件通過2-連續(xù)加工的總完工時間為

由k≥4可得當(dāng)k為奇數(shù)時，則將k-1個工件分批進行2-連續(xù)加工，由（2）式知，這k-1個工件2-連續(xù)加工的總完工時間為。而第k個工件單獨加工，完工時間為2（k-1）+2+l。所以，這k個工件的總完工時間為

由k≥3和0≤l＜1可得

因此，最優(yōu)排序中只存在2-連續(xù)加工和單獨加工這兩種方式。

引理1.2 如果最優(yōu)排序中存在單獨加工的工件，則該工件必在連續(xù)加工的工件之后進行加工。

證明：假設(shè)在A時刻有一個工件單獨加工，后面存在連續(xù)加工的工件，不妨設(shè)有m（m為偶數(shù)）個工件，由引理1.1可知，這些工件都是2-連續(xù)加工。由（2）式可知，這m+1個工件的總完工時間為而將這個工件放在m個工件之后加工的總完工時間為

比較這兩個總完工時間可知，（4）-（5）=ml＞0。

因此，在最優(yōu)排序中，若有2-連續(xù)加工的工件，必在零時刻開始加工所有的2-連續(xù)工件，然后再加工那些單獨加工的工件。

2 最優(yōu)算法

本節(jié)將給出問題1｜l，aj=bj=1｜∑Cj的最優(yōu)算法，對和進行考慮。下面先給出情形的最優(yōu)排序。

(1)膨潤土開發(fā)利用水平MEL值同“三率”及權(quán)重值有較重要的契合關(guān)系，計算時選礦回收率從蒙脫石角度評價，綜合利用率從其它共(伴生)礦物角度評價，MEL值中綜合利用率權(quán)重項高于采礦回采率和選礦回收率權(quán)重項。

Ji和Jj兩個工件的完工時間減少了（3+4）-（2+l+4+2l）=1-3l，而后s個工件的總完工時間的增加了2ls。由于-2，不難得到1-3l≥2ls，即Ji和Jj完工時間的減少量不小于后面s個工件的總完工時間的增加量。

下面考慮第二種情況，若存在正整數(shù)i使得

即

由引理1.2可知，最優(yōu)排序?qū)?-連續(xù)工件先加工，再加工單獨工件。設(shè)前2j個工件兩個一組進行2-連續(xù)加工，其余單獨加工。此時總完工時間為

類似可以計算得到算法的目標(biāo)函數(shù)值為兩種情形分別

因此，當(dāng)j=i時，目標(biāo)函數(shù)值最小，即算法所得是最優(yōu)排序。

算法H 2 （1）若工件個數(shù)為偶數(shù)則將所有工件進行2-連續(xù)加工；

（2）若工件個數(shù)為奇數(shù)，則將前n-1個工件進行2-連續(xù)加工，最后一個工件單獨加工。

證明：由引理1.1和1.2知，最優(yōu)排序中只存在2-連續(xù)加工和單獨加工，且單獨加工的工件都在連續(xù)加工之后加工。結(jié)合筆者的算法，只需證明最優(yōu)排序不可能存在兩個或者兩個以上單獨加工的工件。

不妨假設(shè)在A時刻有兩個相鄰的工件單獨加工，現(xiàn)將這兩個工件放在一起加工，比較這兩個工件在前后兩種排序中的總完工時間。若單獨加工，不難得到這兩個工件的總完工時間為

A+2+l+A+4+2l=2A+3l+6。

而將這兩個工件放在一起進行2-連續(xù)加工，總完工時間為

A+3+A+4=2A+7。

比較這兩個總完工時間知（2A+3l+6）-（2A +7）=3l-1≥0。

因此，算法H 2得到的排序為最優(yōu)排序。

3 結(jié)束語

本文研究了帶有至少l（0≤l＜1）個單位時間延遲的單位工件單機排序問題，目標(biāo)是極小化總完工時間。分別針對兩種情形給出了相應(yīng)的最優(yōu)算法。對于該類問題的進一步研究，可以考慮工件的加工時間更為一般的情況，包括兩道工序加工時間不同的情形，以及工件的延遲時間不同的情形下的近似算法設(shè)計及分析。

［1］Orman A J，Potts C N.On the complexity of coupledtask scheduling［J］.Discrete Applied Mathematics，1997，72（1）：141-154.

［2］Leung J，Li H，Zhao H.Scheduling two-machine flow shops with exact delay［J］.International Journal of Foundations of Computer Science，2007，18（2）：341-360.

［3］Ageev A A，Kononov A V.Approximation algorithms for scheduling problems with exact delays［C］//Erlebach T，Kaklamanis C.4th International Workshop，WAOA 2006，Lecture Notes in Computer Science.Berlin：Springer，2007，4368：1-14.

［4］Ageev A A，Kononov A V.Approximation algorithms for the single and two-machine scheduling problems with exact delays［J］.Operations Research Letters.2007，35（4）：533-540.

［5］Yu W，Hoogeveen H，Lenstra J K.Minimizing makespan in a two-machine flow shop with delays and unittime operations is NP-hard［J］.Journal of Scheduling，2004，7（5）：333-348.

［6］Huo Y，Li H，Zhao H.Minimizing total completion time in two-machine flow shops with exact delays［J］. Computers and Operations Research.2009，36（6）：2018-2030.

［7］Glascock J，Hunter B.Minimizing total completion time in two-machine flow shops with exact delay using genetic algorithm&ant colony algorithm［C］//Rothlauf F. Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference，New York：ACM，2009：2733-2736.

［8］Kern W，Nawijn W M.Scheduling multi-operation jobs with time lags on a single machine［C］//Faigle U，Hoede C.Proceedings 2nd Twente Workshop on Graphs andCombinatorial Optimization.Enschede：University of Twente，1991.

［9］Dell’Amico M.Shop problems with two machines and time lags［J］.Operations Research，1996，44（5）：777-787.

［10］Dell’Amico M，Vaessens R J M.Flow and open shop scheduling on two machines with transportation times and machine-independent processing times is NP-hard［M］.Modena：Universita Degli Studi di Modena，1996：103-121.

［11］Johnson S M.Discussion：sequencing n jobs on two machines with arbitrary time-lags［J］.Management Science，1959，5（3）：299-303.

［12］Mitten L G.Sequencing n jobs on two machines with arbitrary time-lags［J］.Management Science，1959，5（3）：293-298.

［13］Yu W.The two-machine flow shop problem with delays and the one-machine total tardiness problem［D］. Germany：Eindhoven University of Technology，1996.

Single Machine Sequencing Problem of Minimization of Total Completion Time with Time Delay

HU Jue-liang，WANG Huan-nan，JIANGYi-wei
（School of Sciences，Zhejiang Sci-Tech University，Hangzhou 310018，China）

This paper studies the sequencing problem of single machine with its workpieces having two processes.In this problem，the first process of workpieces is implemented earlier than the second one and the commencement time of the second one and the completion time of the first one should at least have a certain time interval，called as delay time.The objective is to minimize the total completion time of all workpieces.This paper considers situations when all workpieces are the same and the processing time of two processes is unit time，respectively designs two algorithms according to the delay time by introducing the concept of k-continuous process and analyzing the property of optimal solution and proves that the sequencing obtained by the algorithm is the optimal sequencing.

single machine；time delay；total completion time；design and analysis of algorithm；optimal sequencing

O233

A

（責(zé)任編輯：許惠兒）

1673-3851（2014）01-0083-05

2012-10-31

國家自然科學(xué)基金（11001242，11071220）

胡覺亮（1958-），男，浙江杭州人，教授，大學(xué)本科，主要從事組合優(yōu)化與數(shù)學(xué)建模的研究