课程表安排的优化模型

一类课表安排的优化模型

xxx

（XXX大学理学院应数班 贵阳 550025）

摘 要：本文采用逐级优化、0-1规划的方法，考虑多重约束条件，引入了偏

好系数，建立了一个良好的排课模型，并根据题目给的数据，通过MATLA B编程，进行模型验证，求出了所需课表。且在方案合理性分析中用计算机模拟的方法分析了偏好系数的变化、教室的种类对排课结果的影响。最后给出了教师、教室的最优配置方案。

关键词：逐级优化；0-1规划；多重约束条件；排课模型

1.问题提出

用数学建模的方法安排一个贵州民族学院理学院合理的课表，尽可能让老师和学生都满意。让老师满意，就是要让每位家住贵阳和花溪的老师在一周内前往上课的天数尽可能少（家住民院的老师前往学院的次数尽可能少），同时还要使每位老师在学校逗留的时间尽可能少（家住贵阳和花溪的老师每天最多往返学校一次），比如安排尽量少出现像同一天同一位老师上1-2节，7-8节；让同学们满意，可从以下几方面考虑，比如，同一班级同一门课程，至少应隔一天上一次，另外对学生感到比较难学的课程尽量安排在最好的时段。 用数学建模的方法解决以下问题：

1) 建立排课表的一般数学模型；

2) 利用你的模型对本学期我院课表进行重排，并与现有的课表进行比较； 3) 给出评价指标评价你的模型，特别要指出你的模型的优点与不足之处；

4) 对学院教务处排课表问题给出你的建议。

2.问题分析

在学校的教务管理工作中，课程表的编排是一项十分复杂、棘手的工作。排课需要考虑时间、课程、教学区域、教室、院系、班级、教师等等因素。经优化的排课，可以在任意一段时间内，教师不冲突，授课不冲突，授课的班级不冲突，教室占用不冲突，且综合衡量全校课表在宏观上是合理的。如何利用有限的师资力量和有限教学资源，排出一个合理的课程安排结果，对稳定教学秩序、提高教学质量有着积极的意义。 某高校现有课程50门，编号为c01~c50；教师共有48名，编号为t01~t48；教室28间，编号为r01~r26。具体属性及要求见附录1； 课表编排规则：每周以5天为单位进行编排；每天最多只能编排10节课，上午4节，下午4节，特殊情况下可以编排10节课，每门课程以2节课为单位进行编排，同类课程尽可能不安排在同一时间。比如安排尽量少出现像同一天同一位老师上1-2节，7-8节；让同学们满意，可从以下几方面考虑，比如，同一班级同一门课程，至少应隔一天上一次，另外对学生感到比较难学的课程尽量安排在最好的时段。

本题的目标是将所有课程按照一定的约束条件安排到时间表中。 由于总周

课时数为700，最少需要14张时间表。根据假设，学校要将其全部编排，则目标是排出14张课程表。假设14张表同时上课，那么要求教师不冲突、教室不冲突、课程全部排完以及所有软、硬约束。 由于目标是将所有课程排完，可以先将不同课程按照其时间要求随机分配至时间表中，形成“时间段-课程”组合；再建立该组合对教师的约束，通过“0-1规划”确定最优的“时间段-课程-教师”组合；同理，确定出“时间段-课程-教师-教室”的最优组合，最终得到所求课表。

3.模型的建立

3.1 模型假设

1.假设学校的目标是将课程全部编排；

2.假设所编排的课程表是学生自选型，不考虑班级或上课人数； 3.假设在课程要求中的各项均为强制要求，即“硬约束”；

4.假设在教师属性中，能胜任课程类别、周最大课时数为强制要求，即“约 束”；对教室类别要求、上课时间要求用偏好程度衡量，为“软约束”； 5.假设所得14张课表中2张同时上课，上完后另外2张课表开始上课； 6.假设课表内容由上课时间、教师、教室、课程组成。

3. 2 符号说明

A1A2A3A4A5 :效用矩阵 ; tk :教师编号 ;

ru :教室编号 ;

ci

:课程编号 ;

 :偏好系数，表示教师对教室、教师对上课时间的偏好系数;

si :课程表上时间段的编号 ; stk

:为ci课程的要求课时数 ;

sci :为tk教师的要求课时数 ;

siyj,tk,ru :课程表上某一时间段的课程-教师-教室组合 ;



i



3．3 模型的准备与初步建立：

3．3.1 模型的准备

1.根据分析，关联关系有教师—教室、教师—课程、教师—上课时间、课程—教室、课程—上课时间一共五个。

图1 关联关系示意图

（实线表示“硬约束”，虚线表示“软约束”）

依次建立A1,A2,,A7七个效用矩阵。其中，为强制约束的有A2,A4,.

A1 矩阵：

A1aij

（刻画 i教师上

j 教室的偏好效果指标）其中：0aij1;

A2 矩阵：

A2aij（刻画i 教师上j 课程时的效果指标）其中：aij0,1

A3 矩阵：

A3aij

（刻画i教师上

其中:0aij1 j时间段上课时的偏好效果指标）

A4 矩阵：

A4aij（刻画i 课程在j教室上时的效果指标）其中：aij0,1

偏好约束有A1、A3。 2. 时间段si 的编号:

每一张课表上有星期一到星期五，每天有5 个时间段（每两个课时算一个时间段）。根据假设，假设题目需要同时排十四张课程表，需要对十四张课程表上的时间段都进行编号:

表1 时间段编号

3.对课程的处理

当某一课程的课时数为奇数时，取大于他的最小偶数。对所有课程的课时数进行调整。新的课时数为ki（i1,2,48,即为48 位教师），原课程编号为ci

（i1,2,50），yij（i表示原课程的编号，j1,2, ），待排课程集合为yij. 3．3.2 模型的初步建立

第一步 ：随机分配课程到各个时间段

当课程的上课时间（上下午）要求为强制性约束时，分别选出上下午的课程集合

B上午y1yj



1i

,B

下午

y1yj..我们随机 给B上午中的每一个元素抽取一个上



2i



午的时间段，其中满足的条件是，给B下午中的每一个元素抽取一个下午的时间段。组成

时间段—课程siyij组合。此时， siyij（某一时间段对应的某一课程）。 如此，完成随机分配，使得每个时间段编号都有一个课程赋值。

第二步 ：根据教师tk 对si 时间段上的课程所要求的教室的偏好A1矩阵，对si 进行次赋 值，sisiaij.

s11  s1i

  s  s

kik1

 

最终得到ski

第三步 ： 0-1 规划

1．目标是将tk 教师分配到不同的时间段上，约束条件是分配结果必须满足教师的课时数要求。

因此，问题转化为求有约束条件的0-1 规划问题。 目标函数：

n

n

ki

max Z

s

k1i1

xki

约束条件：

n

xkiSTk/2i1n

xkisci/2

k1

xki0,1

所得解为：

x11 x12  x1i

x21 x22  x2i

X

  

x x  x

kik1k2

 

将教师安排到最优的时间段，此时siYji,Tk若无最优解，重回步骤一。

2．为每一个时间段安排教室

Ru教室对Si这一时间段的效果指标

该时段的老师对教室的

该时段课程对教室的效

偏好果指标

.

3．结合效用矩阵A4 的Si

根据si 时段课程ci 对教室Ru 的效果矩阵A4，对si 进行第一次赋值，若

aij1,则si1，否则，si0。

4．结合效用矩阵A1 的Si

根据si 时段教师Tk 对教室Ru 的效用矩阵A1，对si 进行第二次赋值，

sisiaij

最终得到：

s11  s1i

s  

s  s

uiu1

 

第四步 再次使用0-1 规划

目标是将Ru 教师分配到不同的时间段上，约束条件是分配结果必须满足同一间教室在四张课表的同一时间段不重复。因此，问题转化为求有约束条件的0-1 规划问题。 目标函数：

n

n

ui

max Z约束条件： 

s

u1i1

xui

x11x16x11x161

xx26x31x36121x41x46x51x561



 

 xui0,1

所得解为：



x11 x12  x1i

x21 x22  x2i

X

  

x x  x

uiu1u2



将教室安排到最优的时间段，此时siYji,Tk，Ru若无最优解，重回步骤一。 6.1.4 安排课程表

将每个si 的组合按照其编号读入到表1 中，得到最后的课程表。具体课表见附录二。

4.模型的求解

充分考虑课程的时间要求（上午,下午或晚上），随机分配课程，得到“时间段-课程”组合。分配示例见附录一。 由于，题目所给数据中，教师的总课时数小于课程总课时数，又经过计算，设定目标是为做成十四张课表，其中两张先行开课，上完后，另外再两两开课。利用0-1 规划求解，构造要用矩阵时，要考虑的是，教师对这一事件的偏好，每位家住贵阳和花溪的老师在一周内前往上课的天数尽可能少，同时还要使每位老师在学校逗留的时间尽可能少，同一班级同一门课程，至少应隔一天上一次，另外对学生感到比较难学的课程尽量安排在最好的时段等因素，利用excel 构造出效用矩阵。用LINGO软件求解线性规划模型的过程详见见附录三。

5. 模型的评价与分析

5．1合理性分析：

模型充分考虑了课程、教室、教师等的相互约束，建立了关系关联，并对约束采用0-1规划，确定出 “时间段-课程-教师-教室”组合。同时，我们也充分考虑了教师对教室和上课时间的偏好，建立了一个偏好系数可调的模型，使所得课表尽量满足课程、教室、教师的各种属性及要求，对教师聘用，教室配置给出合理化建议。

5．2模型的评价：

第一．模型的优点：

⒈引入了偏好系数β，能较大程度地满足教师、课程和教室的要求； ⒉建立了关联关系，使模型建立更清晰、明确、具有条理性；

⒊用0-1规划解决相互约束问题，形成“时间段-课程-教师-教室”组合，科学合理；

⒋逐步优化，层层递进，思路清晰，简单易懂。

⒌充分考虑各个教师、教室、课程的要求，具有良好实用性。

以上总结的内容不可能是生产分配研究方法与策略的全部,但愿它能起到敲门砖的作用, 带领更多的有志踏入研究之门. 第二．模型的缺点：

⒈当课时数为奇数时，将其近似为偶数计算，导致课表中所有时间未能充分利用；

⒉在随机给每个时间段安排课程时，未能确立完善的分配方式；

参考文献：

[1] 姜启源、谢金星、叶俊,数学模型（第三版）[M]，北京：高等教育出版社,2003。 [2] 郭耀煌等，运筹学[M]，四川：西南交通大学出版社，2000。 [3] 薛秀谦、朱开永，运筹学[M]，徐州：中国矿业大学出版社，2002。 [4] 韩中庚，数学建模方法与应用[M]，北京：高等教育出版社，2005。 [5] 徐玖平、胡知能，中级运筹学[M]，北京：科学出版社， 2008。

[6] 张小红、张建勋，数学软件与数学实验[M]，北京：清华大学出版社，2004。

[7] 邓集贤、杨维权、司徒荣、邓永录，概率论与数理统计（第四版）[M]，北京：高等教育出版社,2009。

[7]刘卫国. MATLAB程序设计教程[M].北京: 中国水利水电出版社,2005.

[9] 欧阳光中、朱光炎、金福临、陈传璋，数学分析上册（第三版） [M]，北京：高等教育出版社,2007。

[10]王夏林，概率论与数理统计 [M]，西安：西北工业大学出版社,2002。

附录

附录一：

课程、教师、教室（ c01~c50，t01~t48，r01~r26）分别为：

11

附录二： 具体课表为：

星期一 ： 星期二; 星期三;

12

13

星期四 ： 星期五;

14

15

附录三 程序代码： model:

sets:

teacher/ @file('偏好0.1.txt') /:teacheryaoqiu; kecheng/ @file('偏好0.1.txt') /:kechengyaoqiu; links(teacher,kecheng):c,x; endsets data:

teacheryaoqiu=@file('偏好0.1.txt') ; kechengyaoqiu=@file('偏好0.1.txt') ; c=@file('偏好0.1.txt') ; enddata

max=@sum(links:c*x);

@for(kecheng(j):

@sum(teacher(i):

x(i,j))=kechengyaoqiu(j)); @for(teacher(i): @for(links:@bin(x)); End

@sum(kecheng(j):

x(i,j))

16