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

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

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

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