使用哪種算法爲學校生成時間表

我正在研究一個簡單的應用程序，它將爲學校生成時間表（每日計劃）。我已經閱讀了算法的基礎知識，但從哪裏開始感到困惑。
使用哪種算法爲學校生成時間表

問題：
分配老師考慮到了很多限制類相似：
1）除
2）教師
3的專長）持續不超過2類..等

不言而喻，不應該有重疊。基本上我需要每天爲固定數量的工作時間分配N個教師到M班（8）。

的輸入：
1）總與他們的專門知識的沿的類
2）教師數
3）的受試者/每一類
4）每天每類講座數
5課程）像每天老師，每每週老師總工作小時最低/最高工時等

我的問題等柔性約束：
1）它是正確的把它看作是帶有多重約束的分配問題？
2）我應該使用哪種算法？（匈牙利算法？）
3）我應該從一開始就得到整套約束，然後生成表格，還是應該在中間步驟完成？

我是初學者學習/實現算法，所以任何幫助指向我在正確的方向讚賞！謝謝。

2010-02-21 Checksum

我發現了一個PostScript文件，講述了一個**禁忌搜索**（http://en.wikipedia.org/wiki/Tabu_search）算法，用於爲教師分配課程（http://www.uv.es/sestio /TechRep/tr01-01.ps）。這主要是數學啓發式。我希望它給你一些方向。 – 2010-02-21 05:57:42

這是重複的。幾周前我回答了這個問題：http://stackoverflow.com/questions/2177836/algorithm-for-creating-a-school-timetable – 2010-02-21 07:17:03

@Stefano，無價的鏈接！謝謝 – Checksum 2010-02-21 12:09:51

你選擇了一個簡單的問題開始。像這樣的調度優化是NP完全的。關於如何處理類似這樣的問題的問題被稱爲約束滿意度，有大量的論文。您可以執行一個最簡單但也非常耗時的窮舉搜索，如果您的課程數量不足，將無法使用。你可以看看解決方案基礎，這是一個用於解決這些事情的.net工具套件。 Scott Hanselman做了一個播客關於它這裏http://www.hanselminutes.com/default.aspx?showID=209，你可以在這裏找到更多關於它 http://code.msdn.microsoft.com/solverfoundation。如果你喜歡自己做嘗試看看GSAT或其他一些演化算法看起來很有趣http://www.springer.com/engineering/book/978-3-540-48582-7。

來源

2010-02-21 07:14:14 stimms

這個問題每週至少會出現一次，答案（包括我的）總是相同的。我想我們應該在調度算法中創建一個特定的標記（如果不存在的話）。

我會重申，像這樣調度問題的最合適的解決方案是約束編程領域。雖然其他優化技術對於小問題是可以的，但是對於一些限制，配方通常是痛苦的。考慮你必須爲一些簡單的約束創建的所有整數變量。因爲這個問題通常需要一堆可行的時間表（或者確定不可行性）而不是最佳的解決方案，所以CP是首選方法，因爲這是它設計的目的。大多數其他方法都要求用戶「強制」一個實際上不存在的問題的最優性條件。

來源

2010-02-21 07:59:59 Grembo

使用哪種算法爲學校生成時間表

回答

相關問題