我知道那裏有些NP-hard/NP-complete的調度問題......但是，他們中沒有一個用這種方式表示這種情況也是NP。是否所有調度問題NP-Hard？
如果你有一組約束爲startAfter，startBy任務，並時間都試圖用一個單個資源 ...你可以解決的時間表或者確定它不能得到解決沒有詳盡的搜索？
如果答案是「sorry pal，但這是NP-complete」什麼是最好的啓發式（s？）使用，並且有辦法減少花費的時間a）解決計劃和b）確定一個無法解決的時間表。
我已經通過實現「最小窗口優先」啓發式的遞歸實現（在序言中）基本的衝突解決目標。這實際上很快找到解決方案，但發現無效的時間表非常緩慢。有沒有辦法解決這個問題？
Yay for compound questions！
大多數調度問題中最難的部分正在掌握可靠性和完整的約束條件。如果我們把創建一所大學的時間表，例如：早上
那麼你需要一個可以應付變化的時間表系統，所以當一個約束在最後一刻發生變化時，您不必更改完整的時間表。
上述所有內容在有關調度系統的研究論文中通常都會被忽略。對於給定調度問題的NP完整性，在現實生活中，你並不關心，因爲即使它不是NP完整的，你也不可能定義什麼是「最佳解決方案」，這麼好就是好足夠。
查看http://www.asap.cs.nott.ac.uk/watt/resources/university.html瞭解可能幫助您入門的論文列表;調度軟件中仍然有許多PHD。
偉大的鏈接！ .. 謝謝。像這樣的鏈接幾乎屬於http://lambda-the-ultimate.org – 2010-01-29 17:01:59
市場領先的大學調度系統仍然在列表中，並且使用lambda很多。 – 2010-01-29 17:09:18
「」上述所有內容在有關調度系統的研究論文中通常都被忽略了「」 就像旁註：那不是真的。至少在最新的研究中，他們試圖讓它更真實。例如。請參閱2007年國際時間表競賽賽道的要求。 – Karussell 2010-01-29 22:19:23
您可以使用動態編程來解決其中的一些問題。貪婪的算法也浮現在腦海。調度理論既深刻又美觀，但我發現的那兩個將解決我所面臨的大多數問題。也許我很幸運。
貪婪算法不會總是產生一個結果時，雖然存在，是否正確？就我的目的而言，如果存在安排所有任務的解決方案，我必須找到它。 「關閉」的解決方案將無法正常工作=/ 我會在interwebz上尋找一些動態編程調度算法...謝謝！ – 2010-01-29 14:25:18
沒問題。但是，從技術上講，你只能這麼靠近。一個好的啓發式比沒有好，有時甚至可以。調度是優化的基礎，是一個非常深入的領域。從簡單開始，繼續前進。 – wheaties 2010-01-29 14:33:08
最小的窗口第一次真的幫助很多找到解決方案......我需要弄清楚如何修剪我的搜索空間，以便「錯誤」返回來得快。 – 2010-01-29 14:36:10
startBy是什麼意思？
隨着startAfter和如果只有一個資源，那麼一個快速的解決方案可能是使用topological sorting。示例算法以線性時間運行，但如果圖形包含循環，則不包括錯誤情況。
Java中的一些源代碼可以從我的timefinder項目中獲得： https://timefinder.svn.sourceforge.net/svnroot/timefinder/trunk/timefinder-algo/src/main/java/de/timefinder/algo/graph/ – Karussell 2010-01-29 16:22:03
startBy和startAfter之後引用任務必須在其中開始的窗口...即任務a必須在2:00之後開始，並在2:30之後開始30分鐘的「機會窗口」。感謝您的鏈接..我會研究它...現在：-D – 2010-01-29 16:39:39
乍一看，它似乎只考慮到任務的順序，而不考慮該任務的限制......不過......創建可能的「有序」列表並在啓動到O（n^n）完整掃描之前檢查這些解決方案的有效性可能不是一個壞主意。 – 2010-01-29 16:51:13
偉大的列表...看起來像我最小的WindowFirst是一個與EarliestDueDate緊密相關的 – 2010-02-23 03:19:15
經常有像調度NP硬/完整的優化問題好approximation algorithms。您可以瀏覽Ahmed Abu Safia的課程筆記Approximation Algorithms for scheduling或各種papers。
從某種意義上說，所有公鑰密碼術都是用「較難」的問題完成的，比如因子分解，部分原因是因爲NP難題提供了太多簡單的情況。這種NP完全性使得它們在「道德上很難」，這也給它們帶來了太多簡單的問題，而這些問題往往屬於最優化的誤差範圍。
hardness of approximation有一個更深入的理論討論了近似算法的侷限性。
考慮調度問題，那就是在P類：
輸入：其中包括開始時間和結束時間的活動列表。
按結束時間排序。
選擇此排序列表的前N個元素以查找您可以在給定時間內排定的最大活動量。
您可以添加如下警告：所有活動必須在下午5點結束，在這種情況下，當您處理列表時，停止一次到達此時間結束的活動。
你認爲你會爲這個問題添加更多約束嗎？如果是這樣，它看起來像一個時間表問題，這是'通常'通過約束編程解決 http://en.wikipedia.org/wiki/Constraint_programming 甚至線性編程 http://en.wikipedia.org/ wiki/Linear_programming 看一看名爲unitime.org（約束編程）和ilog的約束求解器（非常昂貴，但非常快）的開源項目。 – Karussell 2010-01-29 22:13:32