关于调度作业分析

Question

我正在阅读关于调度算法分析的主题：

假设我们有以下四个作业和相关的运行时间。一个可能的时间表是j1、j2、j3和j4，因为j1以15 (时间单位)完成，j2在23，j3在26，j4在36，平均完成时间为25。一个较好的时间表是j3、j2、j4和j1，平均完成时间为17.75。

工作时间

j1 15

j2 8

j3 3

j4 10

我的问题是，作者如何计算平均完成时间，即我们如何在上述文本中得到25和17.75？

谢谢!

Answer 1

这些作业按顺序运行(一次一个)。

因此，对于order j1-j2-j3-j4，j1在15，j2在15+8=23，j3在15+8+3=26，j4在15+8+3+10=36。然后，他们将15、23、26和36平均起来，使用标准的sum/count公式获得25：

  (15 + 23 + 26 + 36) / 4
=         100         / 4
=                25

换句话说，他们谈论的完成时间不是一项工作开始时需要多长时间，而是从第一项工作开始需要多长时间(即一个时间点，而不是一个持续时间)。我不知道这样的衡量标准有多有用，但基于这些数字，他们就是这么做的。

对于order j3-j2-j4-j1，j3在3，j2在3+8=11，j4在3+8+10=21，j1在3+8+10+15=36。其平均值(3、11、21和36)是17.75。

平均完成时间的最佳(最低)解决方案是按照持续时间的增加顺序完成工作。

这是因为一组四人中的最后一个作业总是同时完成，不管顺序如何(本例中是36)。

因此，为了减少平均终点，其他三项工作的终点应尽可能低。

而且，适用于四个作业的相同规则也适用于三个作业(一旦运行时间最长的j1从混合作业中删除)。然后是两个作业，一旦您删除了j4。

一旦你换掉了三份工作，唯一的选择就是你应该选择的工作(当然)。