一．问题重述
每学期的开学初，总有许多老师对课程安排进行抱怨，还有许多老师要求调课，教务处对这一问题很是头疼。假设你是一名刚刚毕业的大学生，被分配到了教务处，领导安排你负责排出课表，请你们根据实际情况，用数学建模的方法解决这一问题，既要让老师满意，又要让同学和学校满意。
让老师满意，就是要让每位老师在一周内前往上课的乘车次数内尽可能少，同时还要使每位老师在逗留的时间尽可能少，比如安排尽量少出现像同一天同一位老师上1-2节，7-8节；让同学们满意，可从以下几方面考虑，比如，同一专业同一门课程，至少应间隔一天上一次，另外对学生感到比较难学的课程尽量安排在最好的时段；让学校满意，就是要节约支出，每周车次尽可能的少。
请你们从实际情况出发(自己收集相关数据)，用数学建模的方法解决以下问题：
1)建立排课表的数学模型，并研制出排课表的软件包；
2)利用你的模型及软件对本学期校区的课表进行重排，并与现有的课表进行
比较；
3)给出评价指标评价你的模型，特别要指出你的模型的优点与不足之处；
4)对学校教务处排课表问题给出你的建议。
二．基本假设
1、课程对于教室的要求都一样，不存在特定课程对应特定教室的现象;
2、老师与工作人员的满意度与到校区的次数有关，与课程安排的教室位置无关;
3、教室足够多,不存在教室不够用的情况；
4、周一至周五每天上四节课；
5、对于任一专业，某门课程一周内的授课时间数（节数）是固定的，即
不考虑单双周情况；
6、教室足够大，相同专业在一起上课，共用一个课表；
7、每辆校车最多乘坐50人；
8、校车每天开四次，即每次上完课都有校车发车；
9、校车在规定时间到达乘车点后，所有人员应在该点上车的乘客均上车,校车为满员状态，不考虑校车单独去接个别人员的情况。
三.符号约定
四．问题分析
1、让老师满意
让老师满意，就是要让每位老师在一周内前往上课的乘车次数内尽可能少，同时还要使每位老师在教学时间尽可能的集中，比如安排尽量少出现同一天同一位老师上1-2节，7-8节。
首先对老师满意度进行定义，用符号Req表示老师满意度，其值越高，老师对所排课表越满意。若某课程的上课时间完全符合老师要求，如老师希望将课程安排在上午第一节，课表情况亦如此，则Req=10；
如果课表安排与老师要求不符合，但同为上午或下午，则Req=5；其他情况，Req=0。
2、让学生满意
让同学们满意，可从以下几方面考虑，比如，同一专业同一门课程，至少应间隔一天上一次，另外对学生感到比较难学的课程尽量安排在最好的时段。
关于同一门课的排课满意度，为某班相同课程两次课之间的时间间隔赋权
值，权值越大，满意度越高。如表1所示。
根据上课时间的不同为重要度赋权值。如表2所示。
对于比较难学的课，排课表时优先排，以保证能尽量安排在最好时间段。
3.让学校满意
让学校满意，就是要节约支出，每周派往的车次尽可能的少。
相比于让老师满意和让学生满意，让学校满意问题中出现了最低成本，即校车数量最少，这样多目标调度问题就变成了模型优化问题。在“满意度”和“最低成本”这两个变量中建立相关关系，共同评定，求出最优解。
考虑到以上三方面问题，采用遗传算法，得出最优个体，然后考虑让学校满意，对问题进行优化。基本思路如图1
图1：基本思路
五.模型建立、算法及求解
问题的本质是将课程、老师和学生在合适的时间段内分配到合适的教室中，是一个多因素的整体优化问题。
模型的主要任务是将专业、教室、课程、老师安排在一周内且不发生时间冲突。并且尽量做到人性化，最大可能的使学生、老师、学校满意。为此，我们采用遗传算法对学生和老师做排列，输出满意度较高的个体，然后考虑进校车数量
等经济性因素，建立效能函数，对目标进行最终优化。
5.1遗传算法
遗传算法采用类似基因演化的循环过程，其演算过程如下：
1）随机产生一定数目的初始种群；
2）对个体适应度进行评估，如果个体的适应度符合优化准则，则输出最佳个体及其代表的最优解，并结束计算，否则转向第三步；
3）依据适应度选择再生个体；
4）按照一定的交叉概率和交叉方法生成新的个体；
5）按照一定的变异概率和变异方法生成新的个体；
6）由交叉和变异产生新一代的种群，然后返回第2步。如图2所示：
图2：遗传算法示意图
5.2 模型建立
以下分析是在不考虑学校满意度的基础上进行的
5.2.1 约束条件
排课的硬约束条件
在时间和空间上根据不同的约束条件进行排列组合,以使教学正常进行。
一张课表是有效的,则它至少应该满足以下硬约束条件:
1) 教师不能冲突,同一教师在同一时间不能教授两门课程；
2) 教室不能冲突,同一教室在同一时间不能安排两门课程；
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 轴每一间隔代表一个专业。
