4

这是流行的 El Goog 问题的变体。

考虑以下调度问题：有 n 个作业，i = 1..n。有 1 台超级计算机和无限的 PC。每个作业都需要先经过超级计算机的预处理，然后再在 PC 上进行处理。超级计算机上作业 i 所需的时间为 si，i = 1..n。对于 PC，它是 pi，i = 1..n。PC 可以并行工作，但超级计算机一次只能完成一项工作。创建一个时间表 S，超级计算机将根据该时间表处理这些作业。计划 S 中的完成时间 Ti(S) 由 PC 上作业完成的时钟时间给出。我们想找到一个最小化 Maxi[Ti(s)] 的时间表（可以理解为：我们需要找到一个最小化最高完成时间的时间表）. 提出了以下贪心算法： 在 PC 上按处理时间的递减顺序排列作业。该算法的复杂度为 O(nlogn)。要么证明这个算法产生了一个最优解，要么提供一个反例来证明它没有。

我的解决方案（不确定这是否正确）：我认为我们如何订购工作并不重要。最高完成时间仍然相同。考虑这个在 PC 上处理作业列表的时间示例：<5、7、17、8、10>。这将产生 <5, 12, 29, 37, 47> 的完成时间。根据算法，我们将列表排序为 <17, 10, 8, 7, 5> 并将产生 <17, 27, 35, 42, 47> 的完成时间。因此，虽然从技术上讲，贪心算法确实给出了最佳排序，但它需要 nlogn 时间来做到这一点，而简单地遍历作业列表会给我们同样的结果。

如果有人认为贪心算法会更好，或者我的方法有缺陷，我会很感激你的想法。谢谢！

更新：我想我可能有答案。超级计算机花费的时间无关紧要。这里的关键是 PC并行运行。从 pi = <5, 7, 17, 8, 10> 的初始示例中，让我们添加 si = <8, 5, 1, 12, 9>。现在，在默认的未排序顺序中，我们的处理时间为 <13, 20, (8 + 5 + 1 + 17 = )31, 34, 45>。所以 45 是完成的时间。假设 pi 的排序顺序是递减的。输出为：<18、20、30、34、40>。[排序输入：pi = <17, 10, 8, 7, 5>, si = <1, 9, 12, 5, 8>]。

这里有一个例子可以说明一切：si = <17, 10>, pi = <10, 17>。未排序情况下的输出（也恰好按 si 的降序排序）将是 <27, 44>。根据 pi 排序，输入为：si = <10, 17>, pi = <17, 10>。输出为 <27, 37>。由于 PC 并行运行，因此您希望最后发送最短的作业。

4

4 回答 4

1

对于数量有限的 PC：

wlog 假设没有超级计算机，你的问题将转换为 Minmum Makespan Scheduling问题（或ppt），即 NP-Hard。因此，您当前的算法不起作用或 P = NP。

但是贪心算法对于近似很有用，您也可以将Bin Packing转换为这个问题，并通过固定数量的近似误差找到好的结果，但运行时不会是好的多项式（例如 n^10）。

PS：您可以简单地假设没有超级计算机，为此假设 Max(s i ) < Min(P i ) 的实例。

P.S2：我一开始没有看到无限数量的PC，所以我写了这个，我会考虑无限数量的PC。

无限案例：

您当前的算法是错误的，假设以下条件：

For PCs: <5, 7, 17, 8, 10>
For super computer: <1000,800,500,600,700).

您当前的解决方案将失败。

于 2012-04-05T09:15:14.053 回答
0

这些作业需要按照 PC 时间的降序排列。
来源 - http://mypathtothe4.blogspot.in/2013/03/greedy-algorithm-example.html

于 2017-09-18T20:09:45.937 回答
0

在找到这个问题之前，我在cs.stackexchange提出了同样的问题。Jaeyoon Kim那里的答案证明了贪婪解决方案的最优性。

于 2020-06-21T11:33:23.817 回答
0

S={a1,a2,...,an} of n单位时间任务。一个单位时间的任务恰好需要 1 个单位的时间来完成最后期限的d1,d2,...,dn, 1<=di<=n 惩罚w1,w2,...,wn。wi如果任务ai没有按时完成，则会产生惩罚di，如果任务在截止日期前完成，则不会受到惩罚。

问题是为 S 找到一个时间表，以最大限度地减少错过最后期限所造成的总损失

我对此有疑问。如下

ai 1 2 3 4 5 6 7
di 4 2 4 3 1 4 6
wi 70 60 50 40 30 20 10

这个问题的解决方案是

{a2,a4,a1,a3,a7,a5,a6}
penalty, w5+w6=50
于 2017-02-23T09:39:07.487 回答