高校排课的数学模型
高校排课的数学模型
关键词由CSDN通过智能技术生成
一、高校排课面临的主要问题
1 .1问题的提出
课程表问题又称时间表问题，课表编排是一个多指标的优化决策冋题，是组合规划中的典型
问
题。课程表的编排就是解决对时间和空间资源争夺而引起的冲突。
20
世纪
60年代末，国外就有人开始研究课表编排问题。1962年，Gotlieb曾提出了一个课表问题的数学模型，之后人们对课表问题的算法，
以及
解的存在性等问题做了很多深入探讨。但是大多数文献所用的数学模型都是Gotlieb的数学模型到的简化或补充。Mihoc和Balas将课表公式化为一个优化问题,，Krawczk则提出一种线性编程的方法。
J
unginger将课表问题简化为三维运输问题，而Tripathy则把课表问题视作整数线性编程问题并提岀了课表的数学模
型。
20
世纪
70年代中期，s·Eveo等人论证了课表问题是NP完全类问题，之后很多人尝试采用各种方法对此问题求解但由于课表问题所涉及的信息较多，并且求课表问题最佳解的时间复杂性是课表规模的指数级，所以对于有一定规模的课表问题,一般采用求较佳解的算法。
1 .2 面临的 主要问题
高等学校排课系统具有其固有复杂性，其本质上是一个多资源分配的复杂问题,这些资源包括教师、时间、教室、班级、课程等等,而这些资源的数量是有限的。在排课系统中，对资源的占有均要求满足一定的约束条件:如教师在同一时间段内只能上ー个班级的某一门课程,在某一段时间内不能跨校区上课:某种类型的教室只能满足某一类课程和某一种班级类型的上课要求等等。本文通过对排课系统中教学资源的分类及其应该满足的约束条件进行系统分析，提出排课问题的线性规划模型在此基础上通过变量和决策变量的选择，
用Lingo软件对两个排课案例进行求解。同时提出列生成算法与排课问题相结合，对求解进行优化，提高求解效率。
实际结果表明，该模型能很好表示
排
课问题
以及
排课结果，
这
表明算法是有效的。
二、模型构建
2.1 模型假设
在实际设计中我们要考虑的有：
- 教师的要求
- 教室的要求
- 班级的要求
- 课程的要求
针对不同的要求我们要在设计中考虑仝面,使得资源的要求能够满足,并且各个资源之间免于发生冲突。
典型的
硬
约束和
软
约束如表
2.1
所示：
(
表
2
.
1）
| 序号 | 硬约束 | 软约束 |
| 1 | 教室不冲突：每一个班级每一节课程只能安排一门科目 | 课程根据类别和性质的不同，某些课程需要安排在限定的时间段,例如高等数学、运筹学、大学英语等重要课程安排在上午等 |
| 2 | 教室课表不冲突： 每位老师， 在 每一时间 段内 只能教 授 一门课程 | 限定某些时间段不能安排课程，如：每周三下午不安排课程 |
| 3 | 课程安排要求1：一 门课程每天只能安排一次 | 课程尽量安排在教学效果较好的节次。通过长期的观察表明课程上课的效果与上课的节次有一定的关系‚一般来说一、二节教学效果最好‚上午时间比下午时间好。所以在排课的时候中应尽量将难度大的课程安排到教学效果较好的节次以确保有一定的教学效果 |
| 4 | 课程安排要求2：本学期所有专业的全部课程都得到安排 | 多学时课程的周次安排要尽量错开。在排课时中‚为了保证有较好的教学效果对于每周不只教授一次的课程‚都要尽量将其隔一天或隔一天以上安排 |
| 5 | 教室容量要求：教室的容量大于参加课程的班级的总人数 | 班级课程表在星期上尽量分布均匀指一个班级上课时间要均匀不能周一周二每天上节课周三以后每天就上次课或是没有课了。尽量做到每天上课节次都差不多。 或者是前半学期课程安排比较满，后半学期几乎不安排课 |
| 6 | 同一个班级的所有学生将参 加 相同的课程 | 一周课表中的每个时间有一定优度对一周中的每天都设置一个优先度数值。然后在排课是按照设定的优先度数进行分配 |
| 7 | …… | 教师对上课时间存在一定的喜好对于某些对上课时间有一定要求的老师可以做到人性化处理 |
| 8 | 班级相邻上课地点尽可能距离较近避免出现教师及学生在一、二节与三、四节的课间无法到下一堂课上课教室的问题 | |
| 9 | 不推荐教师上连堂课。主要是避免出现教师疲劳，导致教学效果不佳的问题 |
硬
约束必须满足，从而产生可行的解决方案。而
软
约
束
的满足会使得排课结果更加具有人性化。
软约束是受主观因素和客观条件的影响,根据不同的要求进行限定,关于其建立的数学模型将在
具体
实例中完成。
2.2 决策变量
我们把
排课系统
看成
是一个线性规划问题，从而建立一个线性规划模型来实现
该排课
系统。排课系统需要
对教师、课程、班级、时间、教室这
五个资源的合理分配我们可以定义五个资源的集合为:
教师集合为T={t
1
,t
2
,…,t
n
}(
n
∈N),教师t∈T每周上课的最大天数为h
t
。
课程集合为S={
s
1
,s
2
,…,
s
m
}(m∈N),一周中每个课程s上课的课时是n
s
。
班级集合为C={c
1
,
c
2
,
…,
c
l
}(l∈N),
时间段集合为P={p
1
,p
2
,…,p
28
},定义每天的上课时间段可以分成4个，分别是8:00-9:50,10:20-12:10,14
:30
-16:20,16:30-18
:2
0。每周上课7天，因此一周的时间段共有28个。P
s
表示课程s要求的时间段。
教室集合为R={r
1
,r
2
…,
r
q
}
(q∈N)。R
s
表示课程s要求的教室，R
t
表示教师要求的教室。
天数集合为D={d
1
,d
2
,
…
,d
7}
一周总共有7天。n
c
mim
和n
c
max
分别表示每个班级c在每天上课时间的最小数和最大数。
下面我们来定义排课系统的决策变量,具体如下:
=1，
课程s在时间段p安排在教室r，s∈S,p∈P,r∈R
=1，
教师t在某一天d是上课时间，
t∈T,d∈D
=1，
课程s属于班级c的课程,s
∈S,c∈C
2.3 目标函数
排课系统变成一个线性规划问题,其目标函数可以叙述为使得那些需要特殊安排的课程能够符合条件达到最大的数量即课程安排的最大值。
目标函数：
2.4 约束条件
目标函数(1)是表示难度大的课程安排的最大值
，
即难度值越大的课程安排的越多越好。
约束
条件(
2
)要求一周中每个课程s上课的课时是n
。
约束
条件(
3
)要求一个教室r不能在一个时间段p安排多门课程
。
约束
条件(
4
)要求每个班级c不能在同一时间段p安排多门课程
。
约束
条件(
5
)要求每个老师t不能在同一时间段教授多门课程
。
约束
条件(6)要求每个班级c的每门课程s在一天d中只能安排一次课程
。
约束
条件(7
)
要求
如果
课程s安排在d天(假设
=1)，班级c每天上课的时间在
和
之间。
约束
条件(8)要求个班级c的课程s应该在同一天d安排在同一个教室r
。
约束
条件
(
(
10
)
是减少每个教师每周上课的天数
(
h
t
表示教师t每周上课的最多天数)。
三、其他分析
３.1合班问题
某年级共有M个班,它们都需要上X,Y两门课。用x
i
表示课程X的第
i个
讲台,也表示这个讲台班数的容量(i=1,2,…
，
n);y
j
表示课程Y的第
j个
讲台,也表示这个讲台班数的容量(
j=1
,2…
，
m)。设a
ijk
=1
表示第k个班级即在
x
i
上课又在
y
j
上课。
得到二维合班问题的0-1规划模型：
３.2跨校区问题
多校区排课比单校区从硬约束多了一条，即一个教师 半天内只能出现在一个校区。那么硬性要求有以下 4 个：
（1）一个教师同一时间只能上一门课程；
（2）一个班级同一时间只能上一门课程；
（3）一个教室同一时间只能上一门课程；
（4）一个教师半天内只能出现在一个校区。
同时在优化目标上即软约束也多了一条，即一个教师同一天内只出现在一个校区。那么软要求有以下 4 个：
（1）当某一门课程一周要上多次时，课程的安排比较分散，如高等数学一周上 3次课，上课时间安排为每周的星期一、星期三、星期五为佳；
（2）体育课安排在下午；
（3）繁难课程（如高等数学）安排在上午；
（4）一个教师同一天内只能出现在一个校区。
通过分析，要达到的目标为：
（1）满足硬性要求；
（2）满足软要求
4 参考文献
【1】龚莎.基于回溯法的自动排课算法[j].技术应用.2020
【2】池春姬.合班问题的0-1规划数学模型[j].哈尔滨职业技术学院学报.2007
【3】胡培成.高校课程表编排理论研究概述[j].科普教育.2015年
06
月
【4】苏明杰.基于线性规划模型的高校排课系统[j].软件时空.2022
【5】张春梅.课表的多指标数学模型及解决方法[j]内蒙古大学学报（自然科学版).2004
【6】陶滔,谢卫星.课表模型及排课算法应用[j].计算机系统应用.2011
【7】王志丹.课程安排管理系统分析与设计[j].计算机系统应用
【８】GUY DESAULNffiRS GERAD and Ecole Polytechnique de Montreal.Column generation[M].Spriringer.2005
【9】谢凡荣.求解排课表问题的一个启发式数值算法[j].运筹与管理.2005.10
【10】李彬，李枫.基于 Lingo 软件的高校排课问题研究[j].佛山科学技术学院学报（自然科学版).2021年3月
【11】陈辉，何军.排课问题的数学模型研究[j].沈阳工程学院学报(自然科学版).2017年7月
【12】杨金龙，党小超.基于Lingo软件求解大学医学实验课程排课问题[j].甘肃高师学报.2016
【13】
彭涛
.课程数据分析的Markov链模型[j].清华大学学报.2005年5月
【14】
朱冠宇
.
利用遗传算法求解中学课表安排问题
[j].计算机工程与应用.2020