‘雷區(qū)行走’排課算法的研究與應用.pdf

1、二十世紀五十年代，國外就有人著手研究用計算機來編制課表，1975年Even等人證明了課表問題屬于NP完全問題，是典型的組合優(yōu)化和不確定性調度問題，時間和空間作為臨界資源的一種不定型分配，這是一類困難問題。但是這類問題有它固有的數(shù)學模型，對于這類問題，人們至今還沒有得到其通用的算法，而是更傾向于去尋找一種有效的近似算法。一個可行的課表滿足以下條件： (1)同一時間，一個教師只能上一門課程；(2)同一時間，一個學生只能上一門課程；(

2、3)同一時間，一個教室只能上一門課程； 國內外許多專家和學者從不同的側重點設計出各種排課算法，其中不凡優(yōu)秀。但大多算法有其不足之處，存在局限性。經(jīng)過反復認真和冷靜的思考，‘雷區(qū)行走’排課算法誕生了。在實際排課應用中，‘雷區(qū)行走’排課算法扮演了一個排‘雷’專家的角色，把矛盾和沖突一一化解，在復雜的排課領域締造沒有矛盾和沖突的排課世界?！讌^(qū)行走’排課算法主要有以下兩個特點： (1)‘雷區(qū)行走’排課算法本質就是編排課表，但并

3、不是編排工作的全部，只是很小的部分?！讌^(qū)行走’排課算法只是有選擇的編排課表，把產(chǎn)生矛盾和沖突的可能消除。‘雷區(qū)行走’排課算法正如一位心理學家，把性格不合可能引發(fā)打架的學生分到不同的班級一樣。 (2)‘雷區(qū)行走’排課算法也是一個理想模型，在實際應用中單獨使用不能起作用，‘雷區(qū)行走’排課算法要發(fā)揮效能，必須和輔助算法捆綁(輔助算法在第三章給出)。 排課是一個學校教務工作的核心環(huán)節(jié)，其重要性不言而喻。在一周內，一位老師，要上