我们面临着一个任务调度问题
规范
- 我们有 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
)
但这两者都不是最优策略。
任何想法或建议将不胜感激。谢谢!
最佳答案
这听起来像是具有依赖性的 Job Shop Scheduling,它是 NP-complete(或 NP-hard)。因此,在合理的时间内扩展并提供最佳解决方案可能是不可能的。
我在类似案例(Task assigning 和 Dependend Job Scheduling)上取得了很好的结果,方法是首先执行构造启发式(几乎是您到达那里的那 2 种分配策略之一)然后执行本地搜索(通常是延迟接受或 Tabu Search)以获得接近最佳的结果。
关于algorithm - 具有依赖性和 worker 约束的任务调度优化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39136653/