algorithm - 如何*最佳*解决调度 N 个作业(到达时间，执行时间)提前已知，以便 N 个作业的平均等待时间最短？

Question

有人能解释一下如何最好地解决这个问题吗？

很明显，即使这两个链接说 SJF 是最优的，贪婪的方法也不会产生最优解(我不认为他们考虑平均等待时间，而是有最小化总执行时间的标准)。

• http://www.cs.jhu.edu/~yairamir/cs418/os2/sld026.htm

• http://os.etf.bg.ac.rs/OS2/Stud/Rad01/sjf.htm

从我对这个问题的了解来看，似乎需要详尽地列出所有可能的工作安排(排列)。但我不确定是否有一种基于动态规划的方法可以让人们获得最佳解决方案，而不必详尽地找到所有可能排列的平均等待时间。

问题:n 不同的(r_i, t_i) 数组中给出了作业请求时间和作业长度时间的列表工作。 r_i表示作业请求何时进来，即作业的到达时间或请求时间，t_i表示作业执行所花费的时间单位。只有一个人处理工作，并且一次只能从事一项工作。

使用输入数组 (r_i, t_i) 计算一组给定的 N 作业的最小平均等待时间？

示例:列表(r_i, t_i):job-1(0, 3), job-2(2, 5), job-3 (3, 2)

如果作业按照job-1, job-2, job-3的顺序完成，那么:

job-1 的等待时间 = 作业结束时间 - 作业请求时间 = 3-0

job-2 的等待时间 = 8-2 = 6

job-3 的等待时间 = 10-3 = 7

所以平均等待时间是:(3 + 6 + 7)/3。

但是如果这些工作按照job-1, job-3, job-2的顺序完成:平均等待时间是:(3+2+8)/3 = 13/3，比原来的顺序要好。所以最小平均等待时间是 13/3 时间单位。

编辑:

1. 作业的等待时间被定义为(完成时间 - 到达或请求时间)。也可以称之为周转时间。问题是最小化总等待时间/N 的问题之一，如果假设等待时间的不同定义为(作业开始时间 - 作业到达时间)，这将与最小化总等待时间的问题相同。

2. SJF(最短作业优先)未给出最优调度的示例:

J1 (1, 5)J2 (2, 2)J3 (0, 3)

最短的工作 j2。但是选择 j3，j2，j1 比在 j2，j3，j1(等待时间 = 4+7+11)中先选择 j2 更好的调度(总等待时间 = 3+3+9)

1. 另一个例子:J1 (0, 100)J2 (1, 2)

在时间0，最短的工作是J1。 J1-J2 作为时间表，总等待时间为 100+102。 J2-J1 时间表给出了 3+103 的最佳总等待时间。

Answer 1

您的描述中有些地方不清楚:是否允许抢占？即是否有可能停止一项工作，开始另一项工作，然后再完成这项工作。在这两种情况下，您都可以查看 this website以便了解您的问题是 NP-hard 还是多项式可解。

• 如果允许抢占，则问题容易解决，写成1|pmtn;rj|∑Cj
• 如果不允许抢占，1|rj|∑Cj 是NP-hard，因此您无法找到贪心算法来解决您的问题。

此外，查看完成时间的总和或等待时间的总和是严格等效的，您只需添加/删除发布日期和处理时间的总和即可。