权区间调度与多个相关的作业/作业所需运行时间

Question

间隔调度算法是围绕排序由结束时间的工作非常基础的，但如果调度作业A意味着你必须安排工作C.

例如，比如你正在试图安排广播节目和节目A的周一上午10点到11点和下午2点到3点，但节目B的周一将会运行1：30-2：30？你不能只运行程序A的10-11部分。它是全部或没有。或者，假设程序每周运行星期一，星期三，星期五但在不同的时间。

想法我打得四处：

最短路径算法，你同时横梁7个图形一周的每一天，每一个图形来分类的连接只有到来后的程序。如果您在星期一选择节目A，则可以在所有日期选择节目，如此类推。如果程序需要在一天内运行两次，此解决方案不能解决问题。

为n个程序生成n×n矩阵并检查每个程序与其他程序的兼容性。遍历每个程序只与非冲突程序连接的图形。有点卡住这个想法，完全寻找下一步或新想法。

Answer 1

我的调度经验法则是几乎所有东西都是NP-完成的，只有少数特例。假设你可以找到一个计划，每天在一小时内填满，因为可能的程序需要任意数量的断开时隙。然后你可以解决https://en.wikipedia.org/wiki/Exact_cover - X的元素是时隙，子集S是程序。确切的封面对应于调度程序，它们填充每个时隙而不会相互重叠。

我认为这意味着您正在寻找启发式方法，如延迟接受登山（http://www.yuribykov.com/LAHC/），有限差异搜索（http://wiki.cs.pdx.edu/cs543-spring2010/important_algorithms.html）以及从多个随机开始的普通爬山。我建议，无论你做了什么，你都会得到一个爬山的结果，旨在发现人们可以发现的小改进，以确保你的计算机不会产生一个时间表，人们可以做出明显的改进。