基于優先級鏈表結構的大學排課算法設計與實現＊

蒙煥念，黃良永

（柳州師范高等專科學校 教務處，廣西 柳州 545004）

大學課程表問題是一種時間表問題TTP（Time-TableProblem）， 是公認的一種 NP （Non deterministic Polynomial）困難問題[1]。幾十年來，人們對計算機排課方法做了很多嘗試，但實現的效果并不是很理想[2]。研究表明，解決大規模的課表編排問題僅靠數學方法是行不通的[3]。排課問題是一個多目標條件組合的優化選擇問題，需要實現課程、學生、老師、上課時間和地點的優化組合，加上大學排課約束因素的多樣性，如教師的特殊要求、課程的特殊要求和學生的特殊要求等，致使排課工作復雜而繁重。

目前，用于解決課程表問題的算法很多，但各種算法同時也存在自身的不足。如遺傳算法復雜，實現難度大；蟻群算法計算時間長，容易出現停滯現象；模擬退火算法控制參數選擇困難，易發生算法迭代不收斂的情況[4]。通過對多種算法的優劣性分析，本文基于貪心算法的思想，以特定的優先級鏈表為主要數據結構，提出并實現了一種改進的排課算法。

1 解決問題的策略

貪心算法也稱為“貪心策略”，它對解空間進行搜索時，不是從整體上考慮最優，其所做出的選擇只是在某種意義上的局部最優解。換句話說，貪心算法進行的每一次貪心選擇，都是對當前條件做出的最佳選擇。雖然這種局部最優選擇并不總能獲得整體的最優解，但是通常能獲得近似的最優解。由于算法考慮的信息量較小，一旦選擇后就不需再改變（不回溯），所以算法效率比較高。

由于大學課程的專業性強，科目多，通常情況下，課程的開課班級和任課老師只能通過人工指定。所以在大學課程表問題中，計算機排課要處理的關鍵問題就是安排課程的上課時間和教室，實現上課時間和教室的沖突檢測和智能選擇。因此，本設計的排課采取的貪心策略為：先為所有的課程、上課時間和教室指定排課優先級[5]，然后從優先級最高的課程開始排課，在當前的條件約束下，選擇符合條件的、優先級最高的上課時間和教室。

2 數據結構與算法實現

2.1 數據結構

2.1.1 待排課程信息（Course）

一般來說，可以從各專業的教學計劃自動生成原始課程信息，然后人工進行合班、指定任課教師，就可以得到待排課程信息，其數據結構可定義如下：

課程的排課優先級可根據學校的具體情況調整，優先級權值大的課程優先排課。優先級權值由4項數據決定，每一項數據權值系數可能取值為 0～9，總權值表達式為：課程性質權值系數×103＋教室類型權值系數×102＋人數容量權值系數×10＋學分權值系數。我校的課程性質和教室類型優先級權值系數設置如表1、表2所示，人數容量系數=人數/40取整，如果人數大于360，則系數取最高權值9；學分權值系數用課程本學期學分直接表示（本學期學分不能大于9）。這樣的優先級設計保證了公共必修課必須先排課，然后優先考慮緊缺教室類型的安排和大班教學排課的情況，如果以上三個條件計算出多個課程的優先級權值都一樣，則由課程的學分決定最終的課程優先級。

表1 課程性質權值設置表

表2 教室類型權值設置表

2.1.2 課程的上課班級（ClassInCourse）

該數據是對待排課程進行合班操作后生成的附屬數據，用于指明一個課程的上課學生班級。把該數據與待排課程信息（Course）分開是考慮到當一個課程對應多個上課班級時，使關系數據仍能滿足第三范式約束。ClassInCourse數據結構定義如下：

2.1.3 上課時間（ClassTime）

為了獲得時間遍歷的高效性，可對時間編碼進行技巧性設計。若每天有 5個上課時段，可用“10”表示“星期一第一大節（1、2 節）”、“11”表示“星期一第二大節（3、4 節）”、“13”表示星期一第三大節（5、6 節），如此類推到其他時段。這樣，一周共35個時段，可定義數組a[45]、a[i]表示一個上課時段，則遍歷一周的時間只需要一個循環：

數組之所以不使用 a[1]～a[9]，是因為 1～9不好作相似運算（相似運算不能區分1和11）。對于各時間段的排課優先級，通常設上午時段和下午5、6節的優先級最高，下午 7、8節次之，最后是晚上，星期六和星期天不能排課，IsUsed設為False。為了保證上課時間均勻分布，本設計用UsedTimes記錄各時段被使用的次數 （初始為零，每使用一次即加1），對于優先級相同的時間段，按時間使用次數升序排列。排課選擇時間時，優先選擇使用次數少的時間。這樣，通常只需檢測序列前面的幾個時間段，就可以命中合適的時間對象，大大提高了選擇時間的命中率。

2.1.4 排課地點（ClassRoom）

排課地點數據結構定義如下：

開花后12～15天，豆莢色綠柔軟，尚未木質化，是采收嫩莢的適宜時期。此時生長迅速、纖維少，切忌采摘過遲，造成纖維增加，莢壁粗硬，品質變劣，不能食用。一般3～5天采收1次。開花至結莢40～50天，豆莢變褐色，基本干枯，應及時采摘老莢。采收過遲，則豆莢自然開裂。采后攤曬脫粒，晾干貯藏。

為了避免出現大教室被小教學班占用的資源浪費現象，設計時按教室容量和教室類型分段劃分教室的使用優先級，如表3所示。

表3 教室使用優先級安排表

與時間一樣，設計時記錄了每一個教室的使用次數（UsedTimes），在教室的優先級相同時，優先選擇使用次數少的教室，從而使教室資源得到有效利用，同時也大大提高了選擇教室的命中率。

2.1.5 排課條件約束（Constraints）

排課條件約束是自動排課非常關鍵的數據結構，因為條件約束很大程度上決定了自動排課的成敗和課表的科學合理性。常見的個性化排課約束條件有：（1）某個老師特定時間（或地點）排課/不排課；（2）某個課程特定時間（或地點）排課/不排課；（3）某個班級特定時間（或地點）排課/不排課；（4）課程的多個上課時間應有合理的時間間隔（1天以上），而上課地點應盡可能相同。

可以看出，條件約束基本可以分為對課程、教師和學生的三種約束類型，約束項目主要有上課時間和上課教室（或教室類型），其取值格式如表4所示。

表4 排課約束格式

表4中，設“大學英語”、“李四”和“數學 101班”分別是約束類型課程表、教師表和學生（班級）表中的唯一主鍵值，約束對象必須是約束類型表（待排課程信息，教師表和學生表）的一個主鍵值。為了簡化程序，邏輯符號只有等于和不等于兩種取值。表中第一行的含義為：安排課程“大學英語”時，上課時間不能選擇“10（星期一第一大節）”。

除了以上自定義的約束外，排課還應該遵循一些基本的常理性約束，如：（1）每個學生在同一時間只能上一門課；（2）每個教室同一時間只能上一門課程；（3）每個教師在同一時間只能在一個地點上課；（4）每個課程任務同一時間只能在一個地點上課；（5）每門課程安排的課時應等于計劃的總課時等。

課程安排表數據結構定義如下：

2.2 算法描述

根據以上的數據結構來實現排課的貪心算法。算法步驟描述如下：

（1）初始化。按優先級從高到低生成待排課程鏈表（*Course）、 時 間 鏈 表 （*ClassTime）和 教 室 鏈 表（*ClassRoom）；新建課程安排空鏈表（*TimeTable）。

（2）遍歷課程鏈表。對應遍歷的每一個課程，做以下3個操作：①為當前課程選擇符合條件的、優先級最高且使用次數最少的上課時間 （無論是否找到合適的時間，限定每個課程對時間鏈表的匹配次數不超過10次）。如果找到符合條件的課程，則把課程和時間加入TimeTable中，時間段使用次數加1；否則，說明該課程無法安排，跳轉到下一門課程，重新執行3個操作；②對當前課程排定的時間，選擇符合條件的、優先級最高且使用次數最少的教室（無論是否找到合適的教室，限定每個課程對教室鏈表的匹配次數不超過10次）。如果找到符合條件的教室，則把教室派給當前課程，教室使用次數加1；否則，說明該課程沒有教室可排，跳轉到下一門課程，重新執行3個操作；③如果當前課程已排時間節次小于課程的周課時，時間指針跳轉到下一天時間段（保證同一門課上課時間間隔一天以上），繼續對當前課程執行3個操作；否則，說明該課程已經安排完畢，調整時間和教室鏈表排序，跳轉到下一門課程 （Course=Course->Next），重新執行 3個操作。

（3）課程鏈表遍歷完成，返回 *TimeTable，算法結束。

3 算法復雜度分析及使用效果

3.1 復雜度分析

本算法為每個課程的上課時間和教室進行了貪心選擇，核心是使用了三層循環嵌套。通常情況下，三層循環嵌套算法的時間復雜度為O（n3）。由于算法根據預先設定的優先級規則生成時間鏈表、教室鏈表，對時間和教室采取先排序，后選擇的貪心策略，使算法總能在鏈表序列前部命中對象，保證循環每次命中目標所遍歷鏈表節點的個數不大于10（如果超過10次未命中則跳出循環）。因此，算法的時間復雜度接近O（n）。

3.2 使用效果

本算法在安排課程的上課時間和教室時，總是選擇優先級高且利用率低的時間和教室對象，保證了資源利用的均衡化。但如果學校的資源確實緊缺或排課約束條件苛刻，則必須調整時間和教室的優先級規則，更改排課約束條件，再進行排課。如仍找不到合適的時間和教室排課，則需要人工調整排課。

本文使用Visual C++6.0和SQL Server2000實現本算法，對我校42個課程、12個班級、36個教室進行排課，每周排課總次數為 142，在 P4雙核 2.8、內存 1 GB的機器上運行，所有課程都成功排課，共耗時3.505 s。此外，還對我校2010～2011年第二學年的1056個課程、130個班級、305個教室級進行完全編排，整個過程耗時60.121 s，比我校正在使用的某公司教務管理系統的排課耗時少了15.826 s。實踐證明，本文排課算法能夠較好地解決大學排課問題，是一個實用而高效的排課算法。

[1]熊焱，王莉，李大衛，等.大學課程表問題的模型與算法[J].鞍山科技大學學報，2005，28（1）：26-29.

[2]高喜瑪，張萍.大學自動排課系統內核算法設計[J].南陽師范學院學報（自然科學版），2003，2（12）：55-58.

[3]潘以鋒.高校智能排課系統的算法[J].上海師范大學學報（自然科學版），2006，35（5）：31-37.

[4]張晶，李廣軍，徐娟.智能排課算法綜述[J].西南民族大學學報（自然科學版），2009，35（3）：675-678.

[5]馮思玲，李艷梅，梁瑜.基于分治和貪心相結合的排課算法研究[J].現代計算機（專業版），2009（3）：11-13.