蒙煥念，黃良永

（柳州師范高等?？茖W(xué)校 教務(wù)處，廣西 柳州 545004）

大學(xué)課程表問(wèn)題是一種時(shí)間表問(wèn)題TTP（Time-TableProblem）， 是公認(rèn)的一種 NP （Non deterministic Polynomial）困難問(wèn)題[1]。幾十年來(lái)，人們對(duì)計(jì)算機(jī)排課方法做了很多嘗試，但實(shí)現(xiàn)的效果并不是很理想[2]。研究表明，解決大規(guī)模的課表編排問(wèn)題僅靠數(shù)學(xué)方法是行不通的[3]。排課問(wèn)題是一個(gè)多目標(biāo)條件組合的優(yōu)化選擇問(wèn)題，需要實(shí)現(xiàn)課程、學(xué)生、老師、上課時(shí)間和地點(diǎn)的優(yōu)化組合，加上大學(xué)排課約束因素的多樣性，如教師的特殊要求、課程的特殊要求和學(xué)生的特殊要求等，致使排課工作復(fù)雜而繁重。

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

1 解決問(wèn)題的策略

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

由于大學(xué)課程的專業(yè)性強(qiáng)，科目多，通常情況下，課程的開(kāi)課班級(jí)和任課老師只能通過(guò)人工指定。所以在大學(xué)課程表問(wèn)題中，計(jì)算機(jī)排課要處理的關(guān)鍵問(wèn)題就是安排課程的上課時(shí)間和教室，實(shí)現(xiàn)上課時(shí)間和教室的沖突檢測(cè)和智能選擇。因此，本設(shè)計(jì)的排課采取的貪心策略為：先為所有的課程、上課時(shí)間和教室指定排課優(yōu)先級(jí)[5]，然后從優(yōu)先級(jí)最高的課程開(kāi)始排課，在當(dāng)前的條件約束下，選擇符合條件的、優(yōu)先級(jí)最高的上課時(shí)間和教室。

2 數(shù)據(jù)結(jié)構(gòu)與算法實(shí)現(xiàn)

2.1 數(shù)據(jù)結(jié)構(gòu)

2.1.1 待排課程信息（Course）

一般來(lái)說(shuō)，可以從各專業(yè)的教學(xué)計(jì)劃自動(dòng)生成原始課程信息，然后人工進(jìn)行合班、指定任課教師，就可以得到待排課程信息，其數(shù)據(jù)結(jié)構(gòu)可定義如下：

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

表1 課程性質(zhì)權(quán)值設(shè)置表

表2 教室類型權(quán)值設(shè)置表

2.1.2 課程的上課班級(jí)（ClassInCourse）

該數(shù)據(jù)是對(duì)待排課程進(jìn)行合班操作后生成的附屬數(shù)據(jù)，用于指明一個(gè)課程的上課學(xué)生班級(jí)。把該數(shù)據(jù)與待排課程信息（Course）分開(kāi)是考慮到當(dāng)一個(gè)課程對(duì)應(yīng)多個(gè)上課班級(jí)時(shí)，使關(guān)系數(shù)據(jù)仍能滿足第三范式約束。ClassInCourse數(shù)據(jù)結(jié)構(gòu)定義如下：

2.1.3 上課時(shí)間（ClassTime）

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

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

2.1.4 排課地點(diǎn)（ClassRoom）

排課地點(diǎn)數(shù)據(jù)結(jié)構(gòu)定義如下：

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

為了避免出現(xiàn)大教室被小教學(xué)班占用的資源浪費(fèi)現(xiàn)象，設(shè)計(jì)時(shí)按教室容量和教室類型分段劃分教室的使用優(yōu)先級(jí)，如表3所示。

表3 教室使用優(yōu)先級(jí)安排表

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

2.1.5 排課條件約束（Constraints）

排課條件約束是自動(dòng)排課非常關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)，因?yàn)闂l件約束很大程度上決定了自動(dòng)排課的成敗和課表的科學(xué)合理性。常見(jiàn)的個(gè)性化排課約束條件有：（1）某個(gè)老師特定時(shí)間（或地點(diǎn)）排課/不排課；（2）某個(gè)課程特定時(shí)間（或地點(diǎn)）排課/不排課；（3）某個(gè)班級(jí)特定時(shí)間（或地點(diǎn)）排課/不排課；（4）課程的多個(gè)上課時(shí)間應(yīng)有合理的時(shí)間間隔（1天以上），而上課地點(diǎn)應(yīng)盡可能相同。

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

表4 排課約束格式

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

除了以上自定義的約束外，排課還應(yīng)該遵循一些基本的常理性約束，如：（1）每個(gè)學(xué)生在同一時(shí)間只能上一門(mén)課；（2）每個(gè)教室同一時(shí)間只能上一門(mén)課程；（3）每個(gè)教師在同一時(shí)間只能在一個(gè)地點(diǎn)上課；（4）每個(gè)課程任務(wù)同一時(shí)間只能在一個(gè)地點(diǎn)上課；（5）每門(mén)課程安排的課時(shí)應(yīng)等于計(jì)劃的總課時(shí)等。

課程安排表數(shù)據(jù)結(jié)構(gòu)定義如下：

2.2 算法描述

根據(jù)以上的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)排課的貪心算法。算法步驟描述如下：

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

（2）遍歷課程鏈表。對(duì)應(yīng)遍歷的每一個(gè)課程，做以下3個(gè)操作：①為當(dāng)前課程選擇符合條件的、優(yōu)先級(jí)最高且使用次數(shù)最少的上課時(shí)間 （無(wú)論是否找到合適的時(shí)間，限定每個(gè)課程對(duì)時(shí)間鏈表的匹配次數(shù)不超過(guò)10次）。如果找到符合條件的課程，則把課程和時(shí)間加入TimeTable中，時(shí)間段使用次數(shù)加1；否則，說(shuō)明該課程無(wú)法安排，跳轉(zhuǎn)到下一門(mén)課程，重新執(zhí)行3個(gè)操作；②對(duì)當(dāng)前課程排定的時(shí)間，選擇符合條件的、優(yōu)先級(jí)最高且使用次數(shù)最少的教室（無(wú)論是否找到合適的教室，限定每個(gè)課程對(duì)教室鏈表的匹配次數(shù)不超過(guò)10次）。如果找到符合條件的教室，則把教室派給當(dāng)前課程，教室使用次數(shù)加1；否則，說(shuō)明該課程沒(méi)有教室可排，跳轉(zhuǎn)到下一門(mén)課程，重新執(zhí)行3個(gè)操作；③如果當(dāng)前課程已排時(shí)間節(jié)次小于課程的周課時(shí)，時(shí)間指針跳轉(zhuǎn)到下一天時(shí)間段（保證同一門(mén)課上課時(shí)間間隔一天以上），繼續(xù)對(duì)當(dāng)前課程執(zhí)行3個(gè)操作；否則，說(shuō)明該課程已經(jīng)安排完畢，調(diào)整時(shí)間和教室鏈表排序，跳轉(zhuǎn)到下一門(mén)課程 （Course=Course->Next），重新執(zhí)行 3個(gè)操作。

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

3 算法復(fù)雜度分析及使用效果

3.1 復(fù)雜度分析

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

3.2 使用效果

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

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

[1]熊焱，王莉，李大衛(wèi)，等.大學(xué)課程表問(wèn)題的模型與算法[J].鞍山科技大學(xué)學(xué)報(bào)，2005，28（1）：26-29.

[2]高喜瑪，張萍.大學(xué)自動(dòng)排課系統(tǒng)內(nèi)核算法設(shè)計(jì)[J].南陽(yáng)師范學(xué)院學(xué)報(bào)（自然科學(xué)版），2003，2（12）：55-58.

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

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

[5]馮思玲，李艷梅，梁瑜.基于分治和貪心相結(jié)合的排課算法研究[J].現(xiàn)代計(jì)算機(jī)（專業(yè)版），2009（3）：11-13.