基于分类优化和优先级算法的自动排课探讨

基于分类优化和优先级算法的自动排课探讨 基于分类优化和优先级算法的自动排课探讨,软件 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 开发, 苟正伟 李传东 约4693字 摘要:为解决目前高校自动排课系统设计复杂、排课效率低的问题，提出了一种基于分 类优化、优先级算法以及矩阵匹配运算的自动排课算法。该算法首先对课程进行分类优化， 然后按优先级进行计算，其次引入矩阵的迭加匹配运算，将整个问题分层分类处理, 从而使 大问题分散在各个子问题当中，并通过逐层处理达到了降低算法复杂性、减少死锁的目的, 最 终实现自动排课。 关键词:自动排课;分类;优先级 中图分类号:TP312文献标识码:A文章编号:1009-3044(2008)34-1645-02 The Discuss on Automatic Course Arrangement Based on Classification Optimization and Priority Algorithm GOU Zheng-wei, LI Chuan-dong (College of Computer Science, Chongqing University, Chongqing 400044, China) Abstract: To solve the problems of the complexity and low effectiveness of course schedule in automatic course arrangement system in universities, a new algorithm for automatic course arrangement is proposed based on the theory of classification optimization, priority algorithm and matrix computation. The main ideas of the proposed method are as follows. The courses to be scheduled are firstly optimally classified and then leveled and sorted based on the priority and matching matrices. Thus, a large problem is shifted into some small problems that can be solved easily. Thus, automatic course arrangement is implemented with lower complexity and reduced deadlock. Key words: automatic course arrangement; classification priority; matrix match 1 前言 目前，关于高校排课算法的研究一直是一个热点问题，早在20世纪70年代就有人提出 自动排课这一问题，直到现在，研究自动排课系统的步伐一直就未停止过。就目前而言，已 经有部分高校和公司成功开发出了学校自动排课软件并投入使用。其采用的算法大多集中在 目前比较流行的基于图论的算法、利用人工智能的遗传算法、蚁群算法等。但由于这些算法 均存在着思路复杂、开发难度大、优化不确切等问题;因而，软件除具有各自的一些优点外， 还不同程度地存在一些问题，例如，排课效率低、排出的课程不够合理、与人工排课相差很 远、且受多种条件的限制等。 针对上述存在的问题，本文提出了一种基于分类优化和优先级的算法，该算法先对课时 段、课程和教室进行分类优化，然后运用优先级算法结合矩阵的迭加匹配运算实现自动排课， 从而解决了排课中关系多、因素多、约束条件多等问题。 2 排课问题的描述 排课是将教师、学生和相应的课程在时间和空间上根据不同的约束条件进行合理的安排， 避免冲突，以使教学工作顺利进行。对教师、班级、课程、时间、教室五部分资源进行最优 化配置，符合教学规律，才能保证充分发挥各个资源的优势，提高教学质量。随着高校教学 规模的扩大，人数增加，校区增加，教师增加，排课涉及的因素越来越多，问题越来越复杂， 使得手工操作逐渐无法胜任排课工作。为了提高教务管理工作效率，改善教学管理质量，合 理高效地利用有限资源，使课 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 编排更合理、科学、快速，自动排课系统的设计被人们所广 泛关注。 为了编排出令各方面都满意的课程表，在课程编排过程中应遵循一定的规则，尽量满足 各种约束条件。下面列出了部分排课问题所涉及的约束条件(1-3为硬约束，其它为软约束): 1) 一个班级在同一时间只能安排一门课; 2) 一个老师在同一时间只能安排一门课; 3) 一个教室在同一时间只能安排一门课; 4) 教室容量必须满足上课学生人数; 5) 课程要安排在它所需要类型的教室中如多媒体教室、机房、物理实验室等; 6) 同一个班级上的同一门课程在一周之内应间隔排列; 7) 繁难课程应尽量排在精力充沛的上午授课; 8) 体育课应该排在下午或者上午三四节，体育课后面避免安排讲授课; 9) 实验、操作课应排在下午或晚上; 10) 教师半天的活动尽量安排在一个校区; 11) 一个班级同一课程在一天内上课不能超过3学时。 要对课表在多资源上实现绝对最优的配置实际上是不可能的，因此，考虑在无任何硬性冲突的基础上，能够满足尽量多的软性冲突，我们就认为这个课表是可行并且较优的。 3 排课问题的定义 在设计算法时，为了降低课程调度的算法复杂性，主要采用了分类、优先级以及矩阵迭加匹配的算法思想。首先对排课数据和时间单元进行预处理，主要的预处理过程有: 3.1 课程预处理 各院系根据各年级开课情况，制订相应的教学 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 。即本院系教师所授课程以及所授的班级上报教务部门，教务部门依据该课程所需课时以及课程的类型、重要程度等确定该课程的优先级，以此确定自动排课的排课号，为按优先级排课打下基础。同时，我们把课程按每天上课的时段分为五种类型，需第一二节上的为一型，三四节上的为二型，下午五六节上的为三型，七八节上的为四型，晚上九十节上的为五型。 3.2 教室预处理 教室根据实际情况按校区可分为普通1型(XX人以内)，普通2型(XX至XX人)、普通3型(XX人以上)、多媒体1型、多媒体2型、多媒体3型、网络1型、网络2型、网络3型、室外等等类型。这样，我们就避免了教室资源的浪费，把最接近的人数安排在相应的教室中，也就是说我们把问题进行分类，化整为零，然后分门别类进行排课处理，这样做就可以大大降低算法的复杂性，从而提高排课处理的速度。 3.3 时间预处理 设置每两小时为一课程单元计算，j表示一周的课程单元数，i表示一学期的周数。定义三张时间矩阵表，一张是教师的矩阵表，表示为Tn[i,j]，一张是学生班级的矩阵表，表示为Cn[i,j]，一张是教室的矩阵表，表示为Rn[i,j]。我们排课的最终目的就是要把所有的课程都安排在这三个矩阵内，且使这三张矩阵表迭加匹配成功，并尽量遵循人工排课的规律。设一天5个单元课时，一周5天计算，就是25课时，那么j的最大值就为25，即定义可用时间代码 j=1…25，其中 j=1…5 分别表示周一的排课情况，j=6…10 分别表示周二的排课情况，以些类推。