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

《带精确时间延迟的排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、带精确时间延迟的排序问题　　摘要：文章主要研究带精确延迟时间的排序问题，目标是极小化加权总完工时间，分别给出了单台机和两台流水作业的最优算法。　　关键词：排序问题；最优算法；延迟　　引言　　精确时间延迟排序问题按机器数量分为单机问题和两台机流水作业问题。用三参数分别表示为1

2、exactlj

3、Cmax，F2

4、exactlj

5、Cmax。本文主要研究带精确时间延迟的单机排序问题和两台机流水作业排序问题。每个工件Jj（j=1，2，…，n）有两道工序aj、bj，第一道工序先于第二道工序加工，第一道工序的完工时间c与第二道工序的开始时间S之间存在一个精确的延迟时间，即S=c+lj

6、。所有工序操作时间都相等aj=bj=a，且精确延误时间是工序操作时间的整数倍lj=ka（k∈N+）。　　现有文献考虑的目标函数大多是以最小化时间表长（makespan）为目标函数.本文所考虑的目标函数是最小化加权总完工时间（？撞wjCj）。　　1预备结果　　下面先给出相关的定义以及一些初步的结论。　　定义1.1将k个工件的第一道工序连续加工，再按照第一道工序的加工顺序连续加工这k个工件的第二道工序。　　当第k个工件的第一道工序ak的完工时间与第一个工件的第二道工序b1的最早开工时间之间存在被迫空闲时，我们称之为被迫不连续加工（图1）。　　图1被迫不连续加工　　引理1.

7、1最优排序中，只存在被迫不连续加工和？资+1-连续加工这两种加工方式，即不存在m（m>k+1或mk+1时，精确延迟时间大于ka；当mk+1或m

8、的工件，不妨设这组工件中有m（m

9、；　　（3）进行？资+1-连续加工工件；　　（4）当工件个数不足k+1个时，将这些工件进行被迫不连续加工。此时单机问题，机器会出现空闲。　　定理2.1算法H1是上述问题的最优算法。　　证明：首先证明算法H1是单机问题的最优算法。　　由于我们研究的是精确时间延迟排序，即每个工件第一道工序的完工时间c与第二道工序的开始时间S之间存在一个精确的延迟时间，当工件第一道工序的开始时间确定时，第二道工序的开始时间也相应确定；因此，我们只需要排好每个工件的第一道工序。　　下面用反证法分步证明。　　（1）显而易见，最优排序中工件J1，J2，…，Jn是按w1？叟w2？叟…？叟wn的顺序

10、加工的。　　（2）当工件的个数是k+1的整数倍时，证明最优排序是将工件J1，J2，…，Jn进行k+1-连续加工；当工件的个数不是？资+1的整数倍时，证明最优排序是先将工件J1，J2，…，Jn进行k+1-连续加工，再将最后一组工件进行被迫不连续加工。　　由引理1.1和引理1.2可知，最优排序中，只存在被迫不连续加工和k+1-连续加工这两种加工方式，如果最优排序中存在被迫不连续加工的工件，则这些工件必在连续加工的工件之后进行加工。结合我们的算法，只需证明最优排序不可能存在两组或者两组以上被迫不连续加工的工件。　　不妨假设在A时刻有两组相邻的被迫不连续加工的工件，第一组中有

11、m个工件，第二组中有n个工件。现将这两组工件放在一起加工，比较这两组工件在前后两种排序中的总完工时间。将这两组工件不放在一起加工时每组的完工时间分别为　　现在考虑将这两组工件不放在一起加工时，这m+n个工件的总完工时间为　　而将这两组工件放在一起加工时，总完工时间分为m+nk+1三?N情况。　　情形一：当m+n