读书人

看不懂王晓东的批处理作业调度的例子解

发布时间: 2012-02-09 18:22:27 作者: rapoo

看不懂王晓东的批处理作业调度的例子
给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理,然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度,设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。
批处理作业调度问题要求对于给定的n个作业,制定最佳作业调度方案,使其完成时间和达到最小。
tji机器1机器2
作业121
作业231
作业323
这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。
  推导了许久,还是搞不清楚王晓东的例子。请高手解释一下最佳方案的18是如何得到的。

[解决办法]
我猜一下,以1,2,3为例:

作业1在机器1上完成的时间为2,在机器2上完成的时间为3
作业2在机器1上完成的时间为5,在机器2上完成的时间为6
作业3在机器1上完成的时间为7,在机器2上完成的时间为10

3+6+10=19,所以是19

1,3,2

作业1在机器1上完成的时间为2,在机器2上完成的时间为3
作业3在机器1上完成的时间为4,在机器2上完成的时间为7
作业2在机器1上完成的时间为7,在机器2上完成的时间为8

3+7+8=18,所以时间和为18
[解决办法]

引用楼主 jqmoab 的帖子:
……
所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和
……

读书人网 >软件架构设计

热点推荐