关于批处理作业调度问题中“完成时间和“的疑问

算法设计与分析（第4版）——王晓东

 

 

这3个作业的6种可能的调度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它们所相应的完成时间和分别是19，18，20，21，19，19。易见，最佳调度方案是1,3,2，其完成时间和为18。

 

 

疑问：

1."批处理作业调度"和"流水作业调度问题"有什么区别？

2.为什么是"结束时间和"，而不是“要求确定这n个作业的最优处理顺序，使得从第1个作业在机器1上处理开始，到最后一个作业在机器2上处理结束所需时间最少”，哪些情况下，查看其“结束时间和”？

（结果待老师回复，或者大牛指点迷津）

下面试分析疑问2的两个结果不等价，即"结果时间和"与"处理结束时间"结果不相同:

同样以n=3为例，考虑以下实例：

 

 

调度方案分析：

 

处理结束时间：10

“结束时间和”：3+6+10=19

 

处理结束时间：8

“结束时间和”：3+7+8=18

 

处理结束时间：10

“结束时间和”：4+6+10=20

 

处理结束时间：9

“结束时间和”：4+8+9=21

 

处理结束时间：8

“结束时间和”：5+6+8=19

 

处理结束时间：8

“结束时间和”：5+6+8=19

综上，对比不同调度下的情况：

调度方案	批处理作业调度	流水作业调度
（1, 2, 3）	19	10
（1, 3, 2）	18	8
（2, 1, 3）	20	10
（2, 3, 1）	21	9
（3, 1, 2）	19	8
（3, 2, 1）	19	8

 

老师的相关问题的回复：