带精确时间延迟的排序问题

开篇：润墨网以专业的文秘视角，为您筛选了一篇带精确时间延迟的排序问题范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：文章主要研究带精确延迟时间的排序问题，目标是极小化加权总完工时间，分别给出了单台机和两台流水作业的最优算法。

关键词：排序问题；最优算法；延迟

引言

精确时间延迟排序问题按机器数量分为单机问题和两台机流水作业问题。用三参数分别表示为1|exact lj|Cmax，F2|exact lj|Cmax。本文主要研究带精确时间延迟的单机排序问题和两台机流水作业排序问题。每个工件Jj（j=1，2，…，n）有两道工序aj、bj，第一道工序先于第二道工序加工，第一道工序的完工时间c与第二道工序的开始时间S之间存在一个精确的延迟时间，即S=c+lj。所有工序操作时间都相等aj=bj=a，且精确延误时间是工序操作时间的整数倍lj=ka（k∈N+） 。

现有文献考虑的目标函数大多是以最小化时间表长（makespan）为目标函数.本文所考虑的目标函数是最小化加权总完工时间（？撞wjCj）。

1 预备结果

下面先给出相关的定义以及一些初步的结论。

定义1.1 将k个工件的第一道工序连续加工，再按照第一道工序的加工顺序连续加工这k个工件的第二道工序。

当第k个工件的第一道工序ak的完工时间与第一个工件的第二道工序b1的最早开工时间之间存在被迫空闲时，我们称之为被迫不连续加工（图1）。

图1 被迫不连续加工

引理1.1 最优排序中，只存在被迫不连续加工和？资+1-连续加工这两种加工方式，即不存在m（m>k+1或m

证明：用反证法证明。

假设最优排序中将工件进行m-连续加工。当m>k+1时，精确延迟时间大于ka；当m

由于我们所研究问题的精确延迟时间为ka，所以得出矛盾。

即最优排序中，只存在被迫不连续加工和？资+1-连续加工这两种加工方式，即不存在m（m>k+1或m

引理1.2 如果最优排序中存在被迫不连续加工的工件，则这些工件必在连续加工的工件之后进行加工。

证明：假设在A时刻有一组不连续加工的工件，不妨设这组工件中有m（m

由图1可知，这m个工件的完工时间为一组等差数列。

因此，如果最优排序中存在被迫不连续加工的工件，则这些工件必在连续加工的工件之后进行加工。

2 主要结果

本节主要研究带精确时间延迟的极小化加权总完工时间问题，每个工件记为Jj（aj，bj，lj，wj），目标函数为加权总完工时间。单机问题三参数表示为 ；两台机流水作业问

题三参数表示为 。

算法H1

（1）将所有工件重新排序，使w1？叟w2？叟…？叟wn；

（2）再按照J1，J2，…，Jn的顺序将工件分组，每组中有k+1个工件；

（3）进行？资+1-连续加工工件；

（4）当工件个数不足k+1个时，将这些工件进行被迫不连续加工。此时单机问题，机器会出现空闲。

定理2.1 算法H1是上述问题的最优算法。

证明：首先证明算法H1是单机问题的最优算法。

由于我们研究的是精确时间延迟排序，即每个工件第一道工序的完工时间c与第二道工序的开始时间S之间存在一个精确的延迟时间，当工件第一道工序的开始时间确定时，第二道工序的开始时间也相应确定；因此，我们只需要排好每个工件的第一道工序。

下面用反证法分步证明。

（1）显而易见，最优排序中工件J1，J2，…，Jn是按w1？叟w2？叟…？叟wn的顺序加工的。

（2）当工件的个数是k+1的整数倍时，证明最优排序是将工件J1，J2，…，Jn进行k+1-连续加工；当工件的个数不是？资+1的整数倍时，证明最优排序是先将工件J1，J2，…，Jn进行k+1-连续加工，再将最后一组工件进行被迫不连续加工。

由引理1.1和引理1.2可知，最优排序中，只存在被迫不连续加工和k+1-连续加工这两种加工方式，如果最优排序中存在被迫不连续加工的工件，则这些工件必在连续加工的工件之后进行加工。结合我们的算法，只需证明最优排序不可能存在两组或者两组以上被迫不连续加工的工件。

不妨假设在A时刻有两组相邻的被迫不连续加工的工件，第一组中有m个工件，第二组中有n个工件。现将这两组工件放在一起加工，比较这两组工件在前后两种排序中的总完工时间。将这两组工件不放在一起加工时每组的完工时间分别为

现在考虑将这两组工件不放在一起加工时，这m+n个工件的总完工时间为

而将这两组工件放在一起加工时，总完工时间分为m+nk+1三N情况。

情形一：当m+n

情形二：当m+n=k+1时，将这两组工件放在一起加工，变为一组k+1-连续加工工件。这m+n个工件的总完工时间为

比较这两个总完工时间知

情形三：当m+n>k+1时，将这两组工件放在一起加工，变为一组k+1-连续加工工件和一组被迫不连续加工工件；这组被迫不连续加工的工件个数为m+n-k-1个。

这m+n个工件的总完工时间为

比较这两个总完工时间知

由2-（5）、2-（7）、2-（9）式可知，将第二组被迫不连续加工的工件前移，总完工时间不会变大。即最优排序不可能存在两组或者两组以上被迫不连续加工的工件。

综上所述，算法H1是单机问题的最优算法。

显而易见，算法H1是两台机流水作业的最优算法。最优排序如图2所示。

图2 最优排序

3 结束语

本文主要研究带精确时间延迟的单机排序问题和两台机流水作业排序问题并给出了最优算法。

参考文献

[1]Pinedo M. Scheduling： Theory algorithms and Systems[M].2nd ed. Prentice Hall，2002.

[2]Lenstra J K. Private communication，1991.

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

[4]Huo Y， Li H， Zhao H. Minimizing total completion time in two-machine flow shops with exact delays， Computers and Operations Research， 36（6），2009.2018-2030.

[5]Farina A， Neri P. Multitarget interleaved tracking for phased array radar， IEEE Proc. Part F： Comm. Radar Signal Process. 127（4），1980.312-318.

[6]Izquierdo-Fuente A， Casar-Corredera J R. Optimal radar pulse scheduling using neural networks， in： IEEE International Conference on Neural Networks. vol. 7，1994.4588-4591.

[7]Ageev AA， Kononov AV. Approximation algorithms for scheduling problems with exact delays. In： Proceedings of the fourth international workshop， WAOA 2006， Zurich， Switzerland， 2006：1-14.

[8]Ageev AA， Kononov AV. Approximation algorithms for the single and two- machine scheduling problems with exact delays. Operations Research Letters，2007，35（4）：533-540.

作者介：王焕男（1986，5-），女，黑龙江省海伦市人，硕士研究生，助教，主要从事组合优化的研究。