什麼算法用於動態調度系統？

Question

我計劃開發一個自動適合學校教師工作負荷（時間，教學負荷等）的專家系統，並生成課堂部分，與某個部門的主任想要的課程至少達到90％的準確率分配某個學期的時間表。

使用什麼算法？啓發式？優化？任何建議或幫助，高度讚賞！

Answer 1

我的兩個朋友爲類項目做了類似的事情。他們使用了simulated annealing啓發式。他們的結論是，它可能不是這項工作的最佳工具。

嘿，知道不是要做的事情可以很有用吧？ :)

Answer 2

這裏是a paper關於動態調度使用遺傳算法......你可能會發現這裏的一些想法很有用......即使這個領域不一樣，我認爲這個想法更普遍適用。

Answer 3

這裏有一些一般性意見：

1）手動調度很少從頭開始嘗試。相反，有人從上一年的時間表開始，並改變它以考慮到需求的變化。用計算機模擬這種方法的一種方法是使用爬山算法，該算法反覆嘗試一些小的改變以改​​進目前的解決方案。這可以在當前時間表開始。

2）手動過程是否終止於需求集體難以實現的結論，並且其中一些必須被刪除？在這種情況下，您的算法必須足夠透明，以便可以理解失敗或者至少能夠提出這樣的改變（例如，通過最大化懲罰函數，從而產生不滿足所有原始約束的「最不好的」解決方案）。我知道一種情況，一種複雜的基於約束的方法被一種更簡單的算法所取代，因爲基於約束的系統的故障沒有提供足夠的用戶反饋。 3）奇怪的是，下一代系統根本沒有使用複雜的調度。事實證明，粗略地說，當時必須做出決定，並不是所有複雜調度決策的後果都是可預見的，並且從長遠來看，可以無限期保持的簡單可預測時間表比不斷重新安排時間表以搶佔短暫的優勢。

Answer 4

看看curriculum course lesson scheduling的例子Drools Planner（開源，java恐怕）。它使用meta-heuristics，如simulated annealing和tabu search。