带时间延迟的极小化总完工时间的单机排序问题

胡觉亮，王焕男，蒋义伟

（浙江理工大学理学院，杭州310018）

带时间延迟的极小化总完工时间的单机排序问题

胡觉亮，王焕男，蒋义伟

（浙江理工大学理学院，杭州310018）

研究工件带有两道工序的单台机排序问题。在该问题中，工件的第一道工序先于第二道工序加工，并且第二道工序的开工时间与第一道工序的完工时间至少间隔一定的延迟时间，目标是极小化所有工件的总完工时间。文章考虑所有工件相同且两道工序的加工时间均为单位时间的情形。通过引入k-连续加工的概念和分析最优解的性质，根据延迟时间的大小，分别设计了两个算法并证明了算法所得的排序为最优排序。

单台机；时间延迟；总完工时间；算法设计与分析；最优排序

0 引 言

本文主要研究带延迟时间的单机排序问题。每个工件Jj有两道工序aj和bj，第一道工序先于第二道工序加工，第一道工序的完工时间与第二道工序的开工时间之间至少存在lj个单位时间延迟，也就是说第二道工序至少等待lj个单位时间才能开工。此类问题在一些产品制造工艺流程、布匹印染和服装订单的生产中有重要的应用背景。对于带有延迟的排序问题，主要分为两类，一类是工件Jj前后两道工序的延迟时间恰好为lj，本文称之为精确延迟排序；另一类是两道工序间的延迟时间至少为lj，称之为至少延迟排序。

关于精确延迟的排序问题，Orman等［1］证明了单台机的一些特殊情况是多项式可解的，并证明即便所有工序的加工时间相同，该问题还是强NP-难的。Leung等［2］利用贪婪算法研究延迟非增的情形，给出了问题F2｜，aj=a，bj=b，a≥b｜∑Cj的最优排序，并对问题F2｜，aj=a，bj=b，a＜b｜∑Cj给出了一个2-近似算法。Ageev等［3］分别研究了单台机和两台流水作业机器问题的一些近似算法。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的计算复杂性并给出相应的启发式算法。

关于至少延迟的排序问题，Kern等［8］证明了以极小化最大完工时间为目标的单台机排序在解不限于排列排序的情况下是NP-难的。而对于两台流水作业排序问题F2｜lj｜C（max），Dell’Amico［9］给出了该问题的一个2-近似算法，并提出了一个禁忌搜索算法。若两道工序的加工时间相同时，Dell’Amico等［10］证明了问题F2｜lj，aj=bj｜Cmax是强NP-难的，Johnson［11］和Mitten［12］证明该问题存在最优排列排序（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 带有至少（精确）延迟时间的单机和两台机流水作业排序

本文研究的问题属于至少延迟排序。由上述结果可以看出，此类问题主要研究单台机和两台机的流水作业问题，且均以极小化最大完工时间为目标。然而，在很多实际问题中，最大完工时间只能体现局部最优性，为了考虑全局的优劣，通常需要考虑总完工时间这一目标函数。例如，在服装订单的问题上，总的完工时间越小说明每个订单的平均等待时间越小，从而体现了全局的最优性。

因此，本文考虑目标为极小化总完工时间的至少延误问题，即1｜l，aj=bj=1｜∑Cj，其中lj= l表示所有工件的延迟时间相同并且假定所有工序的加工时间均为单位时间，即aj=bj=1。Cj表示工件Jj的完工时间。

若延迟时间大于工序的加工时间，即l＞1。不妨假设l=q，这里q为不超过l的最大整数，显然第一道工序的后面可直接安排q个其他工件的工序而不影响该工件的完工，故只需考虑在此之后的延迟时间段l-q是否需要考虑安排其他工件的工序即可。注意到l-q＜1，因此本文主要考虑延迟时间小于工序加工时间的情形，即0≤l＜1。根据l的大小分别对）和）给出了最优排序。

1 预备结果

本节主要给出相关的定义以及一些初步的结论。

定义1.1 将k个工件的第一道工序连续加工，紧接着按照第一道工序的加工顺序连续加工这k个工件的第二道工序，我们称之为k-连续加工（如图1所示）。

图1 k-连续加工

定义1.2 若同一个工件的两道工序之间不存在其他工件的工序，称这种工件的加工方式为单独加工。

引理1.1 最优排序中，只存在单独加工和2-连续加工这两种加工方式，即不存在k（k≥3）-连续加工。

证明：由图1可知，l-连续加工的各个工件的完工时间是一个等差数列，不难得到第一个工件的完工时间C1=k+1，第k个工件的完工时间，故所有的完工时间为

若存在k（k≥3）-连续加工，可以将这些工件按照2-连续加工或者单独加工得到更好的排序，从而得出结论。下面分别根据k的奇偶性对这k个工件进行重新排序。

若k为偶数，即必有k≥4，则将这些工件进行2-连续加工，即有个2-连续。不难得出这k个工件的完工时间如下：第一个工件与第二个工件的总完工时间为3+4=7；第三个工件与第四个工件的总完工时间为7+8=15；第k-1个工件与第k个工件的总完工时间为4k-1。由等差数列的求和可知，这k个工件通过2-连续加工的总完工时间为

由k≥4可得当k为奇数时，则将k-1个工件分批进行2-连续加工，由（2）式知，这k-1个工件2-连续加工的总完工时间为。而第k个工件单独加工，完工时间为2（k-1）+2+l。所以，这k个工件的总完工时间为

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

因此，最优排序中只存在2-连续加工和单独加工这两种方式。

引理1.2 如果最优排序中存在单独加工的工件，则该工件必在连续加工的工件之后进行加工。

证明：假设在A时刻有一个工件单独加工，后面存在连续加工的工件，不妨设有m（m为偶数）个工件，由引理1.1可知，这些工件都是2-连续加工。由（2）式可知，这m+1个工件的总完工时间为而将这个工件放在m个工件之后加工的总完工时间为

比较这两个总完工时间可知，（4）-（5）=ml＞0。

因此，在最优排序中，若有2-连续加工的工件，必在零时刻开始加工所有的2-连续工件，然后再加工那些单独加工的工件。

2 最优算法

本节将给出问题1｜l，aj=bj=1｜∑Cj的最优算法，对和进行考虑。下面先给出情形的最优排序。

(1)膨润土开发利用水平MEL值同“三率”及权重值有较重要的契合关系，计算时选矿回收率从蒙脱石角度评价，综合利用率从其它共(伴生)矿物角度评价，MEL值中综合利用率权重项高于采矿回采率和选矿回收率权重项。

Ji和Jj两个工件的完工时间减少了（3+4）-（2+l+4+2l）=1-3l，而后s个工件的总完工时间的增加了2ls。由于-2，不难得到1-3l≥2ls，即Ji和Jj完工时间的减少量不小于后面s个工件的总完工时间的增加量。

下面考虑第二种情况，若存在正整数i使得

即

由引理1.2可知，最优排序将2-连续工件先加工，再加工单独工件。设前2j个工件两个一组进行2-连续加工，其余单独加工。此时总完工时间为

类似可以计算得到算法的目标函数值为两种情形分别

因此，当j=i时，目标函数值最小，即算法所得是最优排序。

算法H 2 （1）若工件个数为偶数则将所有工件进行2-连续加工；

（2）若工件个数为奇数，则将前n-1个工件进行2-连续加工，最后一个工件单独加工。

证明：由引理1.1和1.2知，最优排序中只存在2-连续加工和单独加工，且单独加工的工件都在连续加工之后加工。结合笔者的算法，只需证明最优排序不可能存在两个或者两个以上单独加工的工件。

不妨假设在A时刻有两个相邻的工件单独加工，现将这两个工件放在一起加工，比较这两个工件在前后两种排序中的总完工时间。若单独加工，不难得到这两个工件的总完工时间为

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

而将这两个工件放在一起进行2-连续加工，总完工时间为

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

比较这两个总完工时间知（2A+3l+6）-（2A +7）=3l-1≥0。

因此，算法H 2得到的排序为最优排序。

3 结束语

本文研究了带有至少l（0≤l＜1）个单位时间延迟的单位工件单机排序问题，目标是极小化总完工时间。分别针对两种情形给出了相应的最优算法。对于该类问题的进一步研究，可以考虑工件的加工时间更为一般的情况，包括两道工序加工时间不同的情形，以及工件的延迟时间不同的情形下的近似算法设计及分析。

［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

（责任编辑：许惠儿）

1673-3851（2014）01-0083-05

2012-10-31

国家自然科学基金（11001242，11071220）

胡觉亮（1958-），男，浙江杭州人，教授，大学本科，主要从事组合优化与数学建模的研究