课表编排问题资料.pdf

《课表编排问题资料.pdf》由会员分享，可在线阅读，更多相关《课表编排问题资料.pdf（14页珍藏版）》请在三一文库上搜索。

1、1 魅力数模美丽力建 力建学院第六届数学建模竞赛 自信坚强团结 创新 论文题目 A 题：课表编排问题 参赛编号 2009tm0502 监制：力建学院团委数学建模协会（ 2010 年 11 月） 2 力建学院第六届数学建模竞赛 承诺书 我们仔细阅读了第六届建工数学建模竟赛的竞赛规则。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与本队以 外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到 的资料） ，必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列

2、出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们愿意 承担由此引起的一切后果。 我们的参赛编号为： 2009tm0502 参赛队员(签名) ： 队员 1：李超 队员 2：王超 队员 3：秦允皓 3 A题：课表编排问题 摘 要 在学校的教务管理工作中，课程表的编排是一项十分复杂、棘手的工作。排课需要考虑时间、课程、 教学区域、教室、院系、班级、教师等因素。我们经过讨论后，对题目的要求进行分析，并认为可以规划 为优化问题，可以将“教师”， “教室” “课程”作为优化因素讨论，以便分配到不同的时间段上，形成课表。 首先，确定各优化因素之间的约束关系，根据各

3、因素间约束关系的不同，将多重约束条件分为硬约束（强 制要求）和软约束（用偏好系数表示） ，编制出各因素间的效用矩阵。其次，把课程随机分配到课表上的每 一个时间段，再以0-1 规划方法分别将教师、教室分配到课表上的不同时间段上。形成时间+课程+教师+教 室的组合。最终，形成满足要求的课表。我们优化、 0-1 规划的方法，加入多重约束条件，引入了偏好系 数，形成排课模型，根据题目给的数据，通过计算机编程，进行模型验证，求出了所需课表。最后给出了 教师、教室的配置建议。 【关键词】：优化因素排课模型多重约束条件0-1 规划 1 问题的重述 在学校的教务管理工作中，课程表的编排是一项十分复杂、棘手的工

4、作。排课需要考虑时间、课程、 教学区域、教室、院系、班级、教师等等因素。经优化的排课，可以在任意一段时间内，教师不冲突，授 课不冲突，授课的班级不冲突，教室占用不冲突，且综合衡量全校课表在宏观上是合理的。如何利用有限 的师资力量和有限教学资源，排出一个合理的课程安排结果，对稳定教学秩序、提高教学质量有着积极的 意义。 某高校现有课程 40 门， 编号为 C01 C40 ； 教师共有 25 名， 编号为 T01T25； 教室 18 间，编号为 R01 R18 。具体属性及要求见表1，表 2，表 3： 课表编排规则：每周以5 天为单位进行编排；每天最多只能编排8 节课，上午 4 节，下午 4 节，

5、特殊情况 下可以编排 10 节课，每门课程以 2 节课为单位进行编排，同类课程尽可能不安排在同一时间。 你所要解决的问题： 请你结合实际情况给出较为合理的课表编排方案，分析你所给出的方案的合理性。 对教师聘用，教室配置给出合理化建议。 2问题的假设 假设课程全部编排； 假设是学生自选课程； 假设在课程要求为强制要求（硬约束） ； 假设在教师属性中，能胜任课程类别、周最大课时数为强制要求（硬约束）；对教室类别要求、上课时间 要求用偏好程度衡量（软约束） ； 假设所得 4 张课表中 2 张同时上课，上完后另外2 张课表开始上课； 假设课表内容由上课时间、教师、教室、课程组成。 4 3 符号说明 主

6、要符号符号意义 A1A2A3A4A5 效用矩阵 Ti 教师编号 Ri 教室编号 Ci 课程编号 偏好系数，表示教师对教室、 教师对上 课时间的偏好系数。 Si 课程表上时间段的编号 ST 一为T一教师的要求课时数 SCi 为Ci课程的要求课时数 Si=Yij,T一,R一 课程表上某一时间段的课程-教师- 教 室组合 5模型准备 根据关联关系，刻画每个关系的效果指标矩阵 根据分析，关联关系有教师教室、教师课程、教师上课时间、课程教室、课程上课时间一共五 个。 图 1关联关系示意图 （实线表示“硬约束”，虚线表示“软约束”） 依次建立 A1，A2A4 七个效用矩阵。其中，为强制约束的有A2、A4。

7、 A2 矩阵： A2 (aij ) （刻画 i 教师上 j 课程时的效果指标）其中： aij 0,1 A4 矩阵： A4 (aij ) （刻画 i 课程在 j 教室上时的效果指标）其中： aij 0,1 偏好约束有 A1、A3。 A1 矩阵 A1 (aij ) （刻画 i 教师上 j 教室的偏好效果指标）其中： 0 aij 1 A3 矩阵 A3 (aij ) （刻画 i 教师上 j 时间段上课时的偏好效果指标）其中： 0 aij 1 时间段 Si 的编号 每一张课表上有星期一到星期五，每天有4 个时间段（每两个课时算一个时间段）。 根据假设，假设题目需要同时排四张课程表，需要对四张课程表上的时

8、间段都进行编号 星期一 , 星期五 星期一 ,星期五 , 星期五 上午1、2 节 s1 , s5 s6 , s10 , s20 上午3、4 节 s21 , s25 s26 , s30 , s40 下午5、6 节 s41 , s45 s46 , s50 , s60 5 下午7、8 节 s61 , s65 s66 s70 , s80 表1 时间段编号 对课程的处理 当某一课程的课时数为奇数时，取大于他的最小偶数。对所有课程的课时数进行调整。新的课时数为Ki （i=1,2 40，即为 40 位教师），原课程编号为Ci（i=1,2 40）， Yij （i 表示原课程的编号， j =1,2（k1+k2+

9、ki ）/2 ）, 待排课程集合为 Yij 教师的课时数为。课程的课时数为。 STi(k=1.2.25) SCi 6 模型的建立与求解 6.1 模型的建立 6.1.1 随机分配课程到各个时间段 当课程的上课时间（上下午）要求为强制性约束时，分别选出上下午的课程集合 B上午=Y11Yij ，B下午=Y21Yij 。我们随机给中的每一个元素抽取一个上午的时间段，其中满 足的条件是，给中的每一个元素抽取一个下午的时间段。组成时间段课程 (SiYij)组合。此时，Si= Yij （某一时间段对应的某一课程）。 6.1.2 给每一个时间段安排教师 6.1.2.1 结合教师、课程的 Si 根据教师 Tk

10、对课程 Cj 的效用矩阵 A2，对i s 进行第二次赋值。当第 i 个时间段上的 初值是 Yij ，若aij=1,则Si =1,否则， Si =0。 6.1.2.2 结合效用矩阵 A3 的Si 根据教师 Tk 对上课时间的偏好 A3 矩阵，对 i s 进行第三次赋值， Si =Si -aij 。 6.1.2.3 结合效用矩阵 A1 的 Si 根据教师 Tk 对 si时间段上的课程所要求的教室的偏好 A1 矩阵，对 si 进行第四次赋值，si= si-aij 。最终得到 6.1.2.4 0-1 规划 目标是将Tk教师分配到不同的时间段上，约束条件是分配结果必须满足教师的课时数要求。因此，问题 转

11、化为求有约束条件的 0-1 规划问题。 目标函数： nn max Zskixki k 1 i 1 约束条件： 6 7 所得解为： 将教师安排到最优的时间段， 此时Si=Yij,Ti,Ri。若无最优解，重回 6.1.1 。 6.1.3 为每一个时间段安排教室 Ri 教室对 Si 这一时间段的效果指标： （1）该时间段的老师对教室的偏好（2） 该时间段课程对教室的效果指标 6.1.3.1 结合效用矩阵 A4 的 Si 根据 si时段课程 Ci 对教室 Ru 的效果矩阵 A4，对 si进行第一次赋值，若 aij=1, 则s i=1,否则， si=0。 6.1.3.2 结合效用矩阵 A1 的 Si 根

12、据si时段教师 Ti 对教室 Ru 的效用矩阵 A1 ，对si进行第二次赋值， si =s i-aij。最终得到： 6.1.3.3 0-1 规划 目标是将Ru 教师分配到不同的时间段上， 约束条件是分配结果必须满足同一 间教室在四张课表的同一时间段不重复。因此，问题转化为求有约束条件的 0-1 规划问题。目标函数： nn max Zsuixui u 1 i 1 约束条件： 8 所得解为： 将教室安排到最优的时间段， 此时 sYjk,Ti,Ri。若无最优解， 重回 6.1.1 。 6.1.4 安排课程表 将每个 Si的组合按照其编号读入到表 1 中，得到最后的课程表。 6.2 模型的求解 6.2

13、.1 为时间段编号并随机分配课程 充分考虑课程的时间要求 （上午或下午） ，随机分配课程， 得到“时间段 - 课程” 组合。分配示例见附录一。 由于，题目所给数据中，教师的总课时数小于课程总课时数，又经过计算，设定 目标是为做成四张课表，其中两张先行开课，上完后，另外两张课表再开课。利 用 0-1 规划求解，构造要用矩阵时，要考虑的是，教师对这一事件的偏好，教 师对这一试点的课程的效用两个因素，利用 excel 构造出效用矩阵。 lingo 编 程计算。程序代码见附录二。 6.2.2 分配教师 结合效用矩阵，为每个“时间段-课程”组合分配教师，得到“时间段- 课程-教 师”组合。 6.2.3

14、分配教室 结合效用矩阵，为每个“时间段-课程- 教师”组合分配教室，得到“时间段-课 程教师 - 教室”的最优组合，从而得到所求课程表。课程表见附录三 6.2.3 编排课表 将获得的时间段编号 +课程+教师+教室的组合编制成课表，编制结果参看附录。 其中，第一、二张课表同时开课，上完后，第三、四张课表开课。 9 7 模型的检验与分析 7.1 模型的检验（偏好系数 的检验 =1 时，课表中教师所上课程满足其对时间、教室类别的要求。当 =0 时， 课表中教师所上课程完全不满足其对时间、教室类别的要求。 另外，当教师和教 室的偏好度越大时， 0-1 规划得到的效用最小，例如当偏好系数为 0.1 时，

15、效 用只有 38.2 ，当偏好系数为 0 时，为最大效用 40 。可以见得，取极限，当偏 好度为 1 时，无解。所以，我们的模型能较大程度地满足教师、课程和教室的 要求，给出最终符合条件的课表。 7.2 模型的分析 7.2.1 合理性分析 模型充分考虑了课程、教室、教师等的相互约束，建立了关系关联，并对约束采 用0-1 规划，确定出“时间段 - 课程-教师- 教室”组合。同时，我们也充分考 虑了教师对教室和上课时间的偏好，建立了一个偏好系数可调的模型，使所得课 表尽量满足课程、教室、教师的各种属性及要求，对教师聘用，教室配置给出合 理化建议。但是，当四张课表一起开课时，无法达到教师的学时要求，

16、即四张课 表总需要周学时数为 160 ，但教师所能提供的只有 116 学时。计算机模拟表示， 没有最优解。于是，我们做出以下调整：将题目简化为两张课表一同开课，待到 上完课程后，再开另外两张课表。 7.2.2 几种特殊情况的处理 在模型准备的对课程的课时数的处理中，将奇数课时的处理成偶数， 以便计算。 在最终课表中， 对排好的课表进行调动， 奇数课时课程只上其要求的课时数，即 找到课程所在时间段，随机取消一节课。 如果所给课程的总课时数 （取偶后的总和） 大于教师的总课时数， 则按照教师 的课时数取 n 个课表，且 n 个课表同时开课。 如果所给课程的总课时数 （取偶后的总和） 小于或等于教师

17、的总课时数，则将 课程安排到 n 个课表中，且 n 个课表同时开课。 8 模型的评价 8.1 模型的优点 引入了偏好系数 ，能较大程度地满足教师、课程和教室的要求； 建立了关联关系，使模型建立更清晰、明确、具有条理性； 用 0-1 规划解决相互约束问题， 形成“时间段 - 课程- 教师-教室”组合， 科学 合理； 逐步优化，层层递进，思路清晰，简单易懂。 充分考虑各个教师、教室、课程的要求，具有良好实用性。 8.2 模型的缺点 当课时数为奇数时， 将其近似为偶数计算， 导致课表中所有时间未能充分利用； 在随机给每个时间段安排课程时，未能确立完善的分配方式； 10 9 参考文献 (1) 韩中庚，

18、数学建模方法与应用，北京：高等教育出版社，2005。 (2) 张小红、张建勋，数学软件与数学实验，北京：清华大学出版社，2004。 11 附录 附录一 程序代码： model: sets : teacher/ file ( 偏好0.1.txt) /:teacheryaoqiu; kecheng/ file ( 偏好0.1.txt) /:kechengyaoqiu; links(teacher,kecheng):c,x; endsets data : teacheryaoqiu= file ( 偏好0.1.txt) ; kechengyaoqiu= file ( 偏好0.1.txt) ; c= file ( 偏好0.1.txt) ; enddata max= sum (links:c*x); for(kecheng(j): sum (teacher(i): x(i,j)=kechengyaoqiu(j); for(teacher(i): sum (kecheng(j): x(i,j)=teacheryaoqiu(i); for(links:bin (x); End 12 附录二 所得四张课程表 14