面向高校統一教學資源排課問題的啟發式方法

張德珍，陳剛，王營，郭賽君，李永華

（1.大連海事大學信息科學技術學院，遼寧大連 116026；

2.大連海事大學研究生院，遼寧大連 116026；

3.大連拓撲偉業科技有限公司，遼寧大連 116600）

面向高校統一教學資源排課問題的啟發式方法

張德珍1，陳剛1，王營2，郭賽君1，李永華3

（1.大連海事大學信息科學技術學院，遼寧大連 116026；

2.大連海事大學研究生院，遼寧大連 116026；

3.大連拓撲偉業科技有限公司，遼寧大連 116600）

面向高校整體教學資源環境下的復雜多約束排課問題，提出了一種啟發式方法.基于實際教學過程中涉及學生、任課教師、上課教室，以及各自的可行時間段等教學資源下的復雜多約束條件建立了約束函數，構建了以學生每周上課節次的均勻度與教師對任課時間滿意度最大化為目標函數的優化模型.在求解過程中，將各約束條件轉化為關系代數的關系運算，在縮小解空間的基礎上進而采用啟發式策略進行優選.最后，以一個實際高校的排課算例驗證本文方法的有效性.

高校排課問題；優化；啟發式算法；關系運算

1 引言

高校排課問題隨著我國高等教育改革的不斷深化，變得越來越突出.一方面，在招生規模擴大，學生個性化培養模式不斷出現的情況下，以往的以“班級”為單位的排課方法與新的培養模式不相符；另一方面，由于高校招生類別不斷細化，如本科、學術型碩士、專業學位碩士與博士等，而現階段我國本科和研究生教學體系是分開進行的，缺乏統一教學資源管理平臺，同一學校又公用統一教學資源，即教學場館（所）及其可用時間段、任課教師及其可支配時間段、選課學生及其可行時間段和所開設的課程，以往僅單方面針對某一學生類別的排課策略，不僅是當前多類別學生排課理論的缺失，而且在教學資源的計劃統籌、優化配置等方面，極易造成浪費，缺乏有效科學方法指導.

排課問題是典型的多目標組合優化問題，Even等［1］證明排課問題為NP完全類問題.在早期，排課問題的解決方法主要為模擬手工排課的啟發式方法［2,3］，該方法具有人工排課的靈活性特點，一定程度上減輕了手工排課的繁雜工作量，但由于缺乏全局范疇的優化統籌，當教學資源相對緊缺，排課量大時，容易造成排課后期部分課程無解，即排課失敗，而不得不返回重新調整.后來，研究者們將排課問題簡化為一些經典問題來求解，出現了整數規劃法［4］、拉格朗日松弛法［5］、切割平面法［6］以及基于網絡流方法［7］等.此類方法很大程度上簡化了排課問題，但也往往忽略了部分實際過程中的約束條件.隨著計算機技術和現代智能優化技術的發展，應用模擬退火［8］、禁忌搜索［9］、遺傳算法［10］、蟻群算法［11,12］以及HSA［13］等方法，在局部尋優求解方面具有較好性能.但類似算法通常針對某些高校自身教學體系的特點進行個性化設計，缺乏對實際問題的復雜多約束性考慮，忽略了統一教學資源環境下各種資源的綜合調配及優化處理.因而，缺少通用性及系統性，這種現象在我國當前在用的排課系統中較為突出.

本文面向高校整體教學資源環境下的復雜多約束排課問題，提出了一種啟發式方法，綜合考慮了全校整體教學資源的優化配置，并基于實際教學過程中的復雜多約束條件，構建了以學生每周上課節次的均勻度與教師對任課時間滿意度加權和最大化為目標函數的優化模型，將啟發式規則轉化為關系運算的方式，在縮小后的解空間內采用啟發式方法求解，以實際排課問題加以應用驗證.

2 問題描述及模型

2.1 符號定義

本文中關于排課問題的集合定義、變量表示及符號定義如下：

教學時間段集合為D=P×W×J，其中P為每學期開課的周次，P=｛1,2,...,｝,≤20；

Timet表示教師t的可用時間段，Timet=｛（p,w,j）｝,p∈P,w∈W,j∈J；

Rrpwj表示教室r在第p周的第w天的第j時間段是否安排課程的二進制變量，若該時間段可以安排課程，則Rrpwj=1，否則Rrpwj=0；

asj表示第s個學生的第j節課與第j+1節課之間的時間間隔是否滿足均勻間隔Js的二進制變量，若滿足均勻間隔，則asj=1，否則asj=0；

pcpwj表示教師對課程c安排在第p周的第w天的第j時間段的滿意程度，若（p,w,j）∈Timet，則pcpwj=1，否則pcpwj=0；

xcrpwj為決策變量，若課程c安排于第p周的第w天的第j時間段在教室r上課，則xcrpwj=1，否則xcrpwj=0.

2.2 問題描述

高校排課問題是將教學計劃擬開設的課程集C，分配到教室資源集R，并分布到各可用時間段集D中，給每門課程安排所需的教室和合理的時間段.其中課程集C中的每門課程c由若干學生（隸屬集合S）選修，并由一名或多名教師（隸屬集合T）任教，同時，一個學生可以選修多門課程，一名教師可以任教多門課程，對教室資源R中的每一間教室r，其可用時間段隸屬于集合D.以下建立排課過程涉及到的約束條件和目標函數.

1）約束條件

課程表是基于排課諸要素滿足必要條件的有意義的編排.針對實際應用中的排課問題，建立約束條件如下：

在同一時間，學生s∈S只能上一門課程，即

在同一時間，教師t∈T只能講授一門課程，即

在同一時間，教室r∈R只能進行一門課程，即

對每門課程c∈C需達到預定的教學時數nc，即

教室容量br大于等于該教室上課人數，即教室總數ˉr大于等于同一時間安排的課程總數，即

特殊課程需安排在特殊類型的教室里，其中RTSR表示教室集合R中去掉特殊教室TSR的剩余教室集合，即

若教室r在時間（p,w,j）上不能安排課程，即Rrpwj=0，則任何一門課程c在時間（p,w,j）都不能安排在教室r，即

2）目標函數

排課問題是在諸多可行方案中進行優選的過程，衡量排課方案的優劣往往難以用一個指標進行評判.本文綜合考慮學生的學習接受能力及任課教師的教學、科研時間搭配等影響因素，將目標函數歸結為學生每周上課節次的均勻度與教師任課時間滿意度之加權和，即

3 模型求解

本文的優化模型是在滿足條件（1）～（9）的情況下，使目標函數（10）達到最大，即綜合考慮學生的學習接受能力及任課教師的教學、科研時間搭配等影響因素，使學生每周上課節次的均勻度與教師任課時間滿意度之加權和達到最大值.

3.1 問題規模

排課問題的NP-hard本質，決定了求解的困難性，特別是在排課數量大（通常超過300門），學生選課情況復雜（多類別、跨專業）的情況下，其排課問題的求解規模極大.以下針對2.2節中的問題描述，討論其排課問題的規模.

以大連海事大學2013-2014第一學期統招碩士、統招博士的523門待排課程為例，總學時數為13856，可用教室數為363，則排課的規模為

對如此規模的問題，需要采取有效的方法進行求解.考慮到課程表是排課諸要素滿足必要條件的有意義的編排，本文采用啟發式方法，首先將排課約束條件轉變為啟發式規則，并采用關系代數表達式將對應的約束函數等價變換為關系之間的運算，進而轉化為關系型數據庫中的SQL操作，逐步縮小解空間的搜索范圍，在此基礎上采用啟發式方法在縮小后的可行解空間中進行優選.

3.2 約束的關系代數轉換

首先定義排課相關的關系模式如下：

學生選課關系模式SC：學號（GID），課程號（CID），任課教師（TID），班級（Cls），學時（Shr），學分（Cre）；

課程關系模式CI：課程號（CID），課程名（CNm），課程類別（CIt），上課時間（ST）；

教室關系模式CR：教室號（RID），教室名（RNm），最大容納人數（MCp），教室類型（Rty），教室需求（Cnd）；

教室與時間關系模式NR：教室號（RID），上課時間（ST），教室不可用時間（NT）；

課程與教室關系模式CD：課程號（CID），教室號（RID）.

將上述約束條件（1）～（9）轉化為如下關系代數表示，其中??表示自然連接操作，∏表示投影操作，σ表示選擇操作，*表示所有屬性，count（·）表示計數函數，G表示聚集操作.

式（1）轉化為

把學生s∈S的上課時間投影到q1，將q1中的上課時間按時間進行分組聚集操作，將分組的結果記錄為Q1，因在同一時間，學生s∈S只能上一門課程，故Q1中所有元素均小于等于1.

式（2）轉化為

把教師t∈T的上課時間投影到q2，將q2中的上課時間按時間進行分組聚集操作，將分組的結果記錄為Q2，因在同一時間，教師t∈T只能講授一門課程，故Q2中所有元素均小于等于1.

式（3）轉化為

把教室r∈R的上課時間投影到q3，將q3中的上課時間按時間進行分組聚集操作，將分組的結果記錄為Q3，因在同一時間，教室r∈R只能進行一門課程，故Q3中所有元素均小于等于1.

式（4）轉化為

按課程進行分組聚集操作，記錄課程c∈C的上課次數為Q4，因對每門課程c∈C需達到預定的教學時數nc，故Q4=nc.

式（5）轉化為

記錄課程c∈C的上課人數為Q5，記錄課程c∈C所在上課教室的最大容納人數MCp記為，因教室容量大于等于該教室上課人數，故Q5≤.

式（6）轉化為

記錄某時刻d∈D開設課程的總數為Q6，因教室總數大于等于同一時間安排的課程總數，故Q6≤.

式（8）轉化為σCID=c,Cnd=Rty（CICDCR）.該式表示課程c∈C安排的教室類型Rty與教室類型需求Cnd相同的記錄，若記錄為空，則表示課程c∈C安排的教室類型與教室類型需求不相同，若記錄不為空，則兩者相同.

式（9）轉化為q9←（σST=NT（CICDNR））.將上課時間與教室不可用時間相同的記錄進行選擇并記錄為q9，若q9=?，則表示上課時間在教師可用時間范圍內.若教室r∈R在某時間不能安排課程，則任何一門課程c（c∈C）在該時間都不能安排在教室r（r∈R），即q9=?時，約束3中的Q3=0.

上述各關系代數形式實際上是一種啟發式規則的表現，在關系數據庫中通過結構化查詢語言（SQL）實現操作，從而獲得縮小后的解空間，為在此基礎上的啟發式方法求解提供基礎.

3.3 算法步驟

步驟1初始化排課基礎數據i=1，擬開設課程集C，教室資源集R，可用教室集R′（R′?R），學生集合S，選擇課程c（c∈C）的所有學生記錄集記為Sc，教師集合T，教師t（t∈T）的任課記錄集記為Ct，學生s（s∈S）上課的沖突時間段集合記為Ds；

步驟3隨機選擇一門優先級最高的待排課程j；

步驟4獲取選擇課程j的所有學生記錄集Sj，且j∈C；

步驟5若s∈S，執行如下操作：

1）獲取學生s的所有課程，根據式（11）標記所有沖突時間段Ds；2）s←s+1；

步驟6若Ds中的元素與所有時間段都沖突，則調整已排課程，得到可用時間段，轉到步驟5；

步驟7獲取任教課程j的教師（們）任課記錄集Ct，且t∈Ct；

步驟8根據上式（12）以及Ct標記沖突時間段；

步驟9若所有時間段都沖突，則調整已排課程，得到不沖突時間段；步驟10獲取可用教室的記錄集R′（R′?R）；

步驟11若可用教室資源為0，則增加可用教室，并轉到步驟12；

步驟12在避免上述所有沖突的情況下尋找滿足上述約束（14）～（16）的所有可用教室.若教室資源不足，則增加教室資源；

步驟13獲取任教課程j的教師（們）的禁忌時間段；

步驟14基于貪心策略選擇教室容量br減去j的上課人數最小的教室，優先選擇符合間隔條件，且與教師禁忌時間不沖突的時間段；

步驟15保存課程j的排課結果，i←i+1，轉到步驟2.

4 實驗結果及分析

以大連海事大學2012-2013學年第二學期和2013-2014學年第一學期，全體學術型碩士研究生、全日制專業學位研究生和博士研究生的教學計劃課程編排為例，采用本文提出的啟發式算法進行求解，系統運行于C/S（客戶端/服務器）網絡體系結構，其中客戶端硬件配置為CPU-Intel Core E4600，內存3GB，OS-windows7 ultimate；服務器硬件配置為CPU-Intel Core E5200，內存-4GB，OS-Windows Server 2008；編譯環境為visual Studio 2010.表1顯示大連海事大學研究生院兩個學期的有關排課數據.

在實際排課過程中，可按需設置目標函數中的α值，使排課結果側重于教師滿意度或側重于課程間隔均勻度.當α=0.5時，排課實驗結果如表2所示.從表2中可以看出，2012-2013學年第二學期課程間隔均勻度為72.9%，2013-2014學年第一學期全體碩士和博士的課程均勻間隔度為79.1%.教師滿意度數據以排課前教師事先錄入的信息為準，在此不再羅列，計算得到2012-2013學年第二學期的教師滿意度為89.2%，2013-2014學年第一學期的教師滿意度為86.8%.

表1 大連海事大學研究生院兩個學期有關排課數據Table 1 The Characteristics of Datasets of two semesters from the Graduate School of DLMU

表2 排課結果Table 2 Computational results of proposed method

表3給出了部分排課結果界面，該排課結果已經應用于大連海事大學研究生院2013-2014學年第一學期所有類別研究生的教學過程中，實際檢測無異常.對個別教師上課時間的個性化需求，通過系統的手動調整功能得到滿足.由于綜合考慮了教師滿意度和課程均勻間隔度，使課程的安排最大可能地滿足教師和學生的上課需求.

表3 部分課程的排課界面Table 3 A partial illustration of a feasible timetable

5 結束語

本文針對高校整體教學資源環境下的復雜多約束排課問題，構建了以學生課程間隔的均勻度與任課教師滿意度加權和最大化為目標函數的優化模型，為高校排課問題的可行解提供了一種新的評價方法；在求解過程中采用啟發式方法，將排課約束轉變為啟發式規則，并采用關系代數表達式將對應的約束函數等價變換為關系之間的運算，逐步縮小解空間的搜索范圍，在此基礎上，采用啟發式方法在縮小后的可行解空間進行優選，為此類問題提供了一種新的求解方法.

［1］Even S，Itai A，Shamir A.On the complexity of time table and multi-commodity flow problems［J］.SIAM Journal on Computing，1976，5（4）：691-703.

［2］Black A.Techniques for producing school timetables on a computer and their application to other scheduling problems［J］.The Computer Journal，1961，4（3）：237-245.

［3］GotliebCC.Theconstructionofclass-teachertimetables［C］//ProceedingsoftheInternationalFederationforInformationProcessing Congress.Amsterdam：North-Holland Publishing Co，1963，73-77.

［4］Shaw C C，Yu C C.From timetabling to train regulation：A new train operation model［J］.Information and Software Technology，2005，9（47）：575-585.

［5］Arabinda T.School timetabling：A case in large binary integer linear programming［J］.Management Science，1984，30（12）：1473-1489.

［6］Pasquale A，Igor V.A computational study of a cutting plane algorithm for university course timetabling［J］.Journal of Scheduling，2005，6（8）：497-514.

［7］諶效東.實用化計算機輔助排課系統的研究與實現［J］.西安電子科技大學學報，1991，18（3）：38-44.

Chen Xiaodong.A study and implementation of the practical computer-aided timetable scheduling system［J］.Journal of Xidian University，1991，18（3）：38-44.（in Chinese）

［8］Aldy G，Kien M N，Kim L P.A hybridized Lagrangian relaxation and simulated annealing method for the course timetabling problem［J］.Computers and Operations Research，2012，12（39）：3074-3088.

［9］周小鋒，劉健.基于偶圖匹配和禁忌搜索的排課新算法［J］.系統工程理論與實踐，2008，28（3）：111-117.

Zhou Xiaofeng，Liu Jian.A new approach to curriculum scheduling based on graph matching and tabu search［J］.Systems Engineering：Theory and Practice，2008，28（3）：111-117.（in Chinese）

［10］Yang S X，Sadaf N J.Genetic algorithms with guided and local search strategies for university course timetabling［J］.IEEE Transactions on Systems，Man，and Cybernetics：Part C，Applications and Reviews，2011，41（1）：93-106.

［11］靳志宏，于波，侯麗曉.基于配載約束的配送優化問題及其求解算法［J］.系統工程學報，2012，27（3）：390-398.

Jin Zhihong，Yu Bo，Hou Lixiao.Vehicle routing optimization problem and its solution method based on vehicle loading constraints［J］.Journal of Systems Engineering，2012，27（3）：390-398.（in Chinese）

［12］Thatchai L，Pupong P.Best-worst ant colony system parameter investigation by using experimental design and analysis for course timetabling problem［C］//Second International Conference on Computer and Network Technology.IEEE Computer Society，2010，467-471.

［13］Mohammed A A，Ahamad T K，Munir Z.University course timetabling using a hybrid harmony search metaheuristic algorithm［J］.

IEEE Transactions on Systems，Man，and Cybernetics：Part C，Applications and Reviews，2012，42（5）：664-681.

University course timetabling problem using a heuristic approach based on uniform teaching resources

Zhang Dezhen1，Chen Gang1，Wang Ying2，Guo Saijun1，Li Yonghua3

（1.College of Information Science and Technology，Dalian Maritime University，Dalian 116026，China；
2.Graduate School，Dalian Maritime University，Dalian 116026，China；
3.Dalian Top Software Science and Technology Ltd，Dalian 116600，China）

The paper studies the university course timetabling problem（UCTP）with the practical-relevant problems based on the union teaching resources of a university for undergraduates，postgraduates and PhD. students.A new heuristic method for UCTP is presented，considering complex multi-constraint conditions based on the uniform teaching resources which include students，teachers and classrooms with feasible times lot，respectively.The constraints are modeled and the objective function is proposed based on the evenness for all the curriculums of a student and a teacher's satisfaction for his/herlecturing time.And then，transform the constraints to relational operation expressed by relation algebra.Thereby heuristic rules are formed by relational calculus.Greedy strategy is applied to search the optimal solutions in the shrunk solution space. Finally，a course timetabling instance from a university is carried out to demonstrate the validation of the new method.

university course timetabling problem；optimization；heuristic algorithm；relational operation

TP273

A

1000-5781（2015）06-0836-08

10.13383/j.cnki.jse.2015.06.011

張德珍（1973-），男，遼寧大連人，博士后，副教授，研究方向：優化理論，軟件工程，Email：dezhen.zhang@gmail.com；

陳剛（1989-），男，山東淄博人，碩士生，研究方向：軟件工程，Email：cg82616424@163.com；

王營（1980-），女，遼寧大連人，助理研究員，研究方向：研究生教育管理Email：jjxiaoker@163.com；

郭賽君（1989-），女，山西長治人，碩士生，研究方向：軟件工程，Email：1031348593@qq.com；

李永華（1987-），女，遼寧大連人，工程師，研究方向：應用數學，Email：605651670@qq.com.

2013-11-05；

2014-05-02.

遼寧省研究生培養機制改革研究資助項目（201310151-40）；大連海事大學研究生教育教學改革資助項目（YJG2013001）；中央高校基本科研業務費資助項目（01750312）.