课程时间安排-数学建模
qq霸气头像-
课程时间安排的优化模型
摘
要
排课是教务运作中的一项重要工作，
同时排课问题也是一个复杂的组合优化
问题，
对此问题的建模和
求解，
难度都非常大。
多数情况下我们只是满足于求解
问题的一个可行解，而对此可行解的进一步优化往往通过手工完成，效率很低。
< br>目前有很多计算机专家和数学专家都致力于对大规模排课问题的研究，
在此我们<
/p>
给出一个规模相对较少，
约束相对较少的较为简单的排课问题。<
/p>
解决排课中的问
题，
既能满足老师授课上
机的要求又能满足学生对上机时间的合理安排。
让学校、
老师和
同学的满意。
让老师满意，就是安排尽量少出现像同一天同一
位老师上
1-2
节，
7-8
节，
最好是
1-2
节面授
然后
4-5
节课上机；
让同学们满意，
可从以下几方面考虑，
比
如，
同一班级同一门课程，
至少应隔一天上一次，
另
外对学生感到比较难学的课
程尽量安排在最好的时段，
上机时间
要安排在面授课之后；
让学校满意，
就是尽
量减少因出现问题而不得不为老师调课的次数。
根据实际情况在具体模型建立过
程中采用了
0-1
矩阵法，
矩阵的乘法等数学方法，
建立优化类数学模型来求解有
效矩阵，
根据有效矩阵初排课表，
结合多方面因素建立修正矩阵
，
对初排课表逐
层修改，得出最优排课表。并通过
matlab
实现算法和给出模型的解。
先将
123
班级课表和
20
张老师课表转换为
0-1
变量，有
课改为
0
，没课改
为
< br>1
，
组成两个矩阵，
然后可用<
/p>
VB
编程得到一个新的矩阵，
两矩阵中元
素都为
1
时，新的矩阵对应的元素就为
1
，即老师和班级同时有空时为
1
。将
多目标函数
转换为单目标函数，
其他的要求可直接在约束条件中
满足。
然后用
lingo
软件编
程解决（其约束条件和目标函数都可用
lingo
的语句表示出来）
关键词：
排课问题
0-1
矩阵
矩阵的乘法
优化目标矩阵
lingo VB
1
问题重述
排课是教务运作中的一项重
要工作，
同时排课问题也是一个复杂的组合优化
问题，
对此问题的建模和求解，
难度都非常大。
多数情
况下我们只是满足于求解
问题的一个可行解，而对此可行解的进一步优化往往通过手工完
成，效率很低。
目前有很多计算机专家和数学专家都致力于对大规模排课问题的研究，<
/p>
在此我们
给出一个规模相对较少，
约束相
对较少的较为简单的排课问题，
请同学们加以解
决。
目前，
某校的计算机上机课大都安排在计算机学
院，
计算机学院有
5
个机房
用于学生上机，每个机房大约容纳
90
人。安排上
机的课程共有
4
门，指导上机
的教师共
有
24
人，其中
20
< br>人为课程的授课教师，见附件
1
，其他四人为机房的
管理人员，
依次为陆老师，
章老师，
张老师和彭老师，
其中陆老师负责
2
个机房。
共有
123
个
班级需要上机，详细名单见附件
1
。教师和学生的上机时间不能
和他
们的授课课程时间冲突，
为此我们给出了各位教师和各个班
级学生的课程表，
见
文件夹附件
2
。四名管理人员可全天进行上机指导，但只能在自己负责的机房进
行
.
要求：
（
1
）为了保证授课效果，学院规定每个老师在同一个时间段只
能为
1
个班
级进行指导；而同一时段允
许有两名教师在同一个机房分别指导一个班级；
（
2
）上机指导老师尽可能指导自己授课班级的学生；
（
3
）周末尽可能不安排上机；其
次晚上尽可能不安排上机。
（
4
）为了减少教师到新校区的次数，上机时间尽可能与其授课时间安排在
同一天。
（
5
）还有其它要求可根据高校教学的情况，酌情给出，给出时要充分考虑
教学规律、教
学效果和大部分老师、学生的要求。
2
条件假设
1.
每个机房大约容纳
90
人，每个班都在
45
人以下，所以假设每个机房在同一
时间可容纳
2
个班，有
5
个机房。所以有
2
*5=10
个班可同时上机。
2.
题目中要求（
1
）很容易满足，班级老
师一对一。根据要求（
2
）
，可假设上
机
指导老师必须指导自己授课班级的学生。
< br>3.
根据要求
（
3
）
，
可假设周末不安排上机，
这样老师学生都愿意，
并假设晚上可
以安排上机。
4.
将要求（
4
）作为目标函数，
（
1
）
（
2
）
（
3
）为约束条件。
3
符号说明
在模型的求解过程中有说明
4
问题分析
1
，通过对所给附件中课表的安排发现影响排课的因素主要有以下几项：
B
课程
时
时间
A
C
D
机房
E
老师
其中时间又有面授时间和上机时间之分
分别以单箭头左边的为行右边的为列建立两关系间的有效矩阵
A
、
B
、
D
，
由
A
B
得矩
阵
C
，再由
C
D
得矩阵
E,
确定其中的时间课程矩阵
B
为目标矩阵
,
以
A
、
C
、
D
影响矩阵为约束对目标矩阵进行修
改即可得所求的最优目标矩阵
B
，以
最
优目标矩阵
B
初排课表，
再根据修正矩
阵
E
对初排课表进行修正即可得最优排
课表。
2
，运用我们建立的模型，对
所给学校专业的课表进行了重排，并和现有的该专
业的课表进行了对比分析；
3
，通过我们建立的排课模型，综合优缺点分析
，对学校教务处排课表问题中出
现的问题给出合理的、可行性的建议
。
5-6
．模型的建立与求解
4.1
因为周末不安排上机，晚上可安排上机，所以一周有<
/p>
25
节课可以上机。
每节课序号如下
：
周一
周二
周三
周四
周五
1-2
节
1
6
11
16
21
3-4
节
2
7
12
17
22
5-6
节
3
8
13
18
23
7-8
节
4
9
14
19
24
9-10
节（晚上）
5
10
15
20
25
老师编号和班级编号如下：
老师编<
/p>
老师全天没
班级编
老师姓名
老师上机指导的班级
号
课
号
1
陈英
周
3
，周
5
材控
1103(35)
1
材控
1104(37)
2
物理
1101(31)
3
物理
1102(31)
4
2
丁胜
1,3
，
5
金材
1101(40)
5
金材
1102(41)
6
金材
1103(39)
7
土木
1101(29)
8
土木
1102(43)
9
土木
1103(42)
10
机工
1105(38)
11
机工
1106(38)
12
3
黄远林
5
安全
1101(34)
13
安全
1102(35)
14
安全
1103(34)
15
化工
1104(47)
16
化工
1105(46)
17
化工
1106(46)
18
采矿
1101(37)
19
采矿
1102(38)
20
4
王思鹏
5
张葵
6
廖建平
7
刘琼
8
田萍芳
采矿
1103(37)
环工
1101(35)
环工
1102(34)
3,5
矿加
1101(37)
矿加
1102(36)
矿加
1103(37)
交工
1101(33)
交工
1102(35)
交工
1103(33)
化工
1101(45)
化工
1102(47)
化工
1103(47)
材控
1101(37)
材控
1102(36)
2,5
机电
1101(36)
机电
1102(38)
机电
1103(38)
机电
1104(38)
3
人力
1101(44)
人力
1102(43)
社保
1101(30)
英语
1101(30)
英语
1102(28)
英语
1103(28)
行管
1101(36)
行管
1102(36)
社保
1102(29)
信息
（电专）
1101(34)
信息
（电专）<
/p>
1102(31)
1,3
法学
1102(31)
法学
1102(31)
德语
1101(35)
国贸
1103(36)
国贸
1104(37)
工商
1101(43)
工商
1102(44)
5
工管
1101(29)
工管
1102(30)
工管
1103(31)
会计
1101(40)
会计
1102(40)
会计
1103(41)
财务
1101(31)
财务
1102(30)
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
9
吴志祥
10
杨治
11
胡慧君
12
涂新辉
13
李琳
14
王磊
15
何亨
16
乔瑞
17
张志辉
18
欧阳琳
1,3
，
5
1,3
，
5
1,3
，
5
1,3
，
5
2,4,5
5
2,3,5
1,3
，
5
2,4,5
3,5
财务
1103(30)
建筑
1101(25)
建筑
1102(24)
建艺
1101(33)
装饰
(
专
)1001(41
)
土木
1104(41)
土木
1105(41)
无材
1101(43)
无材
1102(42)
无材
1103(43)
给排水
1101(36)
给排水
1102(36)
冶金
1102(29)
冶金
1103(30)
冶金
1104(33)
环设
1101(32)
环设
1102(32)
环设
1103(32)
车辆
1101
（产业）
(3
4)
车辆
1102(37)
土木
1106(42)
土木
1107(43)
冶金
1101(32)
冶金
1101
（英才）
(4
0)
给排水
1103(37)
给排水
1104(35)
工业
1101(40)
工业
1102(39)
机工
1101(40)
机工
1102(40)
交运
1101(36)
交运
1102(36)
营销
1101(36)
营销
1102(34)
英语
1104(30)
机工
1107(38)
机工
1108(38)
国贸
1101(38)
国贸
1102(35)
热能
1101(40)
热能
1102(40)
生物
1101(40)
城乡
1101(34)
车辆
1103(37)
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
4.2
以第一位老师为例，第一位老
师陈英课表如下：
陈英教师课表
星
期
星
期
星
期
星
期
一
二
三
四
一
二
三
四
计算机程
序设计基
础
计算机
程
序设计基
础
计算机程
序设计基
础
19
黄莉
20
余志兵
2,5
1,3
，
4
汽服
1101(38)
汽服
1102(38)
机工
1103(40)
机工
1104(40)
预防
1101(40)
预防
1102(40)
预防
1103(37)
药学
1101(34)
药学
1102(35)
临床
1101(44)
临床
1102(43)
临床
1103(43)
临床
1104(44)
临床
1105(44)
临床
1106(45)
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
星
期
五
五
六
计算机程
七
八
序设计基
础
九
十
老师有
课时不能指导学生上机，在一周
25
节课中老师没课改为
1
，有课改为
0
则第
一位老师的课表转换为
0-1
则得到：
陈英教师课表
星
期
星
期
星
期
星
期
星
期
一
二
三
四
五
一
二
1
1
1
1
1
三
四
1
0
1
0
1
五
六
七八
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
九
十
将表格
转换为一维数组有
25
列（对应
25<
/p>
节课）
，则
A1=(
11101
10111
11111
10011
11111 )
，同理第
二位老师的课表转换为
0-1
，则得到
A2=
（
11111 00011 11111 00011
11111
）
，
那么
< br>20
位老师是否有空指导学生上机组成了一个
20
行
25
列的矩阵
A<
/p>
，如下：
1
111110011
11111
11
10110111
1111100011
1111100011
11111
A
..........
..........
..........
..........
.....
..........
..........
< br>..........
..........
.....
1111100101
111111
1111
10111
< br>
4.3
同理将每个班级课表也转换为
0-1
变量，第一个老师教了
4
个班：材控
1103(35)
、材控
1104(37)
物理
1101(31)
、物理
1102(31)
。
第一个老师教的
4
个班组成
一个
4
行（按顺序对应
4
个班）和
25
列（对应
25
节课）的矩阵：
B
1
00111
00111
00011
< br>
00011
第二个老师教了
8
个班，
这
8
个班的的课表转换为
0-1
后组成一个
8
行
25
列的
矩阵：
B
2
<
/p>
1000100001
00111
00011
00111
001
11
00111
< br>
00111
00011
00011
同理可得
B3
，
B4
……
.B20
（
B20
为第
20
个老师所教的班组成的矩阵）
。
那么这
20
个老师教的
123
个班级组成一个
123
行
25
列的矩阵：
B
1
00111
B
2
< br>00111
B
< br>.....
.......
...
..........
..........
..........
.....
B
< br>20
1011100001
00011
<
/p>
4.4
只有老师和学生同时有空，学生
才能上机。矩阵Ａ１中１表示老师有空，Ｂ
１表示老师所教的班有空。由矩阵Ａ１和Ｂ１
可得矩阵Ｃ１。
矩阵Ｃ１表示老师和其所教的班级同时有空
A1=(
11101 10111 11111 10011
11111 )
B
1
<
/p>
00111
00111
00011
00011
所以
A1
和
B1
中的对应的元素同时为
1
是，<
/p>
C1
中相应的元素才为
1
，根据
VB
编程可得
C1
（见附表
1
）
，所
以
C
1
< br>
00111
<
/p>
00111
00011
00011
同理由
A2
，
B2
可得
C2
，
将
C1
，
C2
……
.C20
组成一个
123
行
25
列的矩阵，
得：
C
1
< br>
00111
< br>
C
2
00111
C
....
..........
..........
..........
..........
....
..
C
20
<
/p>
00011
<
/p>
5.5
确定约束条件
设
x
是一个
123
行
25
列的矩阵
1
(
第
i
个班在第节
j
课有空<
/p>
)
x
ij
0
i
个班在第
j
课没空）
（第
一周
25
节课中每个班只需要一个老师指导一次，
所以矩阵每行中只需要一个
1
，
约束条件（
1
）如下
25
j
1
x
< br>ij
1
(
i
1
,
2
,
3
,
4<
/p>
,
5
.......
123
)
只有当老师学生同时有空时才能上机：
25
<
/p>
x
j
1
ij
c
ij
1
(
i
1
,
2
,
3
,
4
,
5
......
123
)
根据假设在同一时间最多只有
10
个班课以上机，即
x
ij
的每列之和小于等于
10
123<
/p>
i
1
x
ij
10
(
j
1
,
2
,
3
,
4
......
25
)
5.6
确定目标函数
第一位老师周三周五全天没课，即第
11
到
15
节，
20
到
25
节没课，
i
为
1,2,3,4
表示第一个老师指导标号为
1,2,3,4
的
4
个班上机，所以<
/p>
12
25
令<
/p>
m1=
x
ij
j
6
x
j
20
ij
(i=1,2,3,4)
第二位老师周一周三周五全天没课，
i
为
5,6,7,8,9,10,11
,12
表示表示第二个老师
指导标号为
5,6,7,8,9,10,11,12
的
8
< br>个班上机
5
15
25
ij
令
m2=
x
ij
j
1
x
j
11
+
x
j
20
ij
(i=6,7,8,9,10,11,12)
以此类推，可得
m3,m4
……
m20.
因为在
lingo
中
@s
ign
表示当
x<0
时返回
-1
，
x>=0
返回
1
所以令
M=
sign(-mi)+sign(-m2)+
……
..+sig
n(-m20)
因为
m1
为
0
或
1
，在其前加一
个负号，所以
-m1
取
0
或
-1
，再用数值函数，可
得目标函数：
max=M
(
即老师全天没课时尽可能不来指导上机
)
7
．模型的推广与评价
优点：
1
，
用
0-1
规划解决相互约束问题。形成“时间段
-
课程
-
教师
-
机房“组合，科学
合理；
2
，逐步优化，层层递进，思路清晰，简单易懂；
3
，本模型充分考虑教师、学生和学校的满意度要
求，课表的设置更加合理和人
性化；
4.
本模型在建立过程中对上课时间巧妙赋值，将实际问题数值化。
缺点：
本模型在建立时，
未考虑单双周排课问题，
若把此因素加以考虑，
将
使模型更加
的完整。
8
．参考文献
[1]
姜启源，谢金星，叶俊
.
数学模型（第三版）
.
北京：高等教育出版
社
2008.
[2]
雷英杰，<
/p>
MATLAB
遗传算法工具箱及应用，西安电子科技大学出版社，
2005
[3]
林志雄，排课数学
模型及其算法，龙岩学院学报第六期，
2006
年
12
月。
附录一：
VB
编程代码
Private Sub command1_click()
Dim a(25), b(25), c(25)
X1 = Replace(,
X2 =
Replace(,
q = Len(X2)
Print Len(X2)
For k = 0 To q 25 - 1
Print Len(X2)
h
= 25 * k
For i = 1 To 25
a(i) = Mid(X1, i, 1)
b(i) =
Mid(X2, i + h + 2 * k, 1)
a(i) = V
al(a(i))
b(i) = V
al(b(i))
c(i) = a(i) * b(i)
n = n + 1
Print c(i);
9.
附录：
Next
Print
Next
End Sub
输入数据得到的结果：
老师
01
11101 10111
11111 10011 11111
学生
00101 00111
01101 01011 00111
00101 00111 01101
01011 00111
00011 00011
00011 00111 00011
00011 00011 00011
00111 00011
00001 00111
01101 00011 00111
00101 00111 01101
01011 00111
00001 00011 00011 00011
00011
00001 00011 00011 00011 00011
老师
02
11111 00011 11111 00011 11111
学生
00011 00011
01101 00011 00111
00011 00011 01111
00011 00011
00011 00011 01101 00011
00111
00101 00011 00001 00011 00111
00001 00011 00011 00011 00111
00001 00011 00011 00011 00111
00001 00001 00111 00011 00011
10001 00001 00111 00001 00011
老师
3
01111 00011 11011 00011 11111
学生
00011 00111
00111 00111 00001
01011 01011 00111
00111 00011
01011 00101 00111 00111
10011
00011 00011 00011 00011 00011
00011 00011 00011 00011 00011
00011 00011 00011 00011 00011
01011 00111 10011 01001 00111
11011 00011 10011 00101 00111