内容发布更新时间 : 2024/6/21 13:10:13星期一 下面是文章的全部内容请认真阅读。

题目二 流水作业调度

2.1问题重述

n个作业{1,2,?,n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi，1?i?n。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

2.2问题分析

设全部作业的集合为N?{1,2,?,n}。S是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。

经过分析，流水作业调度问题具有最优子结构性质。设?是所给n个流水作业的一个最优调度，它所需的加工时间为a?(1)?T'。其中T'是在机器M2的等待时间为b?(1)时，安排作业?(2),?,?(n)所需的时间。

记S?N?{?(1)}，则有T'?T(S,b?(1))。 由流水作业调度问题的最优子结构性质可知:

1?i?nT(N,0)?min{ai?T(N?{i},bi)} （1）

一般形式：

T(S,t)?min{ai?T(S?{i},bi,max{t?ai,0})} （2）

i?S 从公式（1）可以看出，该问题类似一个排列问题，求N个作业的最优调度问题，利用其子结构性质，对集合中的每一个作业进行试调度，在所有的试调度中，取其中加工时间最短的作业做为选择方案。将问题规模缩小。公式（2）说明一般情况下，对作业集S进行调度，在M2机器上的等待时间，除了需要等该部件在M1机器上完成时间，还要冲抵一部分原来的等待时间，如果冲抵已成负值，

自然仍需等待M1将作业做完，所以公式取max{t?ai,0}。

2.3算法描述

从上面的分析可知，流水作业问题一定存在满足Johnson法则的最优调度，从而得到流水作业问题的Johnson算法： （1）令N1?{i|ai?bi}，N2?{i|ai?bi}；

（2）将N1中作业依ai的非减序排序；将N2中作业依bi的非增序排序； （3）N1中作业接N2中作业构成满足Johnson法则的最优调度。 算法代码具体实现，见附录。

2.4验证结果

我们任意选取数据进行验证，即任意选取五个不同的作业在机器1上的运行时间为{3,2,5,4,1}，在机器2上运行时间为{4,6,3,1,2}。输出结果：完成作业的最短时间为：17；作业调度的顺序为：{4,1,0,2,3}。

图2 算法程序运行结果