数模公选.docVIP

B题：课表编排问题 1.1课程表的编排及分析 从数学上讲,本文主要分析建立排课问题是一个在时间、教师、课程代号和教室四维空间的数学模型, 以教学计划和各种特殊要求为约束条件的组合规划问题。其实质就是解决各因素之间的冲突。在设计算法时, 为了降低课程调度的算法复杂性, 我们主要采用了化整为零的思想确立目标函数，再根据优先级算法求出最优化的模型。 首先，在对问题进行分析时，发现课程，教师和教室满足下面的关系： 课程，教师和教室满足的关系（“示一对一关系,表示一对多的关系， 表示多对多的关系） 其次，对于问题进行初步分析得，对于给定的表格，我们该做的是：找到课程，教师，教室它们属性之间的联系。，然后根据联系与约束条件给出符合题目的排课方法。 最后，对所给出的方案的合理性进行分析。 1.2对教师聘用和教室配置的合理建议 对上述问题所求节出的排课方案进行分析，得出普通教室，多媒体教室，机房的利用情况和比例，适当调整教室的配置。 分析得出方案中哪种属性的教师排课比较多，哪种属性的教师排课少，根据教师带课的多少得出聘用教师的合理建议。 模型的建立与求解 1.1目标函数的确立与模型的优化 设一个星期分为矩阵,,即将周一至周五用表示，每天有8节课，2节为一个单位的方式排课，即上课节次：1、2节，3、4节，5、6节，7、8节分别用表示，并总是规定1，2节，3,4节为上午上的课时，5,6节，7,8节为下午上的课时。 学校待上课的教师编号为,要上的课的教室 每位教师在每个教室都有对应的一张课表（附录4） 记是一个维数列矩阵，表示T号老师对应R号教室第I周上，例如： “43“表示周一的第5、6节课。 例：表示1号教师在1号教室周三的第3，4节课程 表示1号教师在1号教室周三的第3，4节不排课 以此类推其他合理规定, 记：表示T号老师到R号教室的 授课时数（以单元计算，两节为一个单元） 表示R号教室在一周内排的总课时，设p号教师，q号教师在R号教室课时数为奇数，应作单双周排课处理，单周由p上课，双周由q上课。在计算可平衡时，对教室只算一个教师，而对教师的课时中，两个教师又都分别计算，在排课位置上，允许只有一个单元占两位教师，其他单元只能一位教师。 比如：p号教师在多媒体教室有6节课，q号教师在多媒体教室又5节课 若某教室安排的奇数课时的教师数为奇数，则增加一位虚拟教师，课时为1节。 矩阵B的处理方法： 1.2算法的实现 1、 排课的预处理 同一教师在同一时间不能安排两门课程 同一教室在同一时间不能安排两门课程 同一时间安排的课程总数不能大于所能提供的教室总数 所提供教室的属性与课程所需教室的属性一致 2、价类的划分 将具有共同对象的任务划分在同一等价类中, 在每个等价类之间只存在 地点上的冲突, 而没有时间上的冲突。 然后按照的大小, 从大到小进行处理。 等价类的划分可以先按性质的划分, 然后再在同一性质中的对象再讨 论,则如下所示: 对象等价类的划分 这样, 按性质分为四个类:课程编号、教室、时间、教师；然后对每个子 类分别进行排课处理,课程代号，教室,时间上午、下午，教师,这样做就可以大大降低算法的复杂性。 3、教室分类 为了合理使用教室, 我们采用了教室分类的办法, 以便尽可能在课程编 排过程中避免上课人数少的课程盲目强占容量大的教室现象。 首先将教室按照其类型分为若干个等价类, 然后, 根据教室的容量再分别对每个教室等价类进行划分: 如分为若干种。 4、时间预处理 对于每种周学时数, 可以将所有合理的时间组合形式存入模式库中。以便进行时间处理时可以用时间模式库中的各种模式进行匹配。 时间数组 为了表示教师、课程的可排课时间, 分别为他们建立一维数组L（如下图）。例如：某位老师的课排课数组为（1234，1234，1234，1234，1234）其中五组数据表示一周中的周一到周五，一组数据中的四个字符1，2，3，4表示一天当中的四个时间单元。如果某位教师不能排课则对应的时间单元用“0”表示。例如：某位老师的可排课时间数组为（0034，0034，0034，0034，0034）这个老师的周一到周五的上午3、4节有课。 5、基于时间片优先级排课算法实现 在实现算法之前我们把一些概念先来讲清楚。在这里我们把教室的类别分为自然教室，操作教室，随意教室，公共教室；在普通教室上课的教室叫自然教室，在机房上课的教室叫操作教室，既能在机房上课，又能在普通教室上课的教室叫随意教室，公共教室则是人数较多一起上课用的教室。课程代号，教室，教师都维护着自己的一张课表，对课表的每个表元（如星期一的第一节课）在这里称为时间片。 基于时间片优先级排课算法以操作教室为单位，围绕着各对像(自然教室，操作教室，随意教室，公共教室)的时间