scheduling - 资源约束项目调度

Question

我需要你的帮助来解决这个问题。我有一组任务，每个任务都有其执行时间。我有两种类型的约束。第一种是任务之间的优先关系。第二种约束类型是允许一组任务同时执行。例如：我有一个包含 6 个任务和以下边 (T1,T2)、(T2,T3)、(T4,T3)、(T4,T5) 和 (T6,T5) 的图 G。假设 T1,T4 能够一起执行，T1,T6 也可以执行，但 T4,T6 不能。考虑到每个任务的执行时间。考虑到某些任务的并行执行，如何找到满足任务之间优先关系的调度，同时最小化调度的长度。

Answer 1

如果排除约束（“T1，T4 能够一起执行”）不存在（并且没有添加其他约束），您可以通过获取所有先前任务的最大完成时间来开始每个任务。这将是最佳的并且可以很好地扩展。您将自动获得最短的制造时间。它不是 NP-complete/hard，也不是作业车间调度。

不幸的是，排除约束（以及您将来可能添加的任何其他约束）将其变成作业车间调度（如 Lars 所述），这是 NP 完全/困难的。请参阅开源 java 实现的作业车间调度变体的视频，该演示说明了为什么某些任务开始晚于其先前任务完成的原因。要解决这个问题，请研究启发式、元启发式（禁忌搜索，...）或其他相关技术。

Answer 2

为简单起见，您可以使用基于优先级规则的建设性启发式方法以及调度生成方案或也称为 SGS，请参阅此以获取更多参考。启发式将根据一些标准生成一个有序的活动列表，SGS 将把这个列表作为输入并生成时间表。在您的 SGS 实施中，您将根据您的第二个约束来判断两个任务是否可以并行执行。

如果你想要更健壮的东西，你可以使用元启发式，基本上你将生成一个解决方案（任务列表）并使用本地搜索技术修改这个解决方案，探索你的解决方案搜索空间。您可以根据优先级规则生成解决方案，并使用 SGS 实施对其进行评估。这只是对元启发式如何工作的简化解释，有几个差异。元启发式的一个很好的例子是模拟退火，应用于 RCPSP 问题：http ://www.sciencedirect.com/science/article/pii/S0377221702007610 。