特殊要求时间段的排课问题数学模型

杨子兰，李 睿，张 瑜

(云南大学 旅游文化学院，云南 丽江 674199)

特殊要求时间段的排课问题数学模型

杨子兰，李 睿，张 瑜

(云南大学 旅游文化学院，云南 丽江 674199)

本文对排课问题的约束条件进行深入分析，将教师、班级、课程捆绑成一个教学任务单元，并以比较重要的课程尽可能地安排在授课效果较好的节次中且多学时课程安排要尽量均匀分布为目标函数，建立0-1整数规划模型，最后结合自然班固定教室的特点，设计出启发式算法求其可行解。

捆绑式排课；整数规划；教学任务单元；启发式算法

1962年Gotlieb提出了课表编排问题的数学模型[1]，从而使之成为计算机软件应用专家和数学家共同研究的课题。1975年S.Even和cooper等人将排课问题理论化，证明了排课问题是NP完全问题[2]，当问题的规模增大时，其复杂度呈指数增长，在一般的实际情况中不可能准确地求出最优解。我国对于排课问题的研究始于20世纪80年代。1984年，林章希和林尧瑞发表了在排课问题上的实验性研究成果[3]。2006年，任克强等给出了一种基于约束满足的高校排课问题模型，提出了高质量排课系统方案[4]。2011年，宗薇根据教师、学生、教室、课程和课程时间段要求建立一个多约束条件的高校排课数学模型，采用随机可行排课法产生可行排课方案，然后利用遗传算法在可行方案中寻找最优排课方案[5]。2012年，杨彦明等人针对军队任职院校课程表编排特点，在分析军队任职院校排课因素、约束条件以及求解目标等问题基础上，建立相应数学优化模型，构建其基本求解框架，并利用遗传算法解决该问题[6]。2014年张丽丽等人在深入分析排课模型基础上，采用三维立体编码，提出基于三维立体遗传编码设计的排课系统，但是收敛速度过于缓慢[7]。2016年顾治程等利用FFD算法思想，提出只考虑教室分配问题的新算法[8]。周靖靖和杨梅以全体教师的满意度最大为目标函数建立了0-1整数规划模型，并以实例验证了模型的实用性[9]。

上述文献中的算法大多是遗传算法，遗传算法是模拟达尔文生物进化论的自然选择和孟德尔遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优化的方法[10]。但遗传算法比较复杂，且排课问题的约束条件较多时，遗传算法可能找不到解。因此，本文分析排课问题的硬性约束条件，为得到较好的数学模型，特将教师、班级、课程捆绑成一个教学任务单元，并以比较重要的课程尽可能地安排在授课效果较好的节次中且多学时课程安排要尽量均匀分布为目标函数，建立0-1整数规划模型，最后结合自然班固定教室等特点，设计出启发式算法求其可行解。

1 问题描述及数学模型

1.1 问题描述

排课问题涉及多方面的问题，涉及到的因素主要有教师、班级、课程、教室、时间等五项基本因素，排课问题就是要寻求把这五个因素各自组合起来的一种方案，且这五项基本因素必须遵守以下硬性条件：（1）同一个时间点，每个班级最多安排上一门课程；（2）同一个时间点，每个老师最多安排上一门课程；（3）同一个时间点，每个教室最多安排上同一门课程；（4）教室上课人数不超过其最大容量；（5）每个班级的每个科目在一周内的课时数必须等于该门课程的课时要求。

1.2 建立数学模型

1.2.1 时间段编号

为得到较好的数学模型，特对时间段进行编号，且对时间段的编号不是按时间顺序编号。具体如下：将一周分为5个工作日，每天设为5个时间段，分别为上午 8：00～9：50为 1-2节课；上午10：10～12：00 为 3-4 节课；下午 2：30～4：20 为 5-6节课；下午 4：30～6：20为 7-8节课；下午 7：30～9：20为9-10节课。这样，每周五天工作日共有二十五个时间段。为了方便，特将25个时间段划分为五种类型，并进行编号，如表1所示。

表1 时间段编号

1.2.2 变量描述

设教师集合表示为T={T1,T2,…,Ti,…,Tm}（m个教师）；教室集合表示为 R={(R1,r1),(R2,r2),…,(Ri,ri),…,(Rn,rn)}（其中 Ri表示第 i个教室，ri表示第i个教室的容量，即该教室所能容纳的人数）；课程集合表示为P={P1,P2,…,Pi,…,Pw}且已按课程重要程度排序（即当i＜j时，pi比 pj重要，且共有w门课程），与P对应的w门课程的周学时数依次为l1,l2,…,lw；时间段集合表示为 π={1,2，…,i,…,25}（25个时间段）；自然班级集合表示为C={(C1,c1),(C2,c2),…,(Ci,ci),…,(Cq,cq)}（其中 Ci表示第 i个班级，ci表示第i个班级的人数）。

1.2.3 数学模型

排课问题对应到数学上就是将五个集合重新排列组合，构成一个大集合，且大集合里的每个元素必须体现某班某时间由某老师在某教室上某课程的信息，这个重新的组合涉及到的最大难度就是冲突问题。一般情况下，由于每个学校某学期的开课计划中已经安排好某教师上某班的某门课程的信息，故排课过程中可以直接利用这些数据资源。本文利用捆绑式排课的方法，即将教师集合T、班级集合C、课程集合P捆绑成一个教学任务单元TCP（假设教学任务单元已按课程重要程度排序，教学任务单元的总数| TCP|=l），教室集合R为一个单元，时间集合π为一个单元。因此，排课的主要问题变成了如何安排时间段和教室，实现某时间段某教学任务单元最多对应一个符合需求的教室，即遵守上述约束条件。为方便建立数学模型，引入三维0-1决策变量xijt，当第i个教学任务单元在第t个时间段在第 j个教室上课时xijt=1，否则xijt=0，则任一教室在同一时间段至多安排一个教学任务单元上课可用数学式子表示为

每周内每个教学任务单元对应的课程上课时间要等于该门课的周课时可用数学式子表示为

同一时间段至多有n个教学任务单元在n个教室上课可用数学式子表示为

第i个教学任务单元在第 j个教室上课时需满足该教学任务单元中的教学班级人数ci不超出教室 j的容量rj可用数学式子表示为

在遵守上述基本条件的前提下，排课应该尽量满足教学任务单元的优化安排需求，以便课程的安排尽可能地科学、合理。本文参考文献[6]中的方法，用 Bj′(j′=1′,2′,3′,4′)表示课程的重要程度，也称为权重，把课程划分为专业核心课、专业基础课、公共课程、专业选修课和全院选修课(设对应于教学任务单元TCP中的课程顺序前m1门课为专业核心课，第m1+1至第m2门课为专业基础课，第m2+1至第m3门课为公共课程，第m3+1至第m4门课为专业选修课，第m4+1至第m5门课为全院选修课)，为了体现出重要程度，假设其权重依次赋值为 4、3、2、0.6、0.4。所以当 j′=1′时，有B′=4（即当1≤i≤m1时有 Bi=4）；当 j′=2′时，有B′=3（即当 m1＜i≤m2时有 Bi=3）；当 j′=3′时，有B′=2（即当 m2＜i≤m3时有 Bi=2）；当 j′=4′时，有B4′=0.6（即当 m3＜i≤m4时有 Bi=0.6）；当j′=5′时 ，有 B=0.4（ 即 当 m＜i≤m时 有5′45Bi=0.4）。用 at′(t′=1′,2′,3′,4′,5′)表示课时质量，其中当 t′=1′时 a′=1表示第一个时间段(即第1、2节)的教学质量，故当1≤i≤5时有 ai=1；当 t′=2′时，有 a′=0.8表示第二个时间段(即第3、4节)的教学质量，故当 6≤i≤10 时，有 ai=0.8；当 t′=3′时，有 a′=0.6表示第三个时间段(即第5、6节)的教学质量，故当11≤i≤15时，有 ai=0.6；当 t′=4′时，有 a′=0.3表示第四个时间段(即第7、8节)的教学质量，故当16≤i≤20 时，有 ai=0.3；当 t′=5′时，有 a′=0.1表示第五个时间段(即第9、10节)的教学质量，故当21≤i≤25时，有ai=0.1。对于周学时较多的课程，要尽量将其间隔一天（含）以上安排。用ei(i=1,2,3,4)表示一门课程安排间隔i天的教学效果系数，设定间隔1、2、3、4天的值分别为 1、3、4、2。

本文考虑比较重要的课程要最大程度地安排在授课效果较好的节次中且多学时课程（周学时大于等于3）的安排要尽量均匀分布为目标函数，得出三维的0-1整数规划模型如下：

2 算法设计

在以往的排课算法中，往往不考虑课程的时间段要求，且大多采用遗传算法[6-8,11-12],本算法以比较重要的课程尽可能地安排在授课效果较好的节次中且多学时课程安排要尽量均匀分布为目标。假设课程i的周学时li是2的奇数倍或偶数倍，则原来的教学任务单元就视为个教学任务单元，假设课程i的周学时li是2的分数倍，则原来的教学任务单元就视为个教学任务单元，得到扩展后的教学任务单元集合S={s1,s2,…,sl}，其含有l个教学任务单元且设S中的元素已按课程的重要程度排序（此时S中有相同元素），其中si表示第i个教学任务单元。假设有q个自然班级，每个自然班都有固定的教室，普通课程都可以安排在相应的自然班教室上课，这样就不用考虑教室的安排及容量问题。因此，本算法只考虑在普通教室上课的情形，且每个学校某学期的开课计划中已经安排好某教师上某班的某门课程的信息，故排课过程中可以直接利用这些数据资源，考虑这些因素，设计出如下启发式算法：

初始条件下，记S1=S，取 j=1。

第1步:在Sj中按顺序选出与教学任务有冲突的教学任务单元，记为Sj+1，且令S(j)=Sj-Sj+1，当Sj+1≠Φ时，转第2步，否则转第3步；

第2步：将S(j)中的教学任务单元依次安排在第i个时间段且在对应的自然班固定教室上课，记，表示由第i个时间段在对应的自然教室上课的教学任务单元时间对构成的集合，令i=i+1，当i＜25时，令 j=j+1，转第 1步开始处，否则无可行解；

第3步：将S(j)中教学任务单元依次安排在第i个时间段且在对应自然班固定教室上课，转第4步；

第 4 步：在 ⋃S(j)′中按元素顺序依次选出周课时数为2的分数倍的课程对应的教学任务单元，按照选出顺序号，规定顺序号为偶数的教学任务单元单周不变，双周减一次课，顺序号为奇数的教学任务单元双周不变，单周减一次课，转第5步；

第 5 步：输出 ⋃S(j)′，算法停止。

算法复杂度分析：第1步的复杂度取决于与前面教学任务有冲突的教学任务单元个数，复杂度最多为O（|S|）；第2步最多循环25次（此时无可行解），复杂度不超出O（25| S(j)|）；第 3 步的复杂度取决于在第i个时间段被安排上课的教学任务单元个数，复杂度最多为O（|S(j)|）；第 4 步的复杂度取决于周课时数为2的分数倍的课程对应的教学任务单元个数，复杂度最多为；算法第5步复杂度为。故算法总复杂度不超出O（25|S|）。

3 算法有效性验证

表2列出了我校信科系下学期的部分教学开课计划表。对表2进行扩展后的教学计划表如表3所示。

表2 信科系下学期的部分教学开课计划表

表3 信科系下学期的部分教学开课计划扩展表

为了方便，表3中的每个教学任务单元都用对应的序号表示，则教学任务单元集合可以表示为，在S1中选出与前面的教学任务单元有冲突的教学任务单元构成一个集合，记为S2，即，则S(1)=S1-S2={1 ,3,6}，将S(1)中的教学任务单元依次安排在第1个时间段且在对应的自然班固定教室上课，得到 S(1)′={(1 ,1),(3,1),(6,1)}；在S2中选出与前面的教学任务单元有冲突的教学任务单元构成一个集合，记为 S3，即，则，将 S(2)中的教学任务单元依次安排在第2个时间段且在对应的自然班固定教室上课，得到；在 S3中选出与前面的教学任务单元有冲突的教学任务单元构成一个集合，记 为 S4，即，则，将 S(3)中的教学任务单元依次安排在第3个时间段且在对应的自然班固定教室上课，得到；在 S4中选出与前面的教学任务单元有冲突的教学任务单元构成一个集合，记为 S5，即，则，将S(4)中的教学任务单元依次安排在第4个时间段且在对应的自然班固定教室上课，得到 S(4)′={( 2,4),(4,4),(5,4),(7,4),(9,4)}；在 S5中选出与前面的教学任务单元有冲突的教学任务单元 构 成 一 个 集 合 ，记 为 S6，即，则，将 S(5)中的教学任务单元依次安排在第5个时间段且在对应的自然班固定教室上课，得到；在 S6中选出与前面的教学任务单元有冲突的教学任务单元构成一个集合，记为 S7，即，则，将 S(6)中的教学任务单元依次安排在第 6个时间段且在对应的自然班固定教室上课，得到S(6)′={( 2″,6),(4″,6)} ；在 S7中选出与前面的教学任务单元有冲突的教学任务单元构成一个集合，记为S8，即 S8= Φ ，则，将 S(7)中的教学任务单元依次安排在第7个时间段且在对应的自然班固定教室上课，得到S(7)′={(8′,7)} ；在 ⋃S(j)′中按元素顺序依次选出周课时数为2的分数倍的课程对应的教学任务单元，按照选出的顺序号，规定顺序号为偶数的教学任务单元单周不变，双周减一次课，顺序号为奇数的教学任务单元双周不变，单周减一次课，得到

即得到一个可行解，表2中的每个教学任务单元都已经被安排，从而验证了算法的有效性。

4 结论

排课问题是一个多约束的组合优化问题，也是NP-完全类问题，很难找到多项式时间算法。本文对时间段进行特殊编号，将教师、班级、课程捆绑成一个教学任务单元集合，以比较重要的课程尽可能地安排在授课效果较好的节次中且多学时课程安排要尽量均匀分布为目标函数，建立0-1整数规划模型，并根据自然班固定教室的特点，利用每个学校某学期的开课计划数据资源信息，设计出启发式算法求其可行解。该算法思想简单，易懂，复杂度对多为O(25|S|)。如何进一步对算法进行丰富、修正，从而提高算法精度是本人今后将要开展的进一步工作。

[1]Gotlieb C C.The construction of Class-Teacher Time-Tables[J].Communications of the ACM,1962,5(6):73-77.

[2]Even S,Itai A,Shamir A.Onthecomplexityof timetableand multi-commodity flow problems[C].Proc of 16 thannual symposiumon foundations of computer science,1975:184-193.

[3]林漳希，林尧瑞.人工智能技术在课表编程中的应用[J].清华大学学报（自然版），1984，24（12）：1-8．

[4]任克强，赵光甫.基于约束满足的高校排课问题研究[J].江西理工大学学报，2006，27（6）：70-72．

[5]宗 薇，赵光甫.高校智能排课系统算法的研究与实现[J].计算机仿真，2011，28（12）：389-392．

[6]杨彦明，岳翠翠，李其申．军队任职院校排课问题的数学建模[J].计算机与现代化，2012，11：14-17.

[7]张丽丽，许 峰，胡 娟．基于三维立体遗传编码设计的排课系统[J].重庆工商大学学报（自然科学版），2014，31（7）：9-13．

[8]顾治程，蒋 艳.基于FFD算法的高校排课系统设计与实现[J].软件导刊，2016，15（1）：110-111.

[9]周靖靖，杨 梅.基于满意度的最优排课方案[J].西南师范大学学报（自然科学版），2016，41（1）：185-187．[10]卓金武，李必文，魏永生，等.MATLAB在数学建模中的应用[M].2版.北京：北京航空航天大学出版社，2014：79．

[11]叶碧虾．遗传算法在排课系统中的优化研究[J].吉林师范大学学报（自然科学版），2014，2:185-187.

[12]Limkar S,Khalwadekar A,Tekale A,et al.Genetic Algorithm:Paradigm Shift over a Traditional Approach of Timetable Scheduling[C].Proceedings of the 3rd International Conference on Frontiers of Intelligent Computing:Theory and Applications(FICTA)2014.Springer International Publishing,2015:771-780.

Mathematical model of course scheduling problem with special requirements

YANG Zi-Lan,LI Rui,ZHANG Yu

（School of Tourism and Culture,Yunnan University,Lijiang Yunnan 674199,China)

This paper made an in-depth analysis of the course scheduling problem,bundled the teacher,class and course into a teaching task unit,and built the 0-1 integer programming model to maximize the effect of the teaching quality,and more school curricula will be evenly distributed as possible as the objective function.Finally,combined with the characteristics of natural classes of fixed classroom,a heuristic algorithm was designed to find the satisfactory solution.

binding scheduling;integer programming;teaching task unit;heuristic algorithm

A

1004-4329（2017）02-015-05

10.14096/j.cnki.cn34-1069/n/1004-4329（2017）02-015-05

2017-01-20

云南省教育厅科学研究基金项目（2016ZDX152）；云南大学旅游文化学院院级项目（2015XY08）资助。

杨子兰（1985－ ），女，硕士，讲师，研究方向：组合最优化与算法研究。