资源约束项目调度

Question

我需要你的帮助来解决这个问题。我有一组任务，每个任务都有它的执行时间。我有两种类型的约束。第一种类型是任务之间的优先关系。第二种约束类型是允许同时执行一组任务。例如:我有一个图G，它有6个任务和以下边(T1，T2)，(T2，T3)，(T4，T3)，(T4，T5)和(T6，T5)。考虑到每个任务的执行时间。如何找到满足任务间优先关系的调度，并在考虑某些任务并行执行的情况下最小化调度长度。

Answer 1

如果排除约束("T1，T4能够一起执行“)不存在(并且没有添加其他约束)，那么您可以通过获取所有先前任务的最大完成时间来启动每个任务。这将是最优的，并具有良好的可扩展性。您将自动获得最短的最短完成时间。这将不是NP-完全/困难，也不是作业车间调度。

不幸的是，排除约束(以及将来可能添加的任何其他约束)会将其转化为作业车间调度(如Lars所提到的)，这是NP-完全/困难的。一个开源java实现job shop调度变体的See this video，演示了为什么一些任务开始得比它们之前的任务完成得晚。要解决这个问题，可以看看启发式，元启发式(禁忌搜索，...)或其他相关技术。

Answer 2

为了保持简单，您可以使用基于优先级规则的构造性启发式，以及时间表生成方案，或者也称为SGS，请参阅this以获得进一步的参考。启发式将根据某些标准生成活动的有序列表，SGS将此列表作为输入，并将生成计划。在您的SGS实现中，您将根据第二个约束判断两个任务是否可以并行执行。

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