多台机器利润递减的高效调度作业
Efficient scheduling jobs with declining profits on multiple machines
问题：考虑M台机器上n个作业的调度问题，其中每个作业i的处理时间为pi并给出a如果在时间 t 之前完成，则利润 gi(t)。所有的工作都在时间 0 被释放。所有的 gi(t) 都是非递增函数。为简单起见，我们可以假设机器不是抢占式的。
对于 M=1 和线性递减的利润函数。这个问题可以使用贪心算法在 O(n) 中解决。但是对于一般函数它是NP完全的。
我对一般情况感兴趣。请给我任何 link 的论文或资源材料来解决这个问题。我在互联网上进行了搜索，但没有发现 M>1 的任何有趣内容，尽管之前有关于 M=1 的近似边界的工作。
请注意，我并不期望您能解决这个问题，而只是需要您之前针对类似问题（如果有）的工作。如果您有任何可以帮助的想法，请随时分享。
我想知道对于具有相同发布日期和一般非递增利润函数的 m 台机器和 n 个作业，这个问题的边界是多少。我找到了朝那个方向的论文
http://arxiv.org/pdf/1008.4889v1.pdf
当所有作业都具有相同的发布时间时，他们给出了 O(1) 近似值。我想为这个问题找到类似的文献以及他们解决问题的想法。
您可以使用调度规则从 "greedy solution" 开始，例如最小化
gi(t0+pi)/pi
在第一台空机器上（我遍历所有尚未安排的作业，t0是时间，第一台机器是空的）。
然后可以使用 Simulated Annealing 等元启发式方法改进此解决方案。解决方案可以表示为作业序列的元组（每台机器一个作业序列）。很关键的一点是，什么"moves"都可以改一个解。也许对于这个问题，可以通过两个基本步骤找到已经很好的解决方案：
- 从一台机器上取一份工作，然后找一个新的地方插入它。
- 交换机器作业序列中的两个作业。
问题：考虑M台机器上n个作业的调度问题，其中每个作业i的处理时间为pi并给出a如果在时间 t 之前完成，则利润 gi(t)。所有的工作都在时间 0 被释放。所有的 gi(t) 都是非递增函数。为简单起见，我们可以假设机器不是抢占式的。
对于 M=1 和线性递减的利润函数。这个问题可以使用贪心算法在 O(n) 中解决。但是对于一般函数它是NP完全的。
我对一般情况感兴趣。请给我任何 link 的论文或资源材料来解决这个问题。我在互联网上进行了搜索，但没有发现 M>1 的任何有趣内容，尽管之前有关于 M=1 的近似边界的工作。
请注意，我并不期望您能解决这个问题，而只是需要您之前针对类似问题（如果有）的工作。如果您有任何可以帮助的想法，请随时分享。
我想知道对于具有相同发布日期和一般非递增利润函数的 m 台机器和 n 个作业，这个问题的边界是多少。我找到了朝那个方向的论文
http://arxiv.org/pdf/1008.4889v1.pdf
当所有作业都具有相同的发布时间时，他们给出了 O(1) 近似值。我想为这个问题找到类似的文献以及他们解决问题的想法。
您可以使用调度规则从 "greedy solution" 开始，例如最小化
gi(t0+pi)/pi
在第一台空机器上（我遍历所有尚未安排的作业，t0是时间，第一台机器是空的）。
然后可以使用 Simulated Annealing 等元启发式方法改进此解决方案。解决方案可以表示为作业序列的元组（每台机器一个作业序列）。很关键的一点是，什么"moves"都可以改一个解。也许对于这个问题，可以通过两个基本步骤找到已经很好的解决方案：
- 从一台机器上取一份工作，然后找一个新的地方插入它。
- 交换机器作业序列中的两个作业。