处理具有相同优先级的作业的算法

Question

我正在解决 Papadimitrou 和 Vazirani 合着的一本名为 Algorithms 的书中的练习题。

下面是问题:

一个服务器有n个顾客在等着服务。每个客户所需的服务时间是预先知道的:客户 i 是 ti 分钟。因此，例如，如果按照 i 递增的顺序为客户提供服务，则第 i 个客户必须等待 Sum(j = 1 to n) tj 分钟。

我们希望尽量减少总等待时间。给出一个有效的算法。

我的尝试:

我想到了几种方法，但无法决定哪种方法最好，或者其他任何方法都比我的好。

方法一:

以循环方式为他们服务，时间片为 5。但是，当我在决定时间片时需要更加小心。它不应该太高或太低。于是，我想到了选择时间片作为服务次数的平均值。

方法二:假设作业根据他们花费的时间排序并存储在数组 A[1...n]

首先服务 A[1]，然后是 A[n]，然后是 A[2]，然后是 A[n-1]，依此类推。

我真的不能决定哪个是这个问题的最佳解决方案。我错过了什么吗？

谢谢，钱德

Answer 1

您可以通过添加排序部分并改进您的循环法来解决这个问题，

首先根据服务时间对客户进行排序

现在除了以循环方式给每个客户一个时间片 t 之外，您还可以检查客户的剩余时间是否少于 t/2，如果是则完成他的任务

所以对于第一个排序列表中的每个客户 时间 t 的服务器客户 如果他的剩余时间 < t/2 那么现在就完成他的服务 否则转移到下一个客户