定制学生课表数学建模初赛.pdf

北京工业大学北京工业大学 数学建模竞赛初赛数学建模竞赛初赛 论文论文 所选题目：所选题目：B B 题：定制学生的课表题：定制学生的课表 小组成员：柏鳗晏小组成员：柏鳗晏 1407312414073124 计算机学院计算机学院 柳丹彤柳丹彤 1407311414073114 计算机学院计算机学院 李双记李双记 1407310414073104 计算机学院计算机学院 20162016 年年 4 4 月月 5 5 日日 1 目录目录 1 摘要.2 2 问题的重述.2 3 问题的假设.3 4 模型的建立.3 1、符号说明.3 2、硬约束条件简述.3 3、软约束条件简述. .4 4、 数学描述.4 5、 硬约束条件描述.4 6、 软约束条件描述.5 5 问题的求解与分析. 5 6 模型的评价. .6 1、模型的优点.6 2 、 模型的缺点.6 3、模型的改进.7 7结论.7 8参考文献.7 附录一 附录二 2 一、摘要一、摘要 在学院教务处的实际工作中， 编排课程表是教务管理中一项非常重要且非常 复杂麻烦的工作。 不仅需要考虑上课时间、 课程、 教师、 每周所需安排课程数量、 每天最大课时数等因素，还要满足部分课程由于自身属性所提出特殊要求，同时 在排课过程中还要尽量照顾师生对课时安排的需求。 本文对此类问题进行研究和讨论，将排课问题建立成数学模型，根据多重约 束条件的关系，运用遗传算法，提出课程编排的优化解决方案。 首先根据课程编排的不同要求，将多重约束条件分为硬约束和软约束，并根 据每条约束列出相应表达式，以满足课程、教师以及学生的多重需求。最后，通 过求解表达式，得到尽可能优化的课程表编排方案。 本文采用多重约束列式和遗传算法优化，形成了一个完整的数学模型，通过 lingo 建模，编排出较为优化的课程表。所建立的数学模型给出了课程表编排的 最优结果，并例举出了两个根据条件所编排出的课程表。最后，本文对该解决方 案分析了优缺点，并设想了改进条件及实现思路。 【关键词】 ：课程编排，遗传算法，约束，组合优化 二、问题重述二、问题重述 某学院在教务管理工作中需要对两个班级的课表进行编排。 在排课过程中， 需要考虑时间、时间段、教师、课程名称、班级等因素，使得排出的课表满足教 师以及班级的课时需求，且在时间、班级和教师等因素上不冲突。 课表编排要求： 该学院共有 7 门课程，共有 9 名教师，分别为 2 个班级授课，每位教师每 周需要在这两个班级各上的课时数如表 B1（见附录二） 。 该大学周一至周五上课，且每天有四个时间段可供安排课程，上午两节， 下午两节。同一个班级的所有学生都将参与相同的课程，除去高等数学课和体育 课之外，这两个班级各门课程的教师都相同。 体育课必须安排两个班同时在下午的第一个时间段，且分别由 H 先生和 I 女士为这两个合班的男生和女生上课。D 先生周一最好不要安排课程，B 女士周 3 三最好不要安排课程。该学院还规定每天每门课只能占用一个时间段。 所需要解决的问题： 需要根据教师和学生的实际需求分别给出两个班较为合理的课表编排方 案。 三、问题假设三、问题假设 1假设学院的要求是将课程全部排进两个班级的课表； 2假设普遍适应于编排课程的约束为“硬约束” ； 3假设教师及课程对上课时间的要求为“软约束” ； 4假设课表内容由上课时间、教师、课程组成。 四、模型建立四、模型建立 1.符号说明 主要符号符号意义 n q 教师编号 h x 课程编号 q t 时间段 m p 班级编号 a d 日子 2.硬约束条件简述 1、一天的一个时间只能由一个班级上一门课程 2、一个时间的一个老师只能给一个班上一门课程 3、一天的一个老师只能给一个班上一门课程 4 3.软约束条件简述 1、满足某些老师提出的在上课时间方面合理的要求 2、有些课程可能会出现合班或拆班的情况 3、有些课程有特殊要求 4.数学描述 （1）一共 H 门课程，N 个教师，Q 个时间段，M 个班级，A 天。 （2）班级集合为 P= 1 p, 2 p. m p; （3）设课程集合为 X= 1 x, 2 x. h x， 对应的班级数为 1 class, 2 class. m class; （4）设教师集合为 Q= 1 q, 2 q. n q, 对应的课程集合为 Z= 1 z, 2 z. h z; （5）日子与时间段的笛卡尔乘积为 K=(d1 1,t1 1)(d1 1,t)(d1 1,t).(d1 1, a t),(d,t1 1).; 5.硬约束条件描述： （1）一天的一个时间只能由一个班级上一个课程： 1111 ()1 QAMH qamhn aqmh tdpxq （2）一个时间的一个老师只能给一个班上一个课程： 1111 ()1 QNMH qamhn qnmh t dpx q （3）一天的一个老师只能给一个班上一节课： 1111 ()1 ANMH qamhn anmh t dpx q 5 6.软约束条件描述： （1）由于两个体育老师的课程在同一时间段内上课，于是优化假设两节体 育课为一节体育课，由一个老师授课，即课程为（H-1）门，老师为（N-1）个 （2）D 老师周一不上课： 114 11 ()() QM qmh qm M A Xftdpxq （3）B 老师周三不上课： 232 11 ()() QM qmh qm M A Xftdpxq （4）体育只能在 13：00-15：05 338 ()M A Xft h 五、问题的求解与分析（包括对问题的解释）五、问题的求解与分析（包括对问题的解释） 问题的目的是：为老师安排对不同班级的合理的课程时间。 问题思路框架： 将问题所求分为时间，教师，班级，课程四大模块，时间又分为：日子与时 间段，总共五个模块，班级，课程，日子，时间段可以集成一个信息集合，经过 硬约束条件，构成基本信息表， 由老师对课表的安排要求构成软约束条件作为优 6 化准则，对基本信息表进行进一步的优化。 对于普遍适应的条件采取硬约束条件， 对于个别的老师的课时要求采取软约 束。于是总体的步骤分为： (a)根据硬约束条件产生随机课表； (b)根据软约束条件作为优化准则，采取遗传算法进行优化。 简化后框架： 六、六、模型的评价（优缺点及模型改进）模型的评价（优缺点及模型改进） 1 模型的优点： a.有条理性，约束明确，详细，对于老师的要求可以尽最大可能的满 足，算法简单，可排出多种符合条件的课表，易于选择，并可以在原有约束上添 加其它别的约束，不添加算法的复杂度。 b.遗传算法从串集开始搜索，覆盖面大，利于全局择优。 c.将排课问题简化为一个多约束多目标的组合优化问题， 已经被证明是一个 NP 问题，继而选择遗传算法，建立科学的合理的计算模型，搜索课表编排的最 优解。 2 模型的缺点： a.步骤冗杂， 会在排出一些无用课表后再进行排查， 对时间的浪费有一点高。 b.遗传算法对算法的精度、可行度、计算复杂性等方面，还没有有效的定量 分析方法。 7 3 模型的改进： 添加对每天的课程的密度的均衡约束以及学生对课堂的时间满意度约束， 以 及较重要的课程占取授课效果较好的时间段的约束，前者可采取：先计算某一班 级平均每天上课的课时数，然后计算该班级的课时日分布均匀度，然后确定优化 目标，后两者可以采用权重的方法优化目标。 七、结论七、结论 本文是针对学校排课问题建立的简单求解框架以及遗传算法数学计算模 型。通过对两个班级、老师、课程的排课特点的整理与分析，提出解决方案，建 立 MATLAB 数学模型，解决多约束多目标的组合优化不规则排课问题，解决实际 生活中的问题。将实际排课问题抽象成一个遗传算法的数学计算模型，从而转化 为数学问题，用数学的思想解决实际应用问题。本文根据所应用的数学方法，例 举出了两个编排好的课程表，见附录。 本文通过已建立的数学模型为课程编排提出了合理化的方案， 并通过该方法 求得多个课程编排结果，最终会为教务处的不同需求筛选出更加优化的课程表。 八、八、参考文献参考文献 1 薛毅. 数学建模基础（第二版） ，北京：科学出版社，2011.4. 2 玄光男，程润伟. 遗传算法与工程优化,清华大学出版社,2004-01-01：25-62. 3 雷英杰. matlab 遗传算法工具箱及应用,西安电子科技大学出版社,2005-4-1:10-92. 4 唐勇，王玲. 基于遗传算法的排课系统. 计算机应用，2002，22（10） ：93-94. 附录一：附录一： （一）（一） ClassClass oneone 一一二二三三四四五五 1 1B BA AC CB BC C 2 2F FB BF FF FG G 3 3H/IH/IE EE EE EE E 4 4 ClassClass twotwo 一一二二三三四四五五 1 1F FB BF FF FG G 2 2B BA AC CB BC C 3 3H/IH/ID DD DD DD D 4 4 （二）（二） ClassClass oneone 一一二二三三四四五五 1 1E EE EA AG GF F 2 2B BF FE EB BE E 3 3B BC CC CH/IH/I 4 4F F ClassClass twotwo 一一二二三三四四五五 1 1G GA AC CC CD D 2