高校自动排课系统的实践 排课系统需求分析 学校排课系统

1、高校自动排课系统的实践孟昭文许彦郭新 （北京城市学院计算中心课表管理系统课题组北京100083） 摘要：本文介绍了高校机房排课系统的设计思想和实现方法，重点阐述了自动排课的策略，并给出了实施方案。 关键词:自动排课；计算机 我校计算中心为校本部各个学部提供共同使用的计算机实验室有16个，其中包括13个计算机软硬件模拟实验室和3个英语听力实验室。为满足近10个学部各学期计划的每周200多个班次的上机实验需要，我们每学期开学前都要花费很大精力安排上机实验课程表，同时为满足各学部平时频繁调课、加课的需要，还要设专人不离岗，接听电话、登记调课情况、调整课表。为了减轻人工排课劳动强度，并方便用户提交上机

2、学期实验计划及平时加课、调课工作，我们采用jsp技术开发了计算机实验室课程表管理系统，该系统包括计算机自动排课和网上申请加课/调课等子系统。其中自动排课是比较困难的，完成一个适用的计算机排课系统，不仅需要找到一个适用的算法，还需要借鉴好的经验和策略。本文就有关计算机排课的策略与实施方面的问题做初步探讨。 一 、高校排课的问题 高校的课表安排是一项十分繁重而复杂的工作，它涉及几十甚至上百个专业、几百门课程、几百名教师的合理安排。然而教室、实验室等资源又有限，更给排课增加了难度。在整个排课过程中，自始至终充满了冲突，其中包括上课班级、所开课程、任课教师、上课时间、上课地点等5个方面在排列组合中所发

3、生的冲突与矛盾。班级多、课程门类多、教师少、教室少是发生冲突和矛盾的重要因素。为了减轻劳动强度，提高工作效率，人们自然想到利用计算机来解决排课问题。早在20世纪50年代，国外就开始了这方面的研究，并在理论上论述了课表问题是np完全的。但由于现代计算机尚未找到解决np完全问题的多项式算法，此后的研究便更多地转向经验方式。我国对这一问题也进行了许多研究，特别在应用方面也出现了一些好的排课软件，如清华大学的tiser和西安交大的一个排课系统。它们在实际应用方面起到很好的作用，是很好的人/机交互式排课系统。但从目前情况看，无论国际还是国内，更为完整有效的自动排课算法还处于研究阶段。我校计算机实验课排课

4、与一般高校排课存在共同性与特殊性。 1共同性 上课班级多：我校每学期一般有200 300多个班次的上机实验； 课程门类多：我校每学期固定在计算中心上实验课的有二百多个专业，每个专业至少要开设1 门实验课，有的要开设2 3门实验课； 教室少：计算中心有普通计算机实验室13个（若每个实验按半天计，则13个实验室每周最多可安排13 x 7 x 2 = 182个实验），英语实验室3个，共计16个。 2特殊性 时间限制多：我校不仅上课班级多，而且上课时间还要受到各个学部各自排课制约，许多班级的上课时间被限制很少几个或唯一的时间段； 对实验环境要求高：我校不仅课程门类多，而且经常增加新的实验项目或使用新的

5、软件，对实验室的软件、硬件要求不断提高； 实验室经常供不应求：我校实验室少，常常不够用。如上所述我们每周最多能安排182个实验，而上报的实验常常要有200 300个实验，缺口比较大； 实验时间多少不统一：如上课时间多样性（不仅有单、双周的不同，而且有的只上半学期，甚至只上几周）以及上课时间多变性（调课频繁，临时加课或停课较多）； 实验内容的不固定性：我校专业设置根据社会需要不断变化，实验内容也就不断增减，新的应用软件也就不断增加。因而实验室的实验环境就要不断变化，特别是一些老实验室的硬件环境就变得不能满足新的实验需要了。 我校的特殊性给我们的排课问题增加了更大的难度。排课问题实质上是在传统排课

6、经验的基础上，利用计算机模拟人脑，探讨排课的思维规律和抉择方案。排课问题也可以归纳为组合优化问题。为了找到近似最优解，出现了许多方法，其中遗传算法是比较热门的一个。然而用它来解决排课问题尚有许多技术难点需要解决。针对我校计算机实验课与实验室的特殊性所建立的“计算机实验室课程表管理系统”（简称课程表系统），刚刚开始接触排课问题。 二、自动排课策略基本策略 总的想法是摸清底数、总体平衡、分类选优、逐步逼近。其实现过程如下： 摸清底数、总体平衡：排课前，首先对所提交的全部上机实验计划表进行必要的统计，以便摸清底数，并在必要时通过修改计划，使需求总体平衡； 分类选优：根据经验和有关统计，进行必要的分类

7、，并建立相关的“排课知识库”和“排课策略库”，制定选优标准； 逐步逼近：要求高的实验优先安排（比如只有极少数实验室可以安排的实验等），如果有限定时间的实验，则将其优先试排之后，再排其它实验。 具体做法是： 将限定时间的实验划分相应的时间段，并按时间段依次选优试排； 首先排限定唯一时间的实验； 然后排限定几个可选时间的实验； 限制相同时间的实验，在所限时间段内统一安排； 当所有限定时间的实验排完之后，再按照人数多少依次排其它的实验。 三 、自动排课实施步骤 为了使计算机排课排得更多、更好，根据我们的经验以及我们实验室的特点，按照上述策略设想，进一步提出排课过程中的预处理、分类选优、遗漏处理和总体

8、调整等基本构想。它们的主要任务是： 1预处理的主要任务 检查并处理供需之间的矛盾，控制需求总体平衡； 统计不同应用软件的需求量，根据需要完善实验环境； 将实验室分别按照实验环境与可安排实验人数多少分类； 统计实验人数，并根据实验室座位数进行分类； 对每一实验分别查找可满足其实验条件的实验室有哪些，并将这些实验室按照优先使用等级分类； 按时间段统计限定实验时间的实验； 制定“排课知识库”和“排课策略库”； 制定排课表过程中所需各种“表”或“视图”； 将部分实验（只有唯一时间及实验室可满足其要求的）预先排上。 2分类选优试排的主要任务 根据预处理中制定的“表”，制定试排需要的“临时表”； 规定各类

9、优先次序与规则； 通过按类“打分”选优方式（“打分”标准见附录），进行试排； 将所有符合可排条件的实验（应占总计划的大多数）一一排完； 完成一个初排“总课表”。 3遗漏处理（补充安排）的主要任务 对照初排的“总课表”，检查“计划表”中是否有遗漏的实验； 制定遗漏处理方法； 将遗漏实验逐一补排上； 4总体调整的主要任务 检查实验室安排的合理性； 检查相同教师安排的合理性； 检查相同班级安排的合理性； 如果检查结果存在不合理成分，则进行总体调整，使之更加合理。 四、结束语 本文结合本校计算中心实验室实际情况以及个人多年人工排课经验，探讨了计算机自动排课的策略问题。提出了“摸清底数、总体平衡、分类选

10、优、逐步逼近”的策略，并探讨了具体的实施方案和一些具体算法，提高了我校开发的“实验室课程表管理系统”中自动排课算法的水平。 参考文献：1赵光哲: 大学排课问题中的遗传算法设计,延边大学学报(自然科学版),200632陈行平等: 基于遗传算法的高校排课系统设计设计,绍兴文理学院学报,2004103何军华: 课表编排系统的算法研究与实现,北京师范学院学报(自然科学版),20031 the practice of automaticmanagement system for classesmeng zhaowenxu yanguo xinabstract:the paper is a narration about the design and implementation of automaticmanageme