基于貪心算法的時間片優(yōu)先級排課算法的研究與應(yīng)用.pdf

1、隨著信息技術(shù)的不斷發(fā)展,計(jì)算機(jī)的應(yīng)用領(lǐng)域越來越廣。作為高校最重要的教學(xué)調(diào)度工作,排課工作也從傳統(tǒng)的手工排課轉(zhuǎn)向了利用計(jì)算機(jī)進(jìn)行排課。但目前計(jì)算機(jī)排課的成功率并不高。如何提高排課軟件的成功率,正受到國內(nèi)外學(xué)者及軟件技術(shù)人員的普遍關(guān)注。
　　課表編排問題實(shí)質(zhì)上是時間、教師、班級、教室、課程這五維關(guān)系的沖突NP完全問題。本文首先從解決排課問題的近似算法入手進(jìn)行分析,如動態(tài)規(guī)劃法、回溯法、貪心算法等,找到了解決排課問題的算法基礎(chǔ),創(chuàng)新性地

2、提出了將貪心算法和時間片優(yōu)先級算法相融合的基于貪心算法的時間片優(yōu)先級排課算法。重點(diǎn)描述和比較了目前流行的基于動態(tài)規(guī)劃法的自動排課算法,基于回溯法的優(yōu)先級排課算法,以及本文所提出和研究的基于貪心算法的時間片優(yōu)先級排課算法。自動排課算法是以課程為中心進(jìn)行搜索匹配,取最先匹配的值,未對數(shù)據(jù)進(jìn)行擇優(yōu)選取,所以不能對教學(xué)資源合理分配,也不能滿足一些特殊要求(比如有些老師偏向于集中式上課,有些課程安排到上午會更合適些等)。優(yōu)先級排課算法主要從解決時

3、間、教師、班級、教室這四維關(guān)系之間的沖突入手,按班級和教室分類,根據(jù)時間數(shù)組來編排教師、教室、班級課表,對于課程的一些特殊要求無法體現(xiàn)。而基于貪心算法的時間片優(yōu)先級排課算法針對時間、教師、教室、班級、課程這五維關(guān)系間的沖突,按時間片優(yōu)先級來解決教師、班級、教室、課程間的沖突,不但對教學(xué)資源能進(jìn)行合理分配,而且也能滿足排課時的一些特殊要求,排出的課表比較合理。從排課的成功率、準(zhǔn)確率以及算法的效率來分析,基于貪心算法的時間優(yōu)先級排課算法明顯