楊 明
(南京鐵道職業(yè)技術(shù)學(xué)院,江蘇 南京 210031)
基于優(yōu)先級(jí)分類(lèi)的排課算法設(shè)計(jì)
楊 明
(南京鐵道職業(yè)技術(shù)學(xué)院,江蘇 南京 210031)
文章分析了國(guó)內(nèi)外對(duì)于排課算法的研究現(xiàn)狀,提出了基于等價(jià)分類(lèi)的優(yōu)先級(jí)排課算法的思想,包含確定算法的基本原則、算法的等價(jià)分類(lèi)和優(yōu)先級(jí)的確定,最后給出了算法的流程圖和相關(guān)測(cè)試數(shù)據(jù)。
教務(wù)系統(tǒng);算法;優(yōu)先級(jí)
對(duì)于課表的研究,國(guó)外最早于20世紀(jì)50年代出現(xiàn)。直到1962年,戈特利布最早提出了一個(gè)數(shù)學(xué)模型,用于求解課表問(wèn)題。此后大家對(duì)此問(wèn)題進(jìn)行了深入的討論和廣泛的研究,如印度Vastapur大學(xué)的Arabinda Tripathy和加拿大Montreal大學(xué)的Jean Aubin等。Tripathy,他的主要工作是以“人”為單位進(jìn)行排課,利用拉格朗日松弛法來(lái)解決,這種方法雖然可以減少變量的個(gè)數(shù),但是人為造成課程間的沖突。其他有代表性的算法有遺傳算法、螞蟻算法等,通過(guò)實(shí)踐表明,單純的運(yùn)用數(shù)據(jù)方法去解決人為因素過(guò)多的課表問(wèn)題,不是切實(shí)可行的辦法。
直到1976年,Even等人證明了此問(wèn)題本質(zhì)上就是一個(gè)NP完全問(wèn)題。因?yàn)閷?duì)于排課的約束條件太多,而一時(shí)也無(wú)法找到所有的約束條件,隨著排課時(shí)間段和學(xué)生人數(shù)、課程數(shù)的不斷增加,排列組合方案會(huì)成幾何數(shù)增長(zhǎng),進(jìn)而在尋求最優(yōu)解的過(guò)程中,系統(tǒng)會(huì)消耗大量的時(shí)間和資源,最后到了讓人無(wú)法忍受的程度,從而導(dǎo)致系統(tǒng)無(wú)法使用。
國(guó)內(nèi)對(duì)排課的研究始于20世紀(jì)80年代初,林漳希、林堯瑞教授于1984年宣布了此課題研究成果,成為國(guó)內(nèi)研究的基礎(chǔ)。已經(jīng)成型的成果有東南大學(xué)的UTSS系統(tǒng),大連理工的智能教學(xué)組織管理調(diào)度系統(tǒng)3.0等。這些已經(jīng)成熟的系統(tǒng)應(yīng)用到實(shí)際工作中后,的確可以減輕排課人員的工作負(fù)擔(dān)。但是這些排課系統(tǒng)大多是模擬人工排課,以班級(jí)作為排課的基本單元,在排課時(shí)依賴具體的教學(xué)體制和教學(xué)模式,不適合廣泛推廣。
排課,是一項(xiàng)非常復(fù)雜的腦力勞動(dòng),它需要在一定的時(shí)間、空間內(nèi),在有限的資源供給條件下,實(shí)現(xiàn)課表的最優(yōu)解。排出的課表既要滿足課程教學(xué)的硬性要求,又要滿足老師、學(xué)生的軟性要求,由于突發(fā)因素太多,每個(gè)學(xué)校情況又不同,因此找到最優(yōu)課表的概率幾乎為零。
本節(jié)使用基于分類(lèi)思想的優(yōu)先級(jí)算法,放棄尋找最優(yōu)解的過(guò)程,而是在給定資源的情況下,滿足必備條件,適當(dāng)滿足選擇條件,產(chǎn)生基礎(chǔ)課表,然后在這基礎(chǔ)課表上對(duì)其優(yōu)化,從而產(chǎn)生滿足實(shí)際需求的可行性課表。這種算法求解的過(guò)程,易于程序?qū)崿F(xiàn),維護(hù)簡(jiǎn)單,效率較高又能兼顧實(shí)際需要,是切實(shí)可行的解決方案。
課表的編排本質(zhì)上就是老師、班級(jí)、課程、時(shí)間、地點(diǎn)的5種資源的排列組合問(wèn)題,在對(duì)這5種資源進(jìn)行合理配置的時(shí)候,最基本的一個(gè)原則就是避免沖突,即任何兩種資源不能出現(xiàn)互相沖突,例如在同一時(shí)間,給一個(gè)老師安排了兩門(mén)課程。
除了這個(gè)基本原則之外,根據(jù)教學(xué)規(guī)律和課程特點(diǎn),排課要遵循一定的基本規(guī)則,按照基本規(guī)則排課,不但能減少?zèng)_突的發(fā)生,而且課表的實(shí)用性會(huì)更強(qiáng),這些基本規(guī)則應(yīng)包含:(1)同一時(shí)間內(nèi),同一個(gè)班級(jí)只能安排一門(mén)課程;(2)同一時(shí)間內(nèi),同一個(gè)老師只能安排一門(mén)課程;(3)同一時(shí)間內(nèi),同一個(gè)教室只能安排一門(mén)課程;(4)教室的座位數(shù)應(yīng)大于上課總?cè)藬?shù);(5)上課教室類(lèi)型要滿足課程需要,例如不能給需要多媒體教室的課程安排一個(gè)普通教室。以上5個(gè)規(guī)則,被稱為“硬”規(guī)則,所謂的“硬”規(guī)則,就是說(shuō)必須要滿足的規(guī)則,如果不能滿足,則教學(xué)活動(dòng)無(wú)法進(jìn)行。
除了“硬”規(guī)則,根據(jù)教學(xué)規(guī)律和人體生物鐘,排課還必須滿足如下“軟”規(guī)則:
(1)對(duì)于同一個(gè)班級(jí),同一門(mén)課程,一天的課時(shí)量最多2節(jié);(2)理論課程盡量安排上午授課;(3)實(shí)踐課程盡量安排在下午授課;(4)必修課程應(yīng)放到體育課程前面安排,體育課應(yīng)盡量安排在第3,4節(jié)或第5,6節(jié)。以上4個(gè)規(guī)則,被稱為“軟”規(guī)則,所謂的“軟”規(guī)則,就是可以使教學(xué)活動(dòng)安排得更加合理有序。排課算法應(yīng)該優(yōu)先滿足“硬”規(guī)則,然后盡量滿足“軟”規(guī)則。
在設(shè)計(jì)算法時(shí),為了實(shí)現(xiàn)上述規(guī)則并有效地降低算法的難度,主要采用了基于優(yōu)先級(jí)的等價(jià)分類(lèi)算法。為了實(shí)現(xiàn)規(guī)則4和規(guī)則5的要求,把教室進(jìn)行分類(lèi),按照其類(lèi)型分為普通教室、多媒體教室和實(shí)訓(xùn)室,如表1所示。
然后,再根據(jù)教室的座位數(shù),對(duì)每個(gè)類(lèi)進(jìn)行進(jìn)一步細(xì)分:如45人以下為一類(lèi),90人以下為一類(lèi)等若干種。教室分類(lèi)完成后,再進(jìn)行課程類(lèi)別分類(lèi),分為理論課、實(shí)踐課、體育課程,體育課可以算做實(shí)踐課程,但是由于排課功能的需要,所以單獨(dú)劃分,各個(gè)學(xué)??梢愿鶕?jù)實(shí)際情況做出調(diào)整,如表2所示。
課程類(lèi)別分類(lèi)完成后,進(jìn)行課程類(lèi)型優(yōu)先級(jí)分配,課程類(lèi)型分為選修課、必修課、板塊課程。優(yōu)先級(jí)依次從低到高,在高職院校中,板塊課程基本上都是屬于必修課程的范圍。在同一板塊內(nèi)上課的班級(jí),一般是上課地點(diǎn)不同,但是上課時(shí)間都保持一致,例如大學(xué)英語(yǔ)、體育課。具體分類(lèi)如表3所示。
課程類(lèi)型完成后,進(jìn)行周學(xué)時(shí)優(yōu)先級(jí)設(shè)置。排課人員根據(jù)其以往的工作經(jīng)驗(yàn)來(lái)設(shè)置該優(yōu)先級(jí),優(yōu)先級(jí)的本質(zhì)就是一系列上課的組合方式。比如一門(mén)課程的周學(xué)時(shí)是6,最佳的上課方式可能是:“13”“31”“51”;表示該課程一周上3次課,分別為周一的34節(jié)、周三的12節(jié)、周五的12節(jié),第一位數(shù)字代表周幾,第二位數(shù)字代表課程,如1代表12節(jié),3代表34節(jié),依次類(lèi)推。因此,為了達(dá)到預(yù)期的上課效果,也要對(duì)時(shí)間組合模式進(jìn)行分級(jí)。如表4所示。
從表4可以看出,優(yōu)先級(jí)為3的上課效果要比優(yōu)先級(jí)為1的好很多,同理,可以做出實(shí)踐課、體育課的周學(xué)時(shí)優(yōu)先級(jí)表。對(duì)于每種優(yōu)先級(jí)的周學(xué)時(shí)數(shù),可以把合理的時(shí)間組合模式放在優(yōu)先級(jí)列表中,這樣在處理課程時(shí),就可以用優(yōu)先級(jí)列表來(lái)匹配。這樣就可以滿足第6, 7, 8, 9等4條“軟”規(guī)則。
表1 教室類(lèi)型
表2 課程類(lèi)別分類(lèi)
表3 課程類(lèi)型分類(lèi)
表4 周學(xué)時(shí)優(yōu)先級(jí)
最后來(lái)定義4張矩陣表,老師矩陣表Tn[i,j]、課程矩陣表Ln[i,j]、班級(jí)矩陣表Cn[i,j]、教室矩陣表Rn[i,j],其中i表示一學(xué)期總的教學(xué)周數(shù),比如通常一學(xué)期教學(xué)周共15周,i就是1—15。j表示1周的教學(xué)課時(shí)量,按照1周5天的教學(xué)計(jì)算,j的取值范圍是[1.3.5.7.9.11.13.15.17.19.……],其中,[1.3.5.7.9]代表第一天的1—2節(jié)、3—4節(jié)、5—6節(jié)、7—8節(jié)、9—10節(jié),同理[11.13.15.17.19]代表第二天的課時(shí)。最終,要把所有的課程都安排到老師、班級(jí)、教室矩陣表中,并且要使3張矩陣表匹配成功。
4個(gè)矩陣的值為正整數(shù),當(dāng)Tn[i,j],Cn[i,j],Rn[i,j]=1時(shí),表示在該時(shí)間段內(nèi),老師、班級(jí)、教室可用;Tn[i,j],Cn[i,j],Rn[i,j] =0,表示在該時(shí)間段內(nèi),老師、班級(jí)、教室不可用;只有當(dāng)Tn[i,j]&Cn[i,j]&Rn[i,j]=1時(shí),表示該時(shí)間段內(nèi),可以排課,同時(shí)更新Tn[i,j],Cn[i,j],Rn[i,j]的數(shù)值為0,這樣就滿足了A,B,C這3條排課的“硬”條件。
算法的第一步:計(jì)算課程優(yōu)先級(jí),優(yōu)先級(jí)公式為:P(x)=J(x)*K1+T(x)*N*K2+S(x)*K3,其中,J(x)表示課程類(lèi)型的優(yōu)先級(jí),如前所述,選修課的優(yōu)先級(jí)最低,板塊課的優(yōu)先級(jí)最高,T(x)表示課程的周學(xué)時(shí)優(yōu)先級(jí),參考周學(xué)時(shí)優(yōu)先級(jí)表,N表示該課程的教學(xué)總周數(shù),S(x)表示教學(xué)計(jì)劃中的上課人數(shù),K1,K2,K3是可以按照實(shí)際需要調(diào)整的參數(shù)。通過(guò)這個(gè)公式,可以看到,課程的類(lèi)型越高,總的學(xué)時(shí)越多,上課的學(xué)生越多。其P(x)值越大,對(duì)應(yīng)的優(yōu)先級(jí)也就越高;反之,P(x)值越小,其優(yōu)先級(jí)越低。優(yōu)先級(jí)越高的課程就先被調(diào)度,而優(yōu)先級(jí)低的課程就后被調(diào)度。
算法的第二步:根據(jù)第一步算出的課程優(yōu)先級(jí),找出最高的優(yōu)先級(jí)課程,根據(jù)課程起始周、學(xué)時(shí),初始化該課程的最大可安排時(shí)間矩陣表Ln[i,j]都為1,即所有時(shí)間都可以安排。
算法的第三步:根據(jù)教學(xué)計(jì)劃,確定所有上課的班級(jí),從而得到班級(jí)的時(shí)間矩陣表Cn[i,j],Cn存放的是班級(jí)已排時(shí)間表,然后并將其與課程時(shí)間矩陣對(duì)比,得到該課程不能安排的時(shí)間列表。
算法的第四步:根據(jù)教學(xué)任務(wù),找出上該課程的老師,查詢老師的時(shí)間矩陣表Tn[i,j],從而得到老師已排課時(shí)間列表,然后并將其與課程時(shí)間矩陣對(duì)比,將進(jìn)一步確認(rèn)課程不能安排的時(shí)間列表。
算法的第五步:在確定了上課時(shí)間、班級(jí)、教師后,根據(jù)教學(xué)計(jì)劃中的教室類(lèi)型,例如多媒體教室還是普通教室,找到該類(lèi)型教室的所有列表,然后計(jì)算列表中教室的優(yōu)先級(jí),計(jì)算公式如下:
教室優(yōu)先級(jí)=(教室座位數(shù)-上課人數(shù))×教室座位數(shù)。
從公式可以看出,優(yōu)先級(jí)越小則優(yōu)先級(jí)越高,優(yōu)先級(jí)為0,則教室座位數(shù)和上課人數(shù)相等。按照優(yōu)先級(jí)數(shù)值從小到大,生成教室矩陣時(shí)間表Rn[i,j],得到教室已排課時(shí)間列表,然后并將其與課程時(shí)間矩陣對(duì)比,最終確認(rèn)課程不能安排的時(shí)間列表。
算法的第六步:找到課程的可排時(shí)間后,根據(jù)周學(xué)時(shí)優(yōu)先級(jí)表,在表中匹配優(yōu)先級(jí)最高的上課時(shí)間。完成以上匹配后,就確定了課程的時(shí)間、教室、老師。
算法的第七步:更改老師時(shí)間矩陣表Tn[i,j]、班級(jí)時(shí)間矩陣表Cn[i,j],教室時(shí)間矩陣表Rn[i,j],同時(shí)記錄選課課號(hào),選課課號(hào)應(yīng)包含學(xué)年學(xué)期、老師、課程、教室信息,并將信息寫(xiě)入選課臨時(shí)表。
如果死鎖發(fā)生在處理過(guò)程中,則可以追溯沖突操作的最近操作,對(duì)它進(jìn)行重排,仍不能解決問(wèn)題,繼續(xù)向上排查,直到回溯第一步操作。最后將回溯不能解決的課程輸出到?jīng)_突列表中,改為手工調(diào)整。系統(tǒng)算法流程如圖1所示。
圖1 法流程圖
進(jìn)行排課算法測(cè)試時(shí),將本文排課算法和購(gòu)買(mǎi)的教務(wù)管理系統(tǒng)排課進(jìn)行對(duì)比,選取某高職院校2014—2015學(xué)年第一學(xué)期的排課數(shù)據(jù)進(jìn)行對(duì)比,對(duì)比數(shù)據(jù)如表5所示。
從表5的統(tǒng)計(jì)結(jié)果可以看出,采用本文算法排課后,沖突率降低8個(gè)百分點(diǎn),成功率上升12個(gè)百分點(diǎn),運(yùn)行時(shí)間縮短了61 min。
如圖2所示,橫坐標(biāo)表示可用時(shí)間點(diǎn)和課程數(shù)目的比值,當(dāng)比值為1時(shí),表明該課程只能有一個(gè)時(shí)間點(diǎn)安排,當(dāng)比值大于1時(shí),表明可用于安排課程的時(shí)間很寬裕,該數(shù)值反映了排課的靈活度。課表的整體優(yōu)化值通過(guò)縱坐標(biāo)顯示,其值越大說(shuō)明排課效果越好。
本節(jié)提出的基于等價(jià)分類(lèi)和優(yōu)先級(jí)模式的計(jì)算機(jī)排課算法,是根據(jù)目前高職院校教務(wù)管理的實(shí)際需求而設(shè)計(jì)的,該算法簡(jiǎn)化思想,降低程序設(shè)計(jì)的復(fù)雜性。只要設(shè)計(jì)好周學(xué)時(shí)優(yōu)先級(jí)表,并能較好地估算出課程優(yōu)先級(jí),便可以較好地完成整個(gè)排課過(guò)程。
表5 對(duì)比數(shù)據(jù)
圖2 算法對(duì)比性能圖
[1]李盤(pán)林,李立健.基于啟發(fā)性知識(shí)研究生院課表編排系統(tǒng)[J].計(jì)算機(jī)學(xué)報(bào),1992(11):876-880.
[2]TRIPATHY A. Computerised decision aid for timetabling-a case analysis[J].Discrete Applied Mathematics, 1992(3): 313-323.
[3]FERLAND J A, FLEURENT C. SAPHIR: A decision sup-port system for course scheduling [J].Interfaces, 1994(2): 105-115.
[4]MONFROGIO A.Timetabling through constrained heuristic search and genetic algorithms[J].Software Practice and Experience, 1996 (3): 251-279.
[5]MERLIN A, SANDRIN P. A new method for unit commitment with ramping constraints [J]. Power Systems, 1983(5): 1218-1225.
[6]TRIPATHY A.School timetabling-a case in large binary integer linear programming[J].Discrete Applied Math Ematics, 1984(3): 313-323.
[7]EVEN S,ITAI A,SHAMIR A.On the complexity of timetable and multi-commodity flow problems [J].SIAM Journal on Compu-ting, 1976(5): 691-703.
[8]HOCHBAUM D. Approximation Algorithms for NP-hard Problems[M].Berkeley: PWS Publishing Company, 1997.
江蘇高校哲社研究立項(xiàng)課題;項(xiàng)目名稱:大數(shù)據(jù)背景下職業(yè)院校教師的挑戰(zhàn)與發(fā)展研究;項(xiàng)目編號(hào):2016SJB880057。
楊明(1978— ),男,江蘇徐州,碩士,工程師;研究方向:數(shù)據(jù)庫(kù)應(yīng)用,軟件工程。