考虑以下调度问题:有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并行运行,您希望将最短的作业最后发送。