胡覺亮，王煥男，蔣義偉

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

帶時(shí)間延遲的極小化總完工時(shí)間的單機(jī)排序問題

胡覺亮，王煥男，蔣義偉

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

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

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

0 引 言

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

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

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

對(duì)上述研究綜述進(jìn)行匯總后，如表1所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

比較這兩個(gè)總完工時(shí)間可知，（4）-（5）=ml＞0。

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

2 最優(yōu)算法

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

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

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

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

即

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

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

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

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

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

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

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

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

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

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

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

因此，算法H 2得到的排序?yàn)樽顑?yōu)排序。

3 結(jié)束語(yǔ)

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

［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

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

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