高校智能排课系统文献综述

高校智能排课系统文献综述吴楝华摘 要 该文是关于高校智能排课系统文献综述。为了让高校智能排课系统及相关领域的理论研究及开发人员对高校智能排课系统研究有一个全面了解以及为读者查阅相关文献提供方便，对近几年发表的高校智能排课系统论文进行了分析。该文对多种排课系统方法进行了论述。研究表明，排课系统多样，各有各的优点，相关研究人员也是越来越多，研究水平不断提升。关键词 智能排课 蚁群算法0 简介 该文是关于高校智能排课系统文献综述。这篇综述，参考了2005年，及2009年，2010年的有关论文，论文就多种高校智能排课的方法进行了讲述。1 文献分类方案为了保持此项工作的持续性和一致性，本文对参考文献进行了分类。科学技术是随着时间的推移而发展的，故高校排课系统方法也会随着时间的推移而越发适应我们的生活，所以按时间排列以下方法：2005年:基于图论的高校排课系统;2009年：基于UML以及基于着色算法的高校排课系统；2010年：基于JSP以及基于蚁群算法的高校排课系统。2 期刊和文献的选取只选取与排课系统方法有关的重要文献，所选文献中，都建立了相关的高校智能排课系统模型，更能形象准确的表达文意，将多种方案综合一起，方便、读者查阅。3 综述内容3.1 2005年:基于图论的高校排课系统对排课问题的讨论， 可以将排课问题看成两个子问题，即：(1)时间的指定， (2)教室的指定。3.1.1时间的指定 通过分析可知造成开课计划冲突的因素，主要是两个计划中具有共同的学生或者教师或者班级，所以将学生、教师和班级看成一个因素，定义成参与者。另外，将开课计划看成图 g中点集，并将具有共同参与者的两个开课计划和连接成边。 则对开课计划指定时间就相当于为每个点指定颜色，所以该问题即为图论着色问题。考虑到课表将来调课的灵活性和可扩充性，该问题不应该过分追求图的色数。因此在工程上往往采用 Welch Powell近似着色法，并限制了每种颜色的点集数，防止某种颜色的点过多，导致无法安排教室。事实上 Welch Powell着色法同手工排课操作类似，即先安排合班数多的计划，再安排一般要求的计划。当然，该算法也仅仅类似专家系统，是一个启发式算法，但算法比遗传算法和专家系统简单且具有稳定性和可靠性，工程上容易实现。另外， 由排课问题形成的图各个点的度数都不是太大，根据3年6学期对我校排课计划数据的统计得出最大度数( 即课程冲突量) 不超过 100，平均度数为 l2 。 一般地， 对多于2000个计划的高校排课采用Welch Powell近似着色法时 ， 最小颜色数 同颜色的点集最饱满 ，后续具有相 同颜色的点数迅速减少。所以在为计划指定时间，按照时间的重要性从最小颜色号依次指定时间。 3.1.2指定教室设具有相同的时间计划点集，并用点集表示所有的教室，形成一个赋权二分图。这样，教室的安排就可以考虑成图论的最优匹配问题 ，然后Kuhn Munkres有效算法进行求解最优值。 3.2 2009年：基于UML以及基于着色算法的高校排课系统3.2.1基于UML的高校排课系统 要做好排课管理系统的需求分析就必须对现行学校的管理体制做初步的调查目的是了解学校现有管理体制的概貌规模等基本问题从而确认新系统的目标通过分析排课系统必须提供以下功能：权限管理，排课管理。构建静态结构模型：本系统中排课模块的功能大致为：教学秘书可以制定和修改教学计划，制定教学安排表,教务专员可以审核教学计划，修改教学安排以及设置排课参数，系统可以依据排课参数实现自动编排课表。从以上的分析，我们可以创建教务专员，系（部）教学秘书系统3个参与者。构建动态行为模型：在建立好系统静态模型的基础上，需要分析和设计系统的动态结构，以及建立相应的动态模型，主要借助于交互图（顺序图、时序图协作图）和行为图（状态图、活动图）进行描述。 在这里，只对用户登录系统和教学秘书作时序图描述。3.22基于着色算法的高校排课系统 排课系统框架：可以将排课系统划分为以下几个部分：输入/输出生成原始表生成衍生表，它们的关系和数据流向如图 1 所示着色算法简要描述：1. 将未着色的顶点按度的降序排序；2. 把第一个未着色顶点的所有邻接点的度减1；3. 如果存在一种颜色未分配给第一个未着色顶点的邻接点且这种颜色的可分配次数大于 0，就把这种颜色分配给它，否则给它分配新颜色；4. 如果还有其它顶点未着色就转到 1，否则结束经过上面两个算法的处理后得到原始表。生成约束表：课元 Ei，时间 Ti，课室 Pi一共可能有的 Not 的情况有：Not (Ei) Not(Ti)Not (Pi)；Not (Ei&Ti) Not (Ei&Pj) Not (Ti&Pj)；Not(Ei&Tj&Pk)等价于 Not(Tj&Pk)3.3 2010年：基于JSP以及基于蚁群算法的高校排课系统3.3.1 基于JSP算法的高校排课系统通过分析，我们采用当前流行的B/S结构,客户端除了浏览器,一般无须任何用户应用程序，只需从 We b服务器上下载程序到本地来执行。在下载过程中若遇到与数据库有关的指令，由Web服务器交给数据库服务器来解释执行，并返回给Web服务器，Web服务器又返回给用户。用户工作界面是通过浏览器( Browser ) 来实现，极少部分事务逻辑在前端实现，主要事务逻辑在服务器端(Server) 实现，大大简化了客户端电脑载荷，减轻了系统维护与升级的成本和工作量 ，降低了用户的总体成本 。BS结构能有效地保护数据平台和管理访问权限，服务器数据库也很安全。特别是在Java这样的跨平台语言出现之后，BS架构管理 软件更是方便、速度快、效果优。 针对目前世界上流行的大量软件和开发工具，经过认真分析其优缺点，结合排课系统的需要和目前的硬件环境，我们选用微软WINDOWS平台下的 Java语言、 my Eclipse作为软件开发工具和 J S P前台页面以及 sQL Server 2000数据库进行连接。 随着视窗操作系统的全面推广和流行，如今GUI(图形用户接口)已经成为业界用户接口的一个标准。在本系统的设计过程中，也按照GUI的设计原则来设计用户接口，给用户提供一个友好的人机交互界面。按照以简单易用和个性化需求，对数据的查询，基本信息输入等几点原则来设计。 排课管理系统是一项复杂的系统工程，其问需要大量的数据来支撑，从某种程度上来讲，排课管理系统的设计过程，其实也就是一个规范和完整的数据库设计过程。经过多年的发展，关系型数据库系统(RDB MS)是最成熟的一种数据库管理模式，也是当前最流行的数据库管理系统。故在此也采用该模式。以下是排课 系统中要用到的表 ： 3.3.2基于蚁群算法的高校排课系统高校课程编排过程中需要尽量满足多种约束条件,而为了编排出令各方面都满意的课程表 ,课程编排过程应遵循一定的规则 ,以满足各种约束条件:1)同一班级在相同时间最多安排一门课程;2)同一老师在同时间最多安排一门课程;3)同一教室在同时间最多安排一门课程;4)教室容量必须大于等于需上课学生数;5)同一时间必须保证总教室数大于等于总课程数;6)同一班级的同一课程在一周之内不应连续二天出现;7)各类型课程要安排在它相应类型的教室(例如实验室、 机房、 绘图室等) ;8)数学、 外语等基础课程应尽量排在上午 1 - 2 节;9)有课的教师和学生在二节课之间最好在同一教区;10)体育课应安排在下午或上午 3 - 4 节 ,下午体育课后应避免安排其他讲授课程;11)语音课应尽量安排在上午 ,实验课程、 操作课尽量排在下午;12)尽可能满足教师的读博、 科研等特殊上课时间要求;13)班级每周课时总量尽量均匀分布.这些约束涉及 2 种:一种是硬约束一种是软约束 ,即在排课过程中必须满足的约束条件和尽可能满足的约束条件.硬约束必须满足 ,否则违反教学规律 ,必定会产生冲突 ,导致课表无法继续运行 ,而在硬约束完全满足的情况下 ,软约束的满足程度即课表优化程度 ,人性化地编排课程.一般来说满足全部硬约束条件的即为可行课表 ,满足硬约束条件并满足软约束条件的为优化课表.以上列出的部分排课问题所涉及的约束条件 ,l)至7)为硬约束 ,其余为软约束.排课问题实际上是一个如何优化进行排列组合的问题 ,多目标的组合规划问题.排课的理想状态是对资源实现最优化配置 ,进行最合理科学的分配 ,也就是说满足所有约束的课表.事实证明 ,绝对优化的课表是不存在的 ,只能编排出完全满足硬约束条件并尽可能多地满足软约束条件的课表.也就是说实际上要完成的任务是通过组合规划生成可行且较优的课表.排课时 ,需要将教师、 班级、 课程安排在一定时间段的某一个教室并且满足硬约束条件.由此可见 ,排课问题中一般存在 5 个元素 ,即课程集合 K = K1 , K2 , K3 , , Knl ,教师集合 S = S l , S2 , S3 , , S nt ,班级集合 B = B1 , B2 , B3 , , Bne ,时间集合 T = T1 , T2 , T3 , , Tnp ,式中 Ti表示可安排课程的第i个时间段,如 T1 表示本周能够安排课程的第一个时间段,周一第 1 - 2节、 T11 表示周二 1 - 2 节.教室集合 J = J 1 , J2 , J3 , , J nr . 笛卡尔积 KS B T J 就构成了课程编排问题的求解空间.这个求解空间的难度在于办学规模、 教学层次、 办学条件等多个因素的共同制约,这个求解的规模巨大,可以想象. 安排课程以前,各学院要完成教学任务的下达、 核实等多项工作,按照教学计划把各专业班级下学期所需要开设的课程选定,选定相关教师担任教学任务,完成后交教务处.其中心任务也就是在排课以前确定班级课程教师这三者的关系,这三者的关系不是满映射,而另外二个因素时间和教室,因为可以每门课程给定一个教室和时间,可以认为是一个满映射.但是课程这个要素却关联着教师和学生,所以排课问题即是满足约束条件的前提下的目标函数:min iR cos tij ,这个函数中, R表示 K B J 笛卡尔积中关联课程集合, j T J ;cos tij 是表示i 这一课程分配的 j 所需要付出的代价.又因为每一个教学时段、 每个教室都可以安排课程 ,故 可以看成是 T J 的满映射.则排课问题可以表示为映射: f : K2 T J .其中 K是课程,它与教师和班级有关,按照教学计划,每个班级固定有相应的课程,而每种课程有相应的教师才能授课; T J 表示时间和教室的笛卡尔积.排课实质上是将教师、 学生和相应的课程在时间和空间上根据不同的约束条件进行合理的安排.对排课问题中涉及的 5 大因素采用集合形式表示 ,并据此对排课结果的解空间和课程与 对的匹配问题都予以介绍.排课问题是以上提及的 5 种元素满足多种约束条件然后进行合理的排列组合.一是同一班级在同一时间只能排一种课程.设 B Ki表示 Ki门课的班级主体.二是同一教师在某一固定时间只能排一种课程.设 J L 表示 J i 这门课的授课教师.三是同一教室在某一时间只能排一种课程.四是教室座位数必须大于等于上课学生数.五是教室总数要大于同一时间安排的课程总数.六是每种课程必须安排在对应类别的教室.满足以上条件的解为可行解.图 1 排课问题的双分图模型构造流程图4 结语高校排课管理处于教学运行的核心位置,主要任务是根据教学计划把各授课部门的教学任务进行汇总,制订全校各班级的课表。随着高校扩招的进行,学生数量和教师数量不断增长,以及多校区运行的现实,传统的手工排课,不可避免地出现教学资源冲突或教师资源冲突的情况。本文，就自动排课系统中的几个关键算法进行综述,旨在让高校智能排课系统及相关领域的理论研究及开发人员对高校智能排课系统研究有一个全面了解以及为读者查阅相关文献提供方便。参考文献1. 吴福贵.高校排课系统的设计与实践.科技创新导报2010 NO.042. 张少宇.基于着色算法的高校排课系统.行业治理.2009年3月10日第3 期3. 齐萍.基于蚁群算法的高校排课系统优化策略.湖北工业大学学报.2010年4 月4. 张健.基于图论的高校排课系统实现.重庆师范大学学报(自然科学版). 2005年3月第22卷 第1期5. 周方，万臣，彭云.基UML的高校排课系统的分析与设计. 软件导刊.2009年3月6. 付宁. 基于JSP的高校排课系统设计研究. 现代商贸工业. 2010年第 l7期