課表安排問題的啟發(fā)式算法研究.pdf

1、課表安排問題實質上就是要求將學校開設的所有課程，在滿足一定的約束條件下，合理地安排到有限的課時和教室資源上。課表安排工作是教學活動中必不可少的一個重要環(huán)節(jié)，對提高教學質量和節(jié)約教學資源起著非常關鍵的作用。該問題還是一個NP完全問題，用傳統(tǒng)的精確算法求解容易導致算法復雜度的指數(shù)組合爆炸，因此設計出高效的啟發(fā)式算法成為當前學者研究課表安排問題的熱點之一。因此，無論是從實際應用還是從理論意義的角度考慮，課表安排問題都具有很大的研究價值。

2、 本文主要研究高中和大學的課表安排問題，目標在于設計簡單、實用和高效的啟發(fā)式算法。課表安排問題的困難在于，必須把大量的課程安排到緊缺的資源上，同時不能違反各種苛刻的客觀約束和主觀約束。這些約束通常分為硬約束和軟約束，并定義滿足所有硬約束的課表為可行解，而違反最少軟約束的可行解為最優(yōu)解。本文利用貪心和禁忌搜索的思想，提出了遍歷搜索和定向搜索這兩種鄰域搜索策略，并在其基礎上結合模擬退火，設計出了一個較為通用的二階段課表安排算法。此算法在第

3、一階段構造一個可行解，而其第二階段則在保持課表可行性的同時進行優(yōu)化，嘗試最大程度地去減少軟約束違反的數(shù)量。 高中的排課問題規(guī)模較小，難度較低，具有靜態(tài)性。針對這些特征，本文提出了基于遍歷搜索策略的模擬退火算法對其進行求解。為了證明算法的高效性，本文選用了HDTT和GPTT這兩個高中課表安排的實例進行測試，并和當前高效的遺傳算法、約束規(guī)劃等算法比較。實驗結果的對比分析體現(xiàn)了我們算法的優(yōu)越性。 在大學課表安排問題這個研究領域