智能排課算法的研究及實現(xiàn).pdf

1、課表的編排是高校教務(wù)活動中非常重要的工作之一,是保證教學(xué)秩序正常進(jìn)行的前提和基礎(chǔ)。目前大多數(shù)院校的排課主要采用手工編排方法,但是隨著高校招生規(guī)模的擴大,教學(xué)資源變得嚴(yán)重不足,教學(xué)資源的利用率也日益被重視起來,同時辦學(xué)形式的多樣化及排課涉及面廣、約束條件多等各類復(fù)雜要求使得手工排課已經(jīng)無法完成,因此借助計算機輔助排課成為一種解決手段。如何利用計算機快速、有效地編排出合理、滿意的課表,是一項值得研究的工作,也吸引了國內(nèi)外一大批研究人員對其進(jìn)

2、行深入研究。然而,在實際應(yīng)用中,由于排課問題是一個NP完全問題,開發(fā)出符合要求的排課系統(tǒng)是一件難事,迄今為止,國內(nèi)尚沒有用戶普遍反映良好的計算機自動排課系統(tǒng)。
　　 本文通過分析課表制定的原則和要求,依據(jù)我校排課的實際需求,建立了排課問題的多目標(biāo)組合規(guī)劃模型,提出了基于貪心思想的智能排課算法。模型通過將無沖突的硬性條件作為約束條件,將一些合理性、適應(yīng)性原則作為優(yōu)化目標(biāo),采用多目標(biāo)優(yōu)化的理論進(jìn)行求解。本文提出的智能排課算法通過分析

3、歷史排課數(shù)據(jù),利用全概率計算公式,將得到的排課規(guī)律應(yīng)用到自動排課過程中,使得到的排課結(jié)果更加合理。在自動排課過程采用了優(yōu)先級的思想,根據(jù)用戶定義的或依照一定規(guī)則計算出的優(yōu)先級順序進(jìn)行課程安排,算法分成教室選擇和時間選擇兩個階段,按照貪心算法的思想,針對每次選定的教室和時間計算其目標(biāo)函數(shù),根據(jù)多目標(biāo)優(yōu)化的理論選擇當(dāng)前最優(yōu)解進(jìn)行課程安排。
　　 針對排課過程中出現(xiàn)的“甩課”問題,本文提出了一個無回溯的簡單調(diào)整算法,通過搜索出要安排“

4、甩課”任務(wù)可能需要取消的任務(wù)集合,結(jié)合用戶決策,取消某些任務(wù)安排即降低其安排的優(yōu)先級,然后重新利用自動排課算法進(jìn)行“甩課”任務(wù)安排。用戶的參與避免了產(chǎn)生不合理的調(diào)整結(jié)果,該算法可以在無回溯的情況下有效的解決“甩課”問題。
　　 最后,本文通過實驗詳細(xì)介紹了智能排課算法過程,證明了通過該算法產(chǎn)生的排課結(jié)果是正確的,并且可以較好的滿足課程、教師等約束條件,有效的利用教室資源。在此基礎(chǔ)上,本文設(shè)計實現(xiàn)了一個排課系統(tǒng),對系統(tǒng)的數(shù)據(jù)庫結(jié)構(gòu)