课表编排问题讲述.doc

魅力数模 美丽力建 力建学院第六届数学建模竞赛 自信 坚强 团结 创新 论文题目 A题：课表编排问题 参赛编号 2009tm0502 监 制：力建学院团委 数学建模协会（2010年11月） 力建学院第六届数学建模竞赛 承 诺 书 我们仔细阅读了第六届建工数学建模竟赛的竞赛规则。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意承担由此引起的一切后果。 我们的参赛编号为：2009tm0502 参赛队员 (签名) ： 队员1：李超 队员2：王超 队员3：秦允皓 A题：课表编排问题 摘 要 在学校的教务管理工作中，课程表的编排是一项十分复杂、棘手的工作。排课需要考虑时间、课程、教学区域、教室、院系、班级、教师等因素。我们经过讨论后，对题目的要求进行分析，并认为可以规划为优化问题，可以将“教师”，“教室”“课程”作为优化因素讨论，以便分配到不同的时间段上，形成课表。 首先，确定各优化因素之间的约束关系，根据各因素间约束关系的不同，将多重约束条件分为硬约束（强制要求）和软约束（用偏好系数表示），编制出各因素间的效用矩阵。其次，把课程随机分配到课表上的每一个时间段，再以0-1规划方法分别将教师、教室分配到课表上的不同时间段上。形成时间+课程+教师+教室的组合。最终，形成满足要求的课表。 我们优化、0-1规划的方法，加入多重约束条件，引入了偏好系数，形成排课模型，根据题目给的数据，通过计算机编程，进行模型验证，求出了所需课表。最后给出了教师、教室的配置建议。 【关键词】：优化因素 排课模型 多重约束条件 0-1规划 1 问题的重述 在学校的教务管理工作中，课程表的编排是一项十分复杂、棘手的工作。排课需要考虑时间、课程、教学区域、教室、院系、班级、教师等等因素。经优化的排课，可以在任意一段时间内，教师不冲突，授课不冲突，授课的班级不冲突，教室占用不冲突，且综合衡量全校课表在宏观上是合理的。如何利用有限的师资力量和有限教学资源，排出一个合理的课程安排结果，对稳定教学秩序、提高教学质量有着积极的意义。 某高校现有课程40门，编号为C01～C40；教师共有25名，编号为T01～T25；教室18间，编号为R01～R18。具体属性及要求见表1，表2，表3： 课表编排规则：每周以5天为单位进行编排；每天最多只能编排8节课，上午4节，下午4节，特殊情况下可以编排10节课，每门课程以2节课为单位进行编排，同类课程尽可能不安排在同一时间。 你所要解决的问题： 请你结合实际情况给出较为合理的课表编排方案，分析你所给出的方案的合理性。 对教师聘用，教室配置给出合理化建议。 问题的假设 ①假设课程全部编排； ②假设是学生自选课程； ③假设在课程要求为强制要求（硬约束）； ④假设在教师属性中，能胜任课程类别、周最大课时数为强制要求（硬约束）；对教室类别要求、上课时间要求用偏好程度衡量（软约束）； ⑤假设所得4张课表中2张同时上课，上完后另外2张课表开始上课； ⑥假设课表内容由上课时间、教师、教室、课程组成。 3 符号说明 主要符号 符号意义 A1A2A3A4A5 效用矩阵 Ti 教师编号 Ri 教室编号 Ci 课程编号 α 偏好系数，表示教师对教室、教师对上课时间的偏好系数。 Si 课程表上时间段的编号 ST一 为T一教师的要求课时数 SCi 为Ci课程的要求课时数 Si={Yij,T一,R一} 课程表上某一时间段的课程-教师-教室组合 5模型准备 根据关联关系，刻画每个关系的效果指标矩阵 根据分析，关联关系有教师—教室、教师—课程、教师—上课时间、课程—教室、课程—上课时间一共五个。 图 1 关联关系示意（实线表示“硬约束”，虚线表示“软约束”） A1，A2…A4 七个效用矩阵。其中，为强制约束的有A2、A4。 A2 矩阵：