如何处理 k-Processor 调度问题？
How to approach the k-Processor Scheduling Problem?
所以，我有一个问题。假设有 k 个处理器和 k*n 个作业。现在，每个处理器应该正好做 n 个工作，每个处理器都需要特定的时间来完成特定的工作。如下图，这里Time k这一列是指处理器k做不同工作所花费的时间。
任务是找到我们可以完成所有工作的最短时间。现在，对于 k=2，我发现贪婪的方法有效。我们可以只计算每个工作的 T2-T1。如果我们在处理器 2 中执行任务，这是时间的净损失。因此，我们可以按非降序对其进行排序，并将前 n 个作业分配给处理器 2，其余处理器 1。我无法扩展解决方案进一步获得更高的 k 值。有没有通用的算法？
如果有人可以为此指出任何论文，或者指导我了解总体方向，我将不胜感激。虽然我需要一个精确的解决方案，但足够接近的解决方案也可以。
编辑：机器 运行 一个接一个，但不是同时进行。因此，完成时间不是所有机器所用时间的最小值，而不是它们时间的总和。
首先，对于 k = 2，简单的贪婪方法不 有效。要看到这一点，只需考虑两个处理器中作业成本相同的特殊情况。这种特殊情况是 Partition Problem which is well-known to be NP-complete. If 2 < k this becomes Multiway number partitioning.
您描述的问题被称为 Unrelated-machines scheduling. The standard polynomial time approximation is from Approximation algorithms for scheduling unrelated parallel machines，它给出的结果与最佳结果的偏差不超过 2 倍。
所以，我有一个问题。假设有 k 个处理器和 k*n 个作业。现在，每个处理器应该正好做 n 个工作，每个处理器都需要特定的时间来完成特定的工作。如下图，这里Time k这一列是指处理器k做不同工作所花费的时间。
任务是找到我们可以完成所有工作的最短时间。现在，对于 k=2，我发现贪婪的方法有效。我们可以只计算每个工作的 T2-T1。如果我们在处理器 2 中执行任务，这是时间的净损失。因此，我们可以按非降序对其进行排序，并将前 n 个作业分配给处理器 2，其余处理器 1。我无法扩展解决方案进一步获得更高的 k 值。有没有通用的算法？ 如果有人可以为此指出任何论文，或者指导我了解总体方向，我将不胜感激。虽然我需要一个精确的解决方案，但足够接近的解决方案也可以。
编辑：机器 运行 一个接一个，但不是同时进行。因此，完成时间不是所有机器所用时间的最小值，而不是它们时间的总和。
首先，对于 k = 2，简单的贪婪方法不 有效。要看到这一点，只需考虑两个处理器中作业成本相同的特殊情况。这种特殊情况是 Partition Problem which is well-known to be NP-complete. If 2 < k this becomes Multiway number partitioning.
您描述的问题被称为 Unrelated-machines scheduling. The standard polynomial time approximation is from Approximation algorithms for scheduling unrelated parallel machines，它给出的结果与最佳结果的偏差不超过 2 倍。