具有依赖性和工人约束的任务调度优化
Task Scheduling Optimization with dependency and worker constraint
我们遇到了任务调度问题
规格
- 我们有 N 个工作人员可用，还有一个任务列表。
- 每项任务-->
Ti需要Di（即工人*天）完成（需求), 最多只能容纳 Ci 名工人同时工作 (容量).
- 并且有些任务只能在其他任务完成后才能开始（Dependency）。
- 目标是通过将工作人员分配给这些序列来实现总最小持续时间。
示例
- 工人人数：10
- 任务列表：
[A, B, C]
- 需求:
[100 50 10] - 单位：工人天 （任务A需要100工人天完成，B需要50 worker天，C需要10个worker天）
- 容量:
[10 10 2] - 单位: worker (任务A只能有10个worker同时工作，B只能容纳10个，C只能容纳 2)
- Dependency:
{A: null, B: null, C: B} - A 和 B 可以随时启动，C 只能在 B 完成后才能启动
示例问题的可能方法：
先给B分配10个工人，需要50/10 = 5天完成。然后在第 5 天，我们将 2 个工人分配给 C，将 8 个工人分配给 A，最多需要 max(10/2 = 5, 100/8 = 12.5) = 12.5 天才能完成.那么总时长是5 + 12.5 = 17.5天。
先给A分配10个工人，需要100/10 = 10天完成。然后在第 10 天，我们将 10 个工人分配给 B，这需要 50/10 = 5 天才能完成。然后在第 15 天，我们将 2 个工人分配给 C，这需要 10/2 = 5 天才能完成。总时长为 10+5+5 = 20 天。
所以第一次练习比较好，因为17.5 < 20.
但是示例问题还有更多可能的分配实践，我们甚至不确定获得最小总持续时间的最佳实践是什么。
我们要的是一个算法:
输入:
Nworker, Demand, Capacity, Dependency
输出：最小总持续时间的工人分配实践。
我们在为没有依赖性的任务分配时考虑的可能分配策略：
- 首先尽快完成别人依赖的任务（比如例子中尽快完成
B）
- 将工人分配给具有最大需求的任务（例如，首先将所有工人分配给示例中的
A）
但两者中的 none 被证明是最优策略。
如有任何想法或建议，我们将不胜感激。谢谢！
这听起来像 Job Shop Scheduling 具有依赖性，它是 NP-complete（或 NP-hard）。因此，在合理的时间内扩展并提供最佳解决方案可能是不可能的。
我在类似案例 (Task assigning and Dependend Job Scheduling) 上取得了很好的结果，方法是首先执行构建启发式（几乎是您到达那里的那 2 种分配策略之一）然后执行本地搜索（通常是延迟接受或禁忌搜索）以获得接近最佳的结果。
我们遇到了任务调度问题
规格
- 我们有 N 个工作人员可用，还有一个任务列表。
- 每项任务-->
Ti需要Di（即工人*天）完成（需求), 最多只能容纳 Ci 名工人同时工作 (容量). - 并且有些任务只能在其他任务完成后才能开始（Dependency）。
- 目标是通过将工作人员分配给这些序列来实现总最小持续时间。
示例
- 工人人数：10
- 任务列表：
[A, B, C] - 需求:
[100 50 10]- 单位：工人天 （任务A需要100工人天完成，B需要50 worker天，C需要10个worker天） - 容量:
[10 10 2]- 单位: worker (任务A只能有10个worker同时工作，B只能容纳10个，C只能容纳 2) - Dependency:
{A: null, B: null, C: B}- A 和 B 可以随时启动，C 只能在 B 完成后才能启动
示例问题的可能方法：
先给B分配10个工人，需要50/10 = 5天完成。然后在第 5 天，我们将 2 个工人分配给 C，将 8 个工人分配给 A，最多需要 max(10/2 = 5, 100/8 = 12.5) = 12.5 天才能完成.那么总时长是5 + 12.5 = 17.5天。
先给A分配10个工人，需要100/10 = 10天完成。然后在第 10 天，我们将 10 个工人分配给 B，这需要 50/10 = 5 天才能完成。然后在第 15 天，我们将 2 个工人分配给 C，这需要 10/2 = 5 天才能完成。总时长为 10+5+5 = 20 天。
所以第一次练习比较好，因为17.5 < 20. 但是示例问题还有更多可能的分配实践，我们甚至不确定获得最小总持续时间的最佳实践是什么。
我们要的是一个算法:
输入: Nworker, Demand, Capacity, Dependency
输出：最小总持续时间的工人分配实践。
我们在为没有依赖性的任务分配时考虑的可能分配策略：
- 首先尽快完成别人依赖的任务（比如例子中尽快完成
B） - 将工人分配给具有最大需求的任务（例如，首先将所有工人分配给示例中的
A）
但两者中的 none 被证明是最优策略。
如有任何想法或建议，我们将不胜感激。谢谢！
这听起来像 Job Shop Scheduling 具有依赖性，它是 NP-complete（或 NP-hard）。因此，在合理的时间内扩展并提供最佳解决方案可能是不可能的。
我在类似案例 (Task assigning and Dependend Job Scheduling) 上取得了很好的结果，方法是首先执行构建启发式（几乎是您到达那里的那 2 种分配策略之一）然后执行本地搜索（通常是延迟接受或禁忌搜索）以获得接近最佳的结果。