求教：排課演算法？

01-06

最近碰到一個項目，涉及到學校的排課，相關條件如下：
1.分年級排課，一個年級一共12個班
2.分12個科目，主科目：一個老師帶兩個班，副科目：一個老師可以帶4個班或者6個班，老師在同一時間不能排課

2：主科就是6節以上的，一周最多只能排兩天第一節，兩個第五節，副科不能拍1、2節；
3.主科，周一至周五，下午必須排一節課
4.副科上下午分布均勻
5.小語種的課一般都是連堂

6.還有一節外教課1-10班，不能排周五
有沒有人知道如何處理（相關的演算法）

排課不要碰，一方面是沒有什麼好演算法可以解決，另一方面你現在寫的有限條件可能有解，到最後用起來條件一複雜就呵呵了，無解無解無解無解。

條件這個東西能複雜到什麼程度？ xx要送孩子上幼兒園不能上第一節課，xxx的課不能排上午最後一節不忍心看學生挨餓等午餐，語文每周要有兩節連堂上作文，等等。

關鍵這些條件還不是滿足不滿足的問題，而是有的需要絕對滿足，有的盡量滿足。難就難在這盡量滿足的條件了，比如十條需要盡量滿足的條件，有矛盾，權重怎麼安排，手工調整然後測試能不能排出課，有這功夫手動直接排課了；電腦用遺傳演算法或者模擬退火演算法做？你可以洗洗睡吧轉天看了，一般情況下解還是無法接受的，因為出來的怪胎雖然滿足你所寫但怎麼看也不是你要的，比如這樣的：尼瑪三個年級36個班同時在操場上體育課，分年級排課是誰定的？重新按多年級一起排？呵呵，這個數量級排完了估計也該放假了。

自動排課基本無解，還是老老實實手動排吧。

手動怎麼排，excel + vba就能解決從排課到輸出的全套工作啦。

Prolog（逃

這個演算法有點值錢←_←……

約束滿足問題，可以看看CSP領域解決rostering相關問題的文獻。如果在hard constraints之外還考慮個體的soft constraints，問題會比較複雜。

搜索吧，本來排課問題就是NP-Complete的，你還加這麼多要求，還讓不讓人活了。

不過你這麼多條件正好可以拿來剪枝啊，搜索演算法肯定很快。

之前跟別人有討論過。可以參考一下這篇http://www.aloul.net/Papers/faloul_sch_gcc07.pdf

就是把排課的要求表示成布爾方程，再把這些方程傳給SAT求解器就行了。SAT求解器嘛見SAT Competitions。下個miniSAT用一下就差不多了。

模擬退火

可以考慮抽象成規劃問題，用LINGO解解試試，不過估計很慢。

這個問題和多核系統的task scheduling很類似，應該是個NP-Complete的，如果只是追求相對最優解的話可以考慮模擬退火

可以試試Constraint programming

Timetable problem 本質上可以看做一個constraint satisfaction problem。這類問題如樓上所說，其實非常非常的複雜，遠遠不是一般的搜索演算法可以解決的。比較好的technique有Constraint Programming。

像LZ的問題，一般都是先假設decision variable：

假設每個班一天八節課，那周一到周五就一共是40個Slot可以排課，12個班則有12x40=480個Slot。一共12個科目，所以一共有480x12=5760個binary variable，1代表該Slot被排該科目，0代表相反。

然後就把LZ的約束條件都用這些Variable寫出來，比如說以第一節課不能是副科，那就強制所有副科每天第一個slot的variable為0，等等。然後輸入Solver就可以出結果了。開源的Constraint Programming Solver有GECODE - An open, free, efficient constraint solving toolkit可以考慮。

約束補償問題，可以直接用回溯法解決

本科時候《計算機程序設計基礎》大作業。一心想寫個程序算全校排課的最優解。最終導致。。。這門課剛好過T_T