一个任务/工作调度问题

Question

我有一个任务/工作调度问题，希望找到高效的算法来解决它。

假设有一些工人，每个工人能够完成不同的一组任务/工作。以下示例可能会让问题更加清晰明了：

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

现在我们有一系列必须完成的任务，例如：T1、T3、T5。

以下是一些限制条件：

1. 每个任务必须由一个工人负责
2. 多个任务可以同时进行
3. 但一个工人同时只能做一个任务（在完成任务之前他/她不可用）

对于上述例子，我们可能会有这样的时间表：

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

正如您所注意到的，上面的日程安排并不是最优的。因为T5必须等待工人C完成T3。以下解决方案更好：

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

因为这里没有等待时间。

现在假设我知道工人任务矩阵（哪个工人可以做哪些任务）。任务一个接一个地到来，但是不知道接下来会是什么任务。我被要求设计一个调度程序，自动为每个任务找到空闲的工人。当最后所有任务完成时，会有最小的等待时间。

因此，我需要一个算法来实现这个调度程序。如果已经存在完美的解决方案，我就不想重复造轮子。请问有人可以帮忙吗？

谢谢。

- yanjiang qian

---

如果你无法预知未来，我猜测将任务按照它们到达的顺序发送给能力最少的工人，会为未来留下最多的可能性。工人是有望最终得到工作的人类吗？还是工人是计算机，它们不在乎是否得到工作？ - sarnold

对我来说，“为每个任务自动找到空闲工人”、“不知道它会是什么”和“最短等待时间”似乎彼此矛盾。如果你不能计划，就无法优化。 - Lasse V. Karlsen

如果没有空闲的工作人员，你打算如何处理？只是排队等待吗？ - Lasse V. Karlsen

另外，所有的工人都同样适合完成所有的任务吗？换句话说，是否有可能工人A比其他工人更适合完成T1类型的任务？ - Lasse V. Karlsen

@Lasse：这也是我的第一反应，与其使用布尔条件，更好的建模方式是为每个工人将执行速度与给定类型的任务相关联。 - Matthieu M.

Answer 1

听起来你正在寻找一个“装箱”算法 -

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

一般的装箱问题与您所描述的非常相似，是NP-困难的问题，因此如果输入规模超过微不足道的程度，您可以忘记最优解。

您可以找到一个解决方案，保证不会太远离最优解，通常是通过某个因子实现的。那篇维基百科文章是一个很好的起点。

- shoosh

---

实际上这不是装箱问题，而是作业车间调度问题：https://en.wikipedia.org/wiki/Job_Shop_Scheduling - Christian Severin

Answer 2

算法在没有预先知道输入的情况下运行，但是随着输入的到来而被称为在线算法。它们只是次优的。它们的衡量标准不仅仅是比最优算法更劣一些（例如，如果最佳解决方案（不是在线的，即具有全部输入）需要X步，您的在线解决方案应该不超过k*X步，当然k越小越好）。

在您的情况下，要求不清楚 - 与什么相比的“最短等待时间”？

一个可能有帮助的想法是选择一个任务列表最小的可用工人，为未来的任务保存更“多样化”的工人。

- davka