任务/作业调度问题

Question

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

假设有一些工人.每个工人都能够完成不同的任务/工作.以下示例可以说清楚:

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

现在我们有一个必须完成的任务列表.例如,列表类似于:T1,T3,T5

有一些限制:

对于上面的示例,我们可能会有这样的计划:

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

您可能已经注意到,上述时间表并非最佳.因为T5必须等待工人C完成T3.以下解决方案更好:

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

因为没有等待.

现在假设我知道worker-tasks矩阵(什么工人可以做什么任务).任务将逐一进行,但不知道它将是什么.我被要求设计一个调度程序,为每个即将到来的任务自动找到一个空闲工作程序.最后所有任务完成后,等待时间最短.

所以我需要一个算法用于这个调度程序.如果完美的车轮已经存在,我不想重新发明轮子.任何人都可以帮忙吗？

谢谢.

Answer 1

听起来您正在寻找“Bin Packing”算法 -

一般的装箱问题与您所说的非常相似，是 NP 困难的，因此如果您的输入大小非常小，您可能会忘记最佳解决方案。

你能找到的是一个保证不会与最佳解决方案相差太远的解决方案，通常是我的一些因素。维基百科的这篇文章是一个很好的起点。