在多台机器上利润下降的高效调度工作

Question

问题:考虑M台机器上n个作业的调度问题,其中每个作业具有处理时间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)近似值.我想找到类似的问题文献以及他们用来解决问题的想法.

Answer 1

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

gi (t _{0 +} pi ₎ / _pi

在第一台空机器上（i 运行所有尚未调度的作业，t ₀是时间，其中第一台机器是空的）。

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

• 从一台机器上取出一份作业，然后找到一个新的位置来插入它。
• 交换机器作业序列中的两个作业。