權區間調度與多個相關的作業/作業所需運行時間

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）以及從多個隨機開始的普通爬山。我建議，無論你做了什麼，你都會得到一個爬山的結果，旨在發現人們可以發現的小改進，以確保你的計算機不會產生一個時間表，人們可以做出明顯的改進。