基于優(yōu)先級(jí)分類(lèi)的排課算法設(shè)計(jì)

楊 明

（南京鐵道職業(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í)

1 目前排課算法現(xiàn)狀

對(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é)模式，不適合廣泛推廣。

2 排課算法指導(dǎo)思想

排課，是一項(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í)可行的解決方案。

3 排課算法基本原則

課表的編排本質(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ī)則。

4 算法的等價(jià)分類(lèi)

在設(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í)

5 算法的矩陣設(shè)置

最后來(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條排課的“硬”條件。

6 排課算法步驟

算法的第一步：計(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 法流程圖

7 排課算法測(cè)試

進(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ō)明排課效果越好。

8 結(jié)語(yǔ)

本節(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)用，軟件工程。