课表模型及排课算法应用.pdfVIP

计 算 机 系 统 应 用 2011 年 第 20 卷 第 2 期 ① 课表模型及排课算法应用 1 2 陶 滔 ，谢卫星 1(苏州科技学院 电子与信息工程系，苏州 251011) 2(南华大学 计算机科学与技术学院，衡阳 421001) 摘 要: 针对排课过程中出现的关于教师、时间、教室和教学班级之间的多维冲突，通过对冲突的复杂度削弱研 究，建立起课表的数学模型并提出了高校综合课表编排算法；同时依据此算法可以对学校的教学资源的可用度 进行评估，为高校的管理提供了科学的决策依据。 关键词：课表；课头；排课；冲突 Curriculum Model and Its Application to Algorithm Curriculum Schedule 1 2 TAO Tao , XIE Wei-Xing 1(School of Electronic Infomation, Suzhou University Science Technology, Suzhou 251011, China) 2(Department of Computer Science and Technology, Nanhua University, Hengyang 421001, China) Abstract: This paper aims at the multidimensional conflict with the Teacher, Time, Classroom and Class in the curriculum schedule. Through weakening and studying the complexities of the conflicts, it gives curriculum model and the algorithm of curriculum schedule in university, and can assess education resource in university according to the algorithm, offers the decision-making for management of the university theoretically. Keywords: schedule; curriculum; curriculum schedule; clash 1 问题的提出 此外，有些文献试图从图论的角度来求解排课表 60 年代末，国外就有人开始研究课表编排问题。 的问题，但是图的染色问题也是 NP 完全问题，只有 1962 年，Gotlieb 曾提出了一个课表问题的数学模 在极为简单的情况下才可以将课表编排转化为二部图 型[1,2,4] ，之后人们对课表问题的算法、解的存在性等 匹配问题，这样的数学模型与实际相差太远，所以对 问题做了很多深入探讨。但是大多数文献所用的数学 于大多数学校的课表编排问题来说没有实用价值。 模型都是 Gotlieb 的数学模型[3][6] 的简化或补充，而至 目前，解决课表的方法有：模拟手工排课法，图 今还没有一个可行的算法来解决课表问题。 论方法，拉格朗日法，二次分配法等多种方法。由于 40 年来人们对课表问题的计算机解法做了许多尝 课表约束复杂，用数学方法进行描述时往往导致问题 试。其中课表编排的整数规划模型将问题归结为求一 规模剧烈增大，这已经成为应用数学编程解决课表问 组 0-1 变量的解，但是其计算量非常大。解决 0-1 线性 题的巨大障碍。 优化问题的分支一定界技术却只适用也规模较小的课