algorithm - 具有依赖性和 worker 约束的任务调度优化

Question

我们面临着一个任务调度问题

规范

• 我们有 N 个可用的 worker ，以及要完成的任务列表。
• 每个任务 -->Ti 需要 Di(即 worker*days)才能完成(Demand) ，并且最多只能容纳 Ci 个 worker 同时对其进行处理(容量)。
• 并且某些任务只能在其他任务完成后才能开始(依赖性)。
• 目标是通过将工作人员分配给这些序列来实现总持续时间最小。

例子

• worker 数:10
• 任务列表:[A, B, C]
• 需求:[100 50 10] - 单位: worker 天(任务A需要100个 worker 天才能完成，B需要50个 worker 天，C需要10个 worker 天)
• 容量:[10 10 2] - 单位:worker(任务A只能有10个worker同时工作，B只能容纳10个，而C只能容纳2)
• 依赖:{A: null, B: null, C: B} - A和B可以随时开始，C只能在B完成后开始

示例问题的可能方法:

• 首先分配 B 10 个 worker ，需要 50/10 = 5 天才能完成。然后在第 5 天，我们将 2 个 worker 分配给 C，将 8 个 worker 分配给 A，最多需要 max(10/2 = 5, 100/8 = 12.5) = 12.5 天才能完成。则总持续时间为 5 + 12.5 = 17.5 天。

• 首先分配 A 10 个 worker ，需要 100/10 = 10 天才能完成。然后在第 10 天，我们将 10 名 worker 分配给 B，这需要 50/10 = 5 天才能完成。然后在第 15 天，我们将 2 个 worker 分配给 C，这需要 10/2 = 5 天才能完成。总持续时间为 10+5+5 = 20 天。

所以第一次练习更好，因为 17.5 < 20。但是示例问题还有更多可能的分配实践，我们甚至不确定获得最小总持续时间的最佳实践是什么。

我们想要的是一种算法:

• 输入:Nworker, Demand, Capacity, Dependency

• 输出:最小总持续时间的 worker 分配实践。

我们在为没有依赖的任务分配时考虑过的可能的分配策略:

• 首先尽快完成其他人依赖的任务(例如，在示例中尽快完成B)
• 将 worker 分配给具有最大需求的任务(例如，首先将所有 worker 分配给示例中的A)

但这两者都不是最优策略。

任何想法或建议将不胜感激。谢谢!

Answer 1

这听起来像是具有依赖性的 Job Shop Scheduling，它是 NP-complete(或 NP-hard)。因此，在合理的时间内扩展并提供最佳解决方案可能是不可能的。

我在类似案例(Task assigning 和 Dependend Job Scheduling)上取得了很好的结果，方法是首先执行构造启发式(几乎是您到达那里的那 2 种分配策略之一)然后执行本地搜索(通常是延迟接受或 Tabu Search)以获得接近最佳的结果。