基于貪心算法的時(shí)間片優(yōu)先級(jí)排課算法的研究與應(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ī)排課的成功率并不高。如何提高排課軟件的成功率,正受到國(guó)內(nèi)外學(xué)者及軟件技術(shù)人員的普遍關(guān)注。
　　課表編排問題實(shí)質(zhì)上是時(shí)間、教師、班級(jí)、教室、課程這五維關(guān)系的沖突NP完全問題。本文首先從解決排課問題的近似算法入手進(jìn)行分析,如動(dòng)態(tài)規(guī)劃法、回溯法、貪心算法等,找到了解決排課問題的算法基礎(chǔ),創(chuàng)新性地

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

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