基于優先級分類的排課算法設計

楊 明

（南京鐵道職業技術學院，江蘇 南京 210031）

基于優先級分類的排課算法設計

楊 明

（南京鐵道職業技術學院，江蘇 南京 210031）

文章分析了國內外對于排課算法的研究現狀，提出了基于等價分類的優先級排課算法的思想，包含確定算法的基本原則、算法的等價分類和優先級的確定，最后給出了算法的流程圖和相關測試數據。

教務系統；算法；優先級

1 目前排課算法現狀

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

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

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

2 排課算法指導思想

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

本節使用基于分類思想的優先級算法，放棄尋找最優解的過程，而是在給定資源的情況下，滿足必備條件，適當滿足選擇條件，產生基礎課表，然后在這基礎課表上對其優化，從而產生滿足實際需求的可行性課表。這種算法求解的過程，易于程序實現，維護簡單，效率較高又能兼顧實際需要，是切實可行的解決方案。

3 排課算法基本原則

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

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

除了“硬”規則，根據教學規律和人體生物鐘，排課還必須滿足如下“軟”規則：

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

4 算法的等價分類

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

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

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

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

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

表1 教室類型

表2 課程類別分類

表3 課程類型分類

表4 周學時優先級

5 算法的矩陣設置

最后來定義4張矩陣表，老師矩陣表Tn[i，j]、課程矩陣表Ln[i，j]、班級矩陣表Cn[i，j]、教室矩陣表Rn[i，j]，其中i表示一學期總的教學周數，比如通常一學期教學周共15周，i就是1—15。j表示1周的教學課時量，按照1周5天的教學計算，j的取值范圍是[1.3.5.7.9.11.13.15.17.19.……]，其中，[1.3.5.7.9]代表第一天的1—2節、3—4節、5—6節、7—8節、9—10節，同理[11.13.15.17.19]代表第二天的課時。最終，要把所有的課程都安排到老師、班級、教室矩陣表中，并且要使3張矩陣表匹配成功。

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

6 排課算法步驟

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

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

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

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

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

教室優先級=（教室座位數－上課人數）×教室座位數。

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

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

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

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

圖1 法流程圖

7 排課算法測試

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

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

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

8 結語

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

表5 對比數據

圖2 算法對比性能圖

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

江蘇高校哲社研究立項課題；項目名稱：大數據背景下職業院校教師的挑戰與發展研究；項目編號：2016SJB880057。

楊明（1978— ），男，江蘇徐州，碩士，工程師；研究方向：數據庫應用，軟件工程。