任务/作业调度问题

Question

我有一个任务/作业调度问题，我想找到最好的有效算法来解决它。

假设有一些工人。每个工人都能完成一组不同的任务/工作。下面的例子可以使它更清楚:

  Worker A (can do): T2, T3
  Worker B         : T1, T3, T4
  Worker C         : T3, T5

现在我们有一个必须完成的任务列表。例如，列表是这样的:T1, T3, T5

有一些限制:

1. 每个任务必须由一个工人完成
2. 多个任务可以同时执行
但是一个worker在同一时间只能做一个任务。(他/她在完成任务后才可用)

对于上面的例子，我们可能有一个这样的时间表:

  T1 --> Worker B
  T3 --> Worker C   T5 --> Worker C

正如您可能注意到的，上述计划并不是最优的。因为T5需要等待工人C来完成T3。下面的解决方案更好:

  T1 --> Worker B
  T3 --> Worker A
  T5 --> Worker C

因为没有等待。

现在假设我知道工人-任务矩阵(哪个工人可以做什么任务)。任务会一个接一个来，但不知道会是什么。我被要求设计一个调度器，它可以自动为每个即将到来的任务找到一个空闲的worker。当最后所有的任务都完成了，就有了最小的等待时间。

所以我需要这个调度程序的算法。如果完美的轮子已经存在，我不想重新发明轮子。有人能帮忙吗?

谢谢。

Answer 1

对预先不知道的输入进行操作的算法称为在线算法。当然，它们只是次优的。它们是通过比最优算法差不超过常数因子来衡量的(例如，如果最佳解决方案(不是在线的，即预先有整个输入)需要X步，那么您的在线解决方案应该不超过k*X步，k越小当然越好)。

在你的情况下，要求不明确-"最小等待时间"与什么相比?

一个可能对你有帮助的想法是用最小的任务列表挑选一个可用的worker，为将来的任务保留更"多样化"的worker。

Answer 2

听起来你在寻找一个"Bin Packing"算法-

http://en.wikipedia.org/wiki/Bin_packing

一般的装箱问题，与你所说的非常相似，是NP-Hard的，所以如果你的输入大小大于平凡，你可以忘记最优解。

你能找到的是一个保证不会离最优解太远的解，通常是我的一些因素。那篇维基百科的文章是一个很好的起点。