楊 明

（南京鐵道職業(yè)技術(shù)學(xué)院，江蘇 南京 210031）

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

楊 明

（南京鐵道職業(yè)技術(shù)學(xué)院，江蘇 南京 210031）

文章分析了國內(nèi)外對于排課算法的研究現(xiàn)狀，提出了基于等價分類的優(yōu)先級排課算法的思想，包含確定算法的基本原則、算法的等價分類和優(yōu)先級的確定，最后給出了算法的流程圖和相關(guān)測試數(shù)據(jù)。

教務(wù)系統(tǒng)；算法；優(yōu)先級

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

對于課表的研究，國外最早于20世紀(jì)50年代出現(xiàn)。直到1962年，戈特利布最早提出了一個數(shù)學(xué)模型，用于求解課表問題。此后大家對此問題進行了深入的討論和廣泛的研究，如印度Vastapur大學(xué)的Arabinda Tripathy和加拿大Montreal大學(xué)的Jean Aubin等。Tripathy，他的主要工作是以“人”為單位進行排課，利用拉格朗日松弛法來解決，這種方法雖然可以減少變量的個數(shù)，但是人為造成課程間的沖突。其他有代表性的算法有遺傳算法、螞蟻算法等，通過實踐表明，單純的運用數(shù)據(jù)方法去解決人為因素過多的課表問題，不是切實可行的辦法。

直到1976年，Even等人證明了此問題本質(zhì)上就是一個NP完全問題。因為對于排課的約束條件太多，而一時也無法找到所有的約束條件，隨著排課時間段和學(xué)生人數(shù)、課程數(shù)的不斷增加，排列組合方案會成幾何數(shù)增長，進而在尋求最優(yōu)解的過程中，系統(tǒng)會消耗大量的時間和資源，最后到了讓人無法忍受的程度，從而導(dǎo)致系統(tǒng)無法使用。

國內(nèi)對排課的研究始于20世紀(jì)80年代初，林漳希、林堯瑞教授于1984年宣布了此課題研究成果，成為國內(nèi)研究的基礎(chǔ)。已經(jīng)成型的成果有東南大學(xué)的UTSS系統(tǒng)，大連理工的智能教學(xué)組織管理調(diào)度系統(tǒng)3.0等。這些已經(jīng)成熟的系統(tǒng)應(yīng)用到實際工作中后，的確可以減輕排課人員的工作負(fù)擔(dān)。但是這些排課系統(tǒng)大多是模擬人工排課，以班級作為排課的基本單元，在排課時依賴具體的教學(xué)體制和教學(xué)模式，不適合廣泛推廣。

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

排課，是一項非常復(fù)雜的腦力勞動，它需要在一定的時間、空間內(nèi)，在有限的資源供給條件下，實現(xiàn)課表的最優(yōu)解。排出的課表既要滿足課程教學(xué)的硬性要求，又要滿足老師、學(xué)生的軟性要求，由于突發(fā)因素太多，每個學(xué)校情況又不同，因此找到最優(yōu)課表的概率幾乎為零。

本節(jié)使用基于分類思想的優(yōu)先級算法，放棄尋找最優(yōu)解的過程，而是在給定資源的情況下，滿足必備條件，適當(dāng)滿足選擇條件，產(chǎn)生基礎(chǔ)課表，然后在這基礎(chǔ)課表上對其優(yōu)化，從而產(chǎn)生滿足實際需求的可行性課表。這種算法求解的過程，易于程序?qū)崿F(xiàn)，維護簡單，效率較高又能兼顧實際需要，是切實可行的解決方案。

3 排課算法基本原則

課表的編排本質(zhì)上就是老師、班級、課程、時間、地點的5種資源的排列組合問題，在對這5種資源進行合理配置的時候，最基本的一個原則就是避免沖突，即任何兩種資源不能出現(xiàn)互相沖突，例如在同一時間，給一個老師安排了兩門課程。

除了這個基本原則之外，根據(jù)教學(xué)規(guī)律和課程特點，排課要遵循一定的基本規(guī)則，按照基本規(guī)則排課，不但能減少沖突的發(fā)生，而且課表的實用性會更強，這些基本規(guī)則應(yīng)包含：（1）同一時間內(nèi)，同一個班級只能安排一門課程；（2）同一時間內(nèi)，同一個老師只能安排一門課程；（3）同一時間內(nèi)，同一個教室只能安排一門課程；（4）教室的座位數(shù)應(yīng)大于上課總?cè)藬?shù)；（5）上課教室類型要滿足課程需要，例如不能給需要多媒體教室的課程安排一個普通教室。以上5個規(guī)則，被稱為“硬”規(guī)則，所謂的“硬”規(guī)則，就是說必須要滿足的規(guī)則，如果不能滿足，則教學(xué)活動無法進行。

除了“硬”規(guī)則，根據(jù)教學(xué)規(guī)律和人體生物鐘，排課還必須滿足如下“軟”規(guī)則：

（1）對于同一個班級，同一門課程，一天的課時量最多2節(jié)；（2）理論課程盡量安排上午授課；（3）實踐課程盡量安排在下午授課；（4）必修課程應(yīng)放到體育課程前面安排，體育課應(yīng)盡量安排在第3，4節(jié)或第5，6節(jié)。以上4個規(guī)則，被稱為“軟”規(guī)則，所謂的“軟”規(guī)則，就是可以使教學(xué)活動安排得更加合理有序。排課算法應(yīng)該優(yōu)先滿足“硬”規(guī)則，然后盡量滿足“軟”規(guī)則。

4 算法的等價分類

在設(shè)計算法時，為了實現(xiàn)上述規(guī)則并有效地降低算法的難度，主要采用了基于優(yōu)先級的等價分類算法。為了實現(xiàn)規(guī)則4和規(guī)則5的要求，把教室進行分類，按照其類型分為普通教室、多媒體教室和實訓(xùn)室，如表1所示。

然后，再根據(jù)教室的座位數(shù)，對每個類進行進一步細(xì)分：如45人以下為一類，90人以下為一類等若干種。教室分類完成后，再進行課程類別分類，分為理論課、實踐課、體育課程，體育課可以算做實踐課程，但是由于排課功能的需要，所以單獨劃分，各個學(xué)?？梢愿鶕?jù)實際情況做出調(diào)整，如表2所示。

課程類別分類完成后，進行課程類型優(yōu)先級分配，課程類型分為選修課、必修課、板塊課程。優(yōu)先級依次從低到高，在高職院校中，板塊課程基本上都是屬于必修課程的范圍。在同一板塊內(nèi)上課的班級，一般是上課地點不同，但是上課時間都保持一致，例如大學(xué)英語、體育課。具體分類如表3所示。

課程類型完成后，進行周學(xué)時優(yōu)先級設(shè)置。排課人員根據(jù)其以往的工作經(jīng)驗來設(shè)置該優(yōu)先級，優(yōu)先級的本質(zhì)就是一系列上課的組合方式。比如一門課程的周學(xué)時是6，最佳的上課方式可能是：“13”“31”“51”；表示該課程一周上3次課，分別為周一的34節(jié)、周三的12節(jié)、周五的12節(jié)，第一位數(shù)字代表周幾，第二位數(shù)字代表課程，如1代表12節(jié)，3代表34節(jié)，依次類推。因此，為了達到預(yù)期的上課效果，也要對時間組合模式進行分級。如表4所示。

從表4可以看出，優(yōu)先級為3的上課效果要比優(yōu)先級為1的好很多，同理，可以做出實踐課、體育課的周學(xué)時優(yōu)先級表。對于每種優(yōu)先級的周學(xué)時數(shù)，可以把合理的時間組合模式放在優(yōu)先級列表中，這樣在處理課程時，就可以用優(yōu)先級列表來匹配。這樣就可以滿足第6, 7, 8, 9等4條“軟”規(guī)則。

表1 教室類型

表2 課程類別分類

表3 課程類型分類

表4 周學(xué)時優(yōu)先級

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

最后來定義4張矩陣表，老師矩陣表Tn[i，j]、課程矩陣表Ln[i，j]、班級矩陣表Cn[i，j]、教室矩陣表Rn[i，j]，其中i表示一學(xué)期總的教學(xué)周數(shù)，比如通常一學(xué)期教學(xué)周共15周，i就是1—15。j表示1周的教學(xué)課時量，按照1周5天的教學(xué)計算，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]代表第二天的課時。最終，要把所有的課程都安排到老師、班級、教室矩陣表中，并且要使3張矩陣表匹配成功。

4個矩陣的值為正整數(shù)，當(dāng)Tn[i，j]，Cn[i，j]，Rn[i，j]=1時，表示在該時間段內(nèi)，老師、班級、教室可用；Tn[i，j]，Cn[i，j]，Rn[i，j] =0，表示在該時間段內(nèi)，老師、班級、教室不可用；只有當(dāng)Tn[i，j]&Cn[i，j]&Rn[i，j]=1時，表示該時間段內(nèi)，可以排課，同時更新Tn[i，j]，Cn[i，j]，Rn[i，j]的數(shù)值為0，這樣就滿足了A，B，C這3條排課的“硬”條件。

6 排課算法步驟

算法的第一步：計算課程優(yōu)先級，優(yōu)先級公式為：P(x)=J(x)*K1+T(x)*N*K2+S(x)*K3，其中，J(x)表示課程類型的優(yōu)先級，如前所述，選修課的優(yōu)先級最低，板塊課的優(yōu)先級最高，T(x)表示課程的周學(xué)時優(yōu)先級，參考周學(xué)時優(yōu)先級表，N表示該課程的教學(xué)總周數(shù)，S(x)表示教學(xué)計劃中的上課人數(shù)，K1，K2，K3是可以按照實際需要調(diào)整的參數(shù)。通過這個公式，可以看到，課程的類型越高，總的學(xué)時越多，上課的學(xué)生越多。其P(x)值越大，對應(yīng)的優(yōu)先級也就越高；反之，P(x)值越小，其優(yōu)先級越低。優(yōu)先級越高的課程就先被調(diào)度，而優(yōu)先級低的課程就后被調(diào)度。

算法的第二步：根據(jù)第一步算出的課程優(yōu)先級，找出最高的優(yōu)先級課程，根據(jù)課程起始周、學(xué)時，初始化該課程的最大可安排時間矩陣表Ln[i，j]都為1，即所有時間都可以安排。

算法的第三步：根據(jù)教學(xué)計劃，確定所有上課的班級，從而得到班級的時間矩陣表Cn[i，j]，Cn存放的是班級已排時間表，然后并將其與課程時間矩陣對比，得到該課程不能安排的時間列表。

算法的第四步：根據(jù)教學(xué)任務(wù)，找出上該課程的老師，查詢老師的時間矩陣表Tn[i，j]，從而得到老師已排課時間列表，然后并將其與課程時間矩陣對比，將進一步確認(rèn)課程不能安排的時間列表。

算法的第五步：在確定了上課時間、班級、教師后，根據(jù)教學(xué)計劃中的教室類型，例如多媒體教室還是普通教室，找到該類型教室的所有列表，然后計算列表中教室的優(yōu)先級，計算公式如下：

教室優(yōu)先級=（教室座位數(shù)－上課人數(shù)）×教室座位數(shù)。

從公式可以看出，優(yōu)先級越小則優(yōu)先級越高，優(yōu)先級為0，則教室座位數(shù)和上課人數(shù)相等。按照優(yōu)先級數(shù)值從小到大，生成教室矩陣時間表Rn[i，j]，得到教室已排課時間列表，然后并將其與課程時間矩陣對比，最終確認(rèn)課程不能安排的時間列表。

算法的第六步：找到課程的可排時間后，根據(jù)周學(xué)時優(yōu)先級表，在表中匹配優(yōu)先級最高的上課時間。完成以上匹配后，就確定了課程的時間、教室、老師。

算法的第七步：更改老師時間矩陣表Tn[i，j]、班級時間矩陣表Cn[i，j]，教室時間矩陣表Rn[i，j]，同時記錄選課課號，選課課號應(yīng)包含學(xué)年學(xué)期、老師、課程、教室信息，并將信息寫入選課臨時表。

如果死鎖發(fā)生在處理過程中，則可以追溯沖突操作的最近操作，對它進行重排，仍不能解決問題，繼續(xù)向上排查，直到回溯第一步操作。最后將回溯不能解決的課程輸出到?jīng)_突列表中，改為手工調(diào)整。系統(tǒng)算法流程如圖1所示。

圖1 法流程圖

7 排課算法測試

進行排課算法測試時，將本文排課算法和購買的教務(wù)管理系統(tǒng)排課進行對比，選取某高職院校2014—2015學(xué)年第一學(xué)期的排課數(shù)據(jù)進行對比，對比數(shù)據(jù)如表5所示。

從表5的統(tǒng)計結(jié)果可以看出，采用本文算法排課后，沖突率降低8個百分點，成功率上升12個百分點，運行時間縮短了61 min。

如圖2所示，橫坐標(biāo)表示可用時間點和課程數(shù)目的比值，當(dāng)比值為1時，表明該課程只能有一個時間點安排，當(dāng)比值大于1時，表明可用于安排課程的時間很寬裕，該數(shù)值反映了排課的靈活度。課表的整體優(yōu)化值通過縱坐標(biāo)顯示，其值越大說明排課效果越好。

8 結(jié)語

本節(jié)提出的基于等價分類和優(yōu)先級模式的計算機排課算法，是根據(jù)目前高職院校教務(wù)管理的實際需求而設(shè)計的，該算法簡化思想，降低程序設(shè)計的復(fù)雜性。只要設(shè)計好周學(xué)時優(yōu)先級表，并能較好地估算出課程優(yōu)先級，便可以較好地完成整個排課過程。

表5 對比數(shù)據(jù)

圖2 算法對比性能圖

[1]李盤林，李立健.基于啟發(fā)性知識研究生院課表編排系統(tǒng)[J].計算機學(xué)報，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.

江蘇高校哲社研究立項課題；項目名稱：大數(shù)據(jù)背景下職業(yè)院校教師的挑戰(zhàn)與發(fā)展研究；項目編號：2016SJB880057。

楊明（1978— ），男，江蘇徐州，碩士，工程師；研究方向：數(shù)據(jù)庫應(yīng)用，軟件工程。