正文
- 格式：doc
- 大小：1.14 MB
- 文档页数：21
1
一． 问题重述
每学期的开学初，总有许多老师对对渭水校区的课程安排进行抱怨，还有许多老师要求调课，教务处对这一问题很是头疼。假设你是一名刚刚毕业的大学生，被分配到了长安大学教务处，领导安排你负责排出渭水校区的课表，请你们根据长安大学的实际情况，用数学建模的方法解决这一问题，既要让老师满意，又要让同学和学校满意。
让老师满意，就是要让每位老师在一周内前往渭水上课的乘车次数内尽可能少，同时还要使每位老师在渭水逗留的时间尽可能少，比如安排尽量少出现像同一天同一位老师上1-2节，7-8节；让同学们满意，可从以下几方面考虑，比如，同一专业同一门课程，至少应间隔一天上一次，另外对学生感到比较难学的课程尽量安排在最好的时段；让学校满意，就是要节约支出，每周派往渭水的车次尽可能的少。
请你们从长安大学的实际情况出发(自己收集相关数据)，用数学建模的方法解决以下问题：
1)建立排课表的数学模型，并研制出排课表的软件包；
2)利用你的模型及软件对本学期渭水校区的课表进行重排，并与现有的课表
进行比较；
3)给出评价指标评价你的模型，特别要指出你的模型的优点与不足之处；
4)对学校教务处排课表问题给出你的建议。
二．基本假设
1、课程对于教室的要求都一样，不存在特定课程对应特定教室的现象;
2、老师与工作人员的满意度与到渭水校区的次数有关，与课程安排的教室
位置无关;
3、教室足够多,不存在教室不够用的情况；
4、周一至周五每天上四节课；
2
5、对于任一专业，某门课程一周内的授课时间数（节数）是固定的，即不
考虑单双周情况；
6、教室足够大，相同专业在一起上课，共用一个课表；
7、每辆校车最多乘坐50人；
8、校车每天开四次，即每次上完课都有校车发车；
9、校车在规定时间到达乘车点后，所有人员应在该点上车的乘客均上车,
校车为满员状态，不考虑校车单独去接个别人员的情况。
三.符号约定
X 时间集合
Xa 第a个时间段
δ 每周上课时间
Y 老师集合
Yb 第b位老师
β 老师总数
Z 专业集合
Zc 第c个专业
α 专业总数
R 教室集合
Rγ 第γ间教室
L 课程集合
Lε 第ε门课程
DepCost(j) j班相同课程的时间间隔度量值之和
PriCost(j) j班课程重要度度量值之和
3
ReqCost(j) j班上课老师的要求与课程安排符合程度度
f(x) 适应度函数
x 决策向量
y 目标向量
e（x） 约束条件
Xi（i=1,2,3…20） 每周内第i节课
Pc 交叉概率
Pm 变异概率
num 随机整数
F 效用函数
g（a） 校车数量函数
G 一周内学校派往渭水的校车总数
四．问题分析
1、让老师满意
让老师满意，就是要让每位老师在一周内前往渭水上课的乘车次数内尽可能少，同时还要使每位老师在渭水教学时间尽可能的集中，比如安排尽量少出现同一天同一位老师上1-2节，7-8节。
首先对老师满意度进行定义，用符号Req表示老师满意度，其值越高，老师对所排课表越满意。若某课程的上课时间完全符合老师要求，如老师希望将课程安排在上午第一节，课表情况亦如此，则Req=10；
如果课表安排与老师要求不符合，但同为上午或下午，则Req=5；其他情况，Req=0。
2、让学生满意
让同学们满意，可从以下几方面考虑，比如，同一专业同一门课程，至少应间隔一天上一次，另外对学生感到比较难学的课程尽量安排在最好的时段。
4
关于同一门课的排课满意度，为某班相同课程两次课之间的时间间隔赋权值，权值越大，满意度越高。如表1所示。
间隔 权值
同一天 0
相邻两天，间隔时间段≤两节课 4
相邻两天，间隔时间段>两节课 6
间隔一天 10
间隔一天以上 6
表1 某班同一门课程时间间隔权值
根据上课时间的不同为重要度赋权值。如表2所示。
周一 周二 周三 周四 周五
第一节 9.5 9.9 9.7 9.4 9.2
第二节 8.5 8.9 8.7 8.4 8.2
第三节 6.5 6.9 6.7 6.1 6.2
第四节 5.5 5.9 5.7 5.1 5.2
表2 一周内每节课的权值
对于比较难学的课，排课表时优先排，以保证能尽量安排在最好时间段。
3.让学校满意
让学校满意，就是要节约支出，每周派往渭水的车次尽可能的少。
相比于让老师满意和让学生满意，让学校满意问题中出现了最低成本，即校车数量最少，这样多目标调度问题就变成了模型优化问题。在“满意度”和“最低成本”这两个变量中建立相关关系，共同评定，求出最优解。
考虑到以上三方面问题，采用遗传算法，得出最优个体，然后考虑让学校满意，对问题进行优化。基本思路如图1
5
图1：基本思路
五.模型建立、算法及求解
问题的本质是将课程、老师和学生在合适的时间段内分配到合适的教室中，是一个多因素的整体优化问题。
模型的主要任务是将专业、教室、课程、老师安排在一周内且不发生时间冲突。并且尽量做到人性化，最大可能的使学生、老师、学校满意。为此，我们采Y 考虑
成本 N 班级、课程、老师、时间
随机
初始种群
适应度评估
是否符合最优化解 输出最佳个体
选择
交叉
变异 新种群 车辆数
平均满载率 效用函数
6
用遗传算法对学生和老师做排列，输出满意度较高的个体，然后考虑进校车数量等经济性因素，建立效能函数，对目标进行最终优化。
5.1 遗传算法
遗传算法采用类似基因演化的循环过程，其演算过程如下：
1）随机产生一定数目的初始种群；
2）对个体适应度进行评估，如果个体的适应度符合优化准则，则输出最佳个体及其代表的最优解，并结束计算，否则转向第三步；
3）依据适应度选择再生个体；
4）按照一定的交叉概率和交叉方法生成新的个体；
5）按照一定的变异概率和变异方法生成新的个体；
6）由交叉和变异产生新一代的种群，然后返回第2步。如图2所示：
图2：遗传算法示意图
5.2 模型建立
以下分析是在不考虑学校满意度的基础上进行的
5.2.1 约束条件
排课的硬约束条件：
在时间和空间上根据不同的约束条件进行排列组合,以使教学正常进行。
一张课表是有效的,则它至少应该满足以下硬约束条件:
1) 教师不能冲突,同一教师在同一时间不能教授两门课程；
2) 教室不能冲突,同一教室在同一时间不能安排两门课程；
7
3) 专业不能冲突,同一专业在同一时间不能安排两门课程。
排课的软约束条件：
为了尽可能的提高老师、学生、学校的满意度，模型还应考虑以下软约束条件:
1)专业课表在星期上分布尽量均匀；
2)对于同一老师，每天上课时间应该相对集中，尽量避免同一天上下午均上
课的情况；
3)同一专业同一门课程，至少应间隔一天上一次，另外对学生感到比较难学
的课程尽量安排在最好的时段；
4)同一课程的多个课时段要保持一定的时间间隔；
5)学校每周派往渭水校区的班车尽可能少，即平均满载率尽可能高。
可以认为，在符合约束条件的情况下，能最大限度满足要求的课表安排方案是优良的。
5.2.2 建立一般模型
对排课问题建立以下模型：
其中，
这里的x表示决策向量即时间、专业、老师因素, y表示目标向量即个体适应度, X表示决策向量x 形成的决策空间, Y表示目标向量y 形成的目标空间,约束条件e(x) 确定决策向量可行的取值范围。
方案一：采用三维编码的方式
如图所示三维坐标系，X轴为时间轴，每个时间坐标对应一个时间间隔。如X1、X2分别代表周一上午第一、二节课。以一周五个工作日、每个工作日四个时间段计，共有20 个坐标值（X1~X20）。Y 轴每一轴代表一位老师。Z 轴每一间隔代表一个专业。
8
三维坐标可以确定一个小方块。其值定义如下：
假设每个老师只教一门课，则Y轴同时也表示课程。
同时，为了保证解的可行性，做以下约束e (xi)：
约束一：如果Y 坐标和Z 坐标确定，则 应与Y老师在一周内给Z 班上课次数相同。
约束二：如果Y 坐标和X 坐标确定，则
约束三：如果X坐标和Z坐标确定，则
采用遗传算法，并定义个体适应度为：
选择算子：
9
为各个个体的新适应度，用赌盘选择法随即确定下一代群体中还未确定
的个体。
交叉算子：交叉概率Pc取0.4～0.99。如下图，以垂直Z轴的面将个体切割，交换两个个体的阴影部分。这样一来就能保证新个体满足编码约束一的要求，而且每个班的适应值不变但个体适应值改变，算法容易收敛
变异算子：变异概率Pm取0.0001～0.1。
变异算子实现如下：
第一步：产生0—1 之间随机数num1，判断是否需要变异。如果num1
第二步：产生1—20之间随机整数num2、num3（num2≠num3）交换X坐标分别为num2和num3，而Y 、Z 坐标相同的基因块值。
很明显，经过这样变异的个体不会冲突，但个体适应值有所变化。由于个体的编码和适应值可以变化，从而提高了局部搜索能力。
另外，每条染色体用以代表每位教师的课表，其结构表示如下：
（教师ID，专业ID，课程ID，教室编号，上课时间）
在算法设计时，染色体采用十进制数编码，例如：某一老师ID为0011，要教授课程编号为0001 的“高等数学”这门课，周学时为4，专业为2101，随机产生上课时间和教室，则可生成染色体如下：
“0011，2101，0001，01102，3251”
其中01102代表教室编号（即明远1号楼102室），3251中32代表上课时间星期
