一．问题重述每学期的开学初，总有许多老师对课程安排进行抱怨，还有许多老师要求调课，教务处对这一问题很是头疼。
假设你是一名刚刚毕业的大学生，被分配到了教务处，领导安排你负责排出课表，请你们根据实际情况，用数学建模的方法解决这一问题，既要让老师满意，又要让同学和学校满意。
让老师满意，就是要让每位老师在一周内前往上课的乘车次数内尽可能少，同时还要使每位老师在逗留的时间尽可能少，比如安排尽量少出现像同一天同一位老师上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 轴每一间隔代表一个专业。
三维坐标可以确定一个小方块。
其值定义如下：错误！未找到引用源。
错误！未找到引用源。
假设每个老师只教一门课，则Y轴同时也表示课程。
同时，为了保证解的可行性，做以下约束e (xi)：约束一：如果Y 坐标和Z 坐标确定，则应与Y老师在一周内给Z 班上课次数相同。
约束二：如果Y 坐标和X 坐标确定，则约束三：如果X坐标和Z坐标确定，则采用遗传算法，并定义个体适应度为：选择算子：为各个个体的新适应度，用赌盘选择法随即确定下一代群体中还未确定的个体。
交叉算子：交叉概率Pc取0.4～0.99。
如下图，以垂直Z轴的面将个体切割，交换两个个体的阴影部分。
这样一来就能保证新个体满足编码约束一的要求，而且每个班的适应值不变但个体适应值改变，算法容易收敛变异算子：变异概率Pm取0.0001～0.1。
变异算子实现如下：，执第一步：产生0—1 之间随机数num1，判断是否需要变异。
如果num1<pm行第二步，否则，保留该个体。
第二步：产生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代表教室编号，3251中32代表上课时间星期三第二个教学单元（即上午3-4节），51代表星期五第一个教学单元（即上午1-2节）。
案例：基于以上算法，对一个学院进行模拟算例数据：Z——专业集合｛01,02,03,04,05,06,07｝Y——老师集合｛01,02,03,04,05,06,07,08,09,10,11,12,13,14,1516,17,18,19,20,21,22,23, 24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40｝L——课程集合｛01,02,03,04,05,06,07,08,09,10,11,12,13,14,15，16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43｝运行参数：{M，T，Pc ，Pm}={645，8000，0.5，0.05}运行结果：下图为某一次进化过程中，最高适应值和平均适应值的变化曲线。
可见，收敛性较好。
如下为部分课表信息：“01，01，01，12301，34”“02，01，02，01201，14” “03，01，03，14102，33” “04，01，04，11306，54” “05，01，05，14203，41” “06，01，06，11110，44” “07，01，07，14204，2324” “08，01，08，14103，1231” “09，01，09，01204，11” “10，01，10，04303，2132” “11，01，11，11203，53” “12，02，12，01301，3221” “13，02，13，01105，44” “02，02，01406,21” “14，02，13，01506，5123”“36，07，18，11102，5433” “37，07，37，01507，34” “38，07，38，13202，14” “39，07，39，11402，2142” “40，07，40，11307，1432”专业一课表如下：考虑学校满意度：问题转变成在满意度与成本之间的优化建立模型：F=0.6f(x) +4g(x)/G该函数表明，g（x）越大即同一时间段来学校的老师越多，所排课程越好，也从侧面说明了对于比较好的时间段，学校要尽可能多的安排老师来上课，从而保证了学生的满意度。
G越小每周所派校车数目最少，说明平均满载率越高，保证了学校的满意度。
F最大时即为最优解，所排课程最好。
如下为部分课表信息：“01，01，01，12301，34”“02，01，02，01201，13”“03，01，03，14102，33”“04，01，04，11306，52”“05，01，05，14203，41”“06，01，06，11102，44”“07，01，07，14204，2342”“08，01，08，14103， 1231”“09，01，09，01204，11”“10，01，10，14303，2132”“11，01，11，11203，22” “12，02，12，01302，1332” “13，02，13，14101，32” “02，02，02，11204，23” “14，02，14，01403，1442”“36，07，36，11303，2241” “37，07，37，01504，43” “38，07，38，14304，33” “39，07，39，03202，52” “40，07，40，13304，3251”专业一的课程经过优化如下：最终我们排好的实际课表如下：和学校现行的课表：相比之下我们的算法排出来的课表1．时间主要相对集中在周一到周四，安排在周五的课只有一节，这样同学就可以享受一个相对较为宽松的周末。