调度，贪心算法

Question

调度，贪心算法

4

这是一个流行的El Goog问题的变形。

考虑以下调度问题：有n个作业，i = 1..n。有1台超级计算机和无限数量的个人电脑。每个任务需要先由超级计算机进行预处理，然后在个人电脑上处理。作业i在超级计算机上所需的时间为si，i = 1..n。对于个人电脑，它是pi，i = 1..n。个人电脑可以并行工作，但超级计算机一次只能处理1个作业。根据计划S创建计划表，超级计算机将按照计划表处理作业。在计划S中完成时间Ti(S)由作业在个人电脑上完成的时钟时间给出。我们希望找到最小化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的时间来完成，而简单地迭代作业列表则可以给我们相同的结果。

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

更新：我想我可能有答案。超级计算机所需的时间无关紧要。关键在于个人电脑并行运行。从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并行运行，您希望将最短的作业最后发送。

- user183037

你如何证明在你的解决方案中完全忽略π值是正确的？ - Ali Ferhat

@AliFerhat：我认为对于超级计算机来说，同样的论点也成立吧？改变π的顺序似乎并不影响最后一个作业的完成时间，但我可能是错的。 - user183037

4个回答

0

工作需要按照PC计时的递减顺序排序。
来源 - http://mypathtothe4.blogspot.in/2013/03/greedy-algorithm-example.html

- Akash

0

在发现这个问题之前，我在 cs.stackexchange 上问了同样的问题。Jaeyoon Kim 在那里的答案证明了贪心算法的最优性。

- Cantfindname

0

S={a1,a2,...,an} 是由n个单位时间任务组成的集合。每个单位时间任务需要恰好1个单位的时间来完成。截止日期为d1,d2,...,dn，1<=di<=n，惩罚为w1,w2,...,wn。如果任务ai在时间di之前未完成，则会产生惩罚wi，如果任务在截止日期完成，则不会产生惩罚。

问题是找到一个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

- Damaceen

您能否重新格式化您的回答，以使其更易于理解？ - Paul Kertscher

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Saeed Amiri · Accepted Answer

对于有限数量的电脑：

不失一般性，假设没有超级计算机，则您的问题将转换为最小完工时间调度问题（或ppt），这是NP难问题。因此您当前的算法不起作用或P = NP。

但贪心算法对于逼近是有用的，此外，您可以将装箱问题转换为此问题，并通过适量误差的逼近找到良好的结果，但运行时间将不是多项式时间（例如n ^ 10）。

附言：您可以简单地假设没有超级计算机，为此请假设实例，使得Max(s_i) < Min(P_i)。

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

无限数量的情况：

你目前的算法是错的，假设这些条件：

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

你当前的解决方案将会失败。