5

问题：考虑 M 台机器上的 n 个作业的调度问题，其中每个作业 i 有一个处理时间 p i并且如果在时间 t 之前完成，则给出利润 g i (t)。所有工作都在时间 0 释放。所有 g i (t) 都是非增函数。为简单起见，我们可以假设机器不是抢占式的。

对于 M=1 和线性递减的利润函数。这个问题可以使用贪心算法在 O(n) 内解决。但对于一般功能，它是 NP 完全的。

我对一般情况感兴趣。请给我任何有关该问题的论文或资源材料的链接。我在互联网上搜索，但没有发现 M>1 的任何有趣内容，尽管之前有关于逼近 M=1 的界限的工作。

请注意，我不希望您解决这个问题，但只需要以前对类似问题的工作（如果有的话）。如果您有任何可以帮助的想法，请随时分享。

我想知道对于 m 台机器和 n 个具有相同发布日期和一般非递增利润函数的工作的问题有什么界限。我在那个方向找到了一张纸

http://arxiv.org/pdf/1008.4889v1.pdf

当所有作业具有相同的发布时间时，他们给出了 O(1) 近似值。我想为这个问题找到类似的文献，以及他们用来解决问题的想法。

4

1 回答 1

2

您可以通过使用例如最小化的调度规则从“贪婪解决方案”开始

g i (t 0 +p i )/p i

在第一台空机器上（我运行所有尚未计划的作业，t 0是第一台机器为空的时间）。

然后可以使用模拟退火之类的元启发式改进此解决方案。解决方案可以表示为作业序列的元组（每台机器一个作业序列）。一个关键点是，允许什么“移动”来改变解决方案。也许对于这个问题，人们可以通过两个基本动作找到已经很好的解决方案：

  • 从一台机器上拿一份工作，然后找一个新的地方插入它。
  • 在机器的作业序列中交换两个作业。
于 2015-10-02T10:36:12.113 回答