面向高校统一教学资源排课问题的启发式方法

张德珍，陈刚，王营，郭赛君，李永华

（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）.