具有从属 jobs/job 且需要多个 运行 时间的加权间隔调度
Weighted Interval Scheduling with dependent jobs/job with multiple required running time
间隔调度算法基本上是基于按结束时间对作业进行排序，但是如果调度作业 A 意味着您必须调度作业 C 怎么办？
例如，假设您正在尝试安排广播节目和节目 A 运行 周一上午 10 点至上午 11 点和下午 2 点至下午 3 点，但节目 B 运行 周一 1:30- 2:30？你不能 运行 只有程序 A 的 10-11 部分。它是全有或全无。或者，说节目 运行 周一、周三、周五，但每天不同的时间。
我尝试过的想法：
最短路径算法，您在一周中的每一天同时遍历 7 个图，每个图都经过排序以仅连接后面的程序。如果您在星期一选择程序 A，则所有天都选择它，依此类推。如果程序需要在一天内 运行 两次，则此解决方案无法解决问题。
为 n 个程序生成一个 n 乘 n 的矩阵，并检查每个程序与其他程序的兼容性。遍历一个图，其中每个程序只与非冲突程序连接。有点坚持这个想法并完全寻找下一步或新想法。
我的调度经验法则是除了少数特殊情况外，几乎所有内容都是 NP 完全的。假设您可以找到一天中每个小时都排满的时间表，给定可能需要任意数量的断开连接的时隙的程序。然后你可以解决 https://en.wikipedia.org/wiki/Exact_cover - X 的元素是时隙，子集 S 是程序。一个精确的覆盖对应于调度程序，该程序填充每个时隙且彼此不重叠。
我认为这意味着您正在寻找试探法，例如延迟接受爬山法 (http://www.yuribykov.com/LAHC/), limited discrepancy search (http://wiki.cs.pdx.edu/cs543-spring2010/important_algorithms.html)，以及从多个随机开始的普通爬山法。我建议，无论你做什么，你都以爬山结束，旨在发现人们可以发现的小改进，以确保你的计算机不会产生人们可以做出明显改进的时间表。
我刚刚在 CS Stack Exchange 上重新提出了这个问题，因为这个问题已经过时了，而且已接受的答案中的等效性有点脆弱。在这里重新发布我的答案以获得更高的知名度：
这相当于最大加权独立集问题 - 给定一个带有加权顶点的图，找到顶点的子集，使得子集中的两个顶点在图中不相邻，并且它们的权重之和最大化.
求解问题的图是一种区间图，其中每个顶点代表一组相关区间，其权重是区间权重的总和。如果一个或多个间隔重叠，则在两个顶点之间绘制一条边。
我还不确定这个公式是否易于处理。虽然这个问题是 NP-hard 问题，但我们知道它可以针对某些类型的图有效地解决，包括每个顶点代表一个区间的区间图。请参阅 Independent Set Wikipedia page 了解已知算法。
间隔调度算法基本上是基于按结束时间对作业进行排序，但是如果调度作业 A 意味着您必须调度作业 C 怎么办？
例如，假设您正在尝试安排广播节目和节目 A 运行 周一上午 10 点至上午 11 点和下午 2 点至下午 3 点，但节目 B 运行 周一 1:30- 2:30？你不能 运行 只有程序 A 的 10-11 部分。它是全有或全无。或者，说节目 运行 周一、周三、周五，但每天不同的时间。
我尝试过的想法：
最短路径算法，您在一周中的每一天同时遍历 7 个图，每个图都经过排序以仅连接后面的程序。如果您在星期一选择程序 A，则所有天都选择它，依此类推。如果程序需要在一天内 运行 两次，则此解决方案无法解决问题。
为 n 个程序生成一个 n 乘 n 的矩阵，并检查每个程序与其他程序的兼容性。遍历一个图，其中每个程序只与非冲突程序连接。有点坚持这个想法并完全寻找下一步或新想法。
我的调度经验法则是除了少数特殊情况外，几乎所有内容都是 NP 完全的。假设您可以找到一天中每个小时都排满的时间表，给定可能需要任意数量的断开连接的时隙的程序。然后你可以解决 https://en.wikipedia.org/wiki/Exact_cover - X 的元素是时隙，子集 S 是程序。一个精确的覆盖对应于调度程序，该程序填充每个时隙且彼此不重叠。
我认为这意味着您正在寻找试探法，例如延迟接受爬山法 (http://www.yuribykov.com/LAHC/), limited discrepancy search (http://wiki.cs.pdx.edu/cs543-spring2010/important_algorithms.html)，以及从多个随机开始的普通爬山法。我建议，无论你做什么，你都以爬山结束，旨在发现人们可以发现的小改进，以确保你的计算机不会产生人们可以做出明显改进的时间表。
我刚刚在 CS Stack Exchange 上重新提出了这个问题，因为这个问题已经过时了，而且已接受的答案中的等效性有点脆弱。在这里重新发布我的答案以获得更高的知名度：
这相当于最大加权独立集问题 - 给定一个带有加权顶点的图，找到顶点的子集，使得子集中的两个顶点在图中不相邻，并且它们的权重之和最大化.
求解问题的图是一种区间图，其中每个顶点代表一组相关区间，其权重是区间权重的总和。如果一个或多个间隔重叠，则在两个顶点之间绘制一条边。
我还不确定这个公式是否易于处理。虽然这个问题是 NP-hard 问题，但我们知道它可以针对某些类型的图有效地解决，包括每个顶点代表一个区间的区间图。请参阅 Independent Set Wikipedia page 了解已知算法。