自动排课算法

第3 5卷第5期 2006年 1 0月 上海师范大学学报(自然科学版) Journal of Shanghai Normal University(Natural Sciences) Vo1．35，No．5 2 0 0 6，Oct． 高校智能排课系统的算法 潘以锋 ，2 (1．华东师范大学 教育学院，上海200062；2．上海师范大学 信息化办公室，上海200234) 摘 要：以教学任务为基本单位，在计算教学任务排课优先级的基础上，对教学任务的时间和 教室的安排均采用优化资源查找的算法．为简化算法，先安排教学任务的时间，然后再安排教 室，设计并实现了一个高效智能排课系统． 关键词：智能排课；课 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 编排；优先级；算法 中图分类号：TP392 文献标识码：A 文章编号：1000．5137(2006)05-0031-07 0 引 言 课程编排作为高等院校教务管理中的一项重要而且繁重的工作，从一般意义上讲，其实质就是对学 校下学期开设的每门课程合理地分配时间资源和教室资源的过程．其中涉及教师、教室、时间和学生等 多种因素，人为要求也比较多，另外由于这几年的高校扩招导致教室资源比较紧张，诸多因素就加重了 课程编排工作的难度和复杂度．如果完全由人工来编排课表，费时费力，其科学性、方便性更是难以保 证，所以利用计算机进行自动排课的想法自然而生． 20世纪50年代末，国外就有人开始研究课程编排问题．1975年，Enen等人证明了课表问题属于 NP完全类．目前，经研究用来解决排课问题的方法有：模拟手工排课法、图论方法、模拟退火法等．国外 的研究表明，解决大规模的课表编排问题光靠数学方法是行不通的．而且，国外研究的许多算法大多没 有考虑教室的因素，不适合我国的高校．国内针对课表问题也相继研制出了一些排课软件，但是软件的 通用性差，因各学校教学资源不尽相同，管理课表的方法也不乏个性，很难完全规范化、程序化．本文作 者根据某高校的实际情况，结合以往的排课经验，通过静态设置教学任务的优先级、分配时间片资源和 教室资源时根据相关参数动态设置其优先级的算法设计并实现了一个高校智能排课系统．如何充分利 用有限的教室和时间资源合理地编排课表，是作者研究的主要问题． 1 排程问题 1．1 术语解释 课程表是协调教师和行政班在上课节次、上课教室二个要素上的总调度，在排课过程中经常使用以 下几个概念： 1．1．1 行政班和教学班 行政班：由同一年级、同一专业、按同一教学计划培养的一定数量的学生组成的，便于管理和课外活 动的学生集体．对学生较多的专业，一般分多个行政班；教学班：在相同时间、相同教室，学习由相同教师 收稿日期 ：2006-05一10 基金项目：上海师范大学教务管理系统(JzooO3)． 作者简介：潘以锋(1968．)，男，上海师范大学信息化办公室；华东师范大学教育学院在职硕士研究生 维普资讯 http://www.cqvip.com 32 上海师范大学学报(自然科学版) 2006年 讲授同--1'3课程的一定数量的学生组成，便于教学和课堂活动的学生集体．一个教学班可以包括一个院 系或多个院系的一个或者多个行政班．例如，数理学院有两个行政班，编号为320601和320602，合并上 高等数学课程，则称320601班和320602班共同组成了高等数学的一个教学班，其教学班号定义为高等 数学教学 l班． 教学类型：与完成--1'3课程的全部教学任务相关的各个相对独立的教学环节，如主讲、实验、上机、 辅导、习题．一门课程一般涉及多个教学类型； 开课院系：负责讲授课程，完成某门课程的全部教学环节和课程考试的院系． 修课院系：学习某门课程的学生所在的院系． 1．1．2 教学任务、时间片和时空片 教学任务：一门课程的每个教学班在一周内可包含多次授课时段，每一个授课时段就是一个教学任 务，例如有一个教学班：05计算机专业数据结构 1班，是O5级计算机专业，所上课程为数据结构，每周5 节课，一周有两次上课时问，一次上课3节，一次上机2节，共上 l8周，则该教学班有两个教学任务，一 个教学任务为每周上课3节，在多媒体教室上课，另一个教学任务为上机，在机房上课． 教学任务的相关属性有：教学班ID、教师ID、人数、教室类型、上课地点、上课时间． 时问片：每一周次可以编排课程的每个节次为一个时问片，即时间片是个三元组([周次、星期几、 节次])． 时空片：课程任务的时间片及对应的上课地点合称为时空片．将教室相同，时问在同一个上午、下午 或晚上且连续的若干个时空片的集合称作时空片簇．因此排课的任务即是为给的每个课元合理地分配 时空片簇． 之所以把时间片精确到某一周次，是因为在实际情况下高校每学期各课程的起止周不完全一样，例 如320601班 l～9周上“概率统计”，lO～l7周上“计算方法”，假设这两门课程的其他上课要求都相 同，那么完全可以将这两门课安排在一周内的同一个时间段，例如，前9周上”概率统计”，后8周上”计 算方法”．如果时间片没有精确到周次，而仅仅是个二元组[]([星期、节次])，就无法做到这一点，不能 充分利用宝贵的时间资源． 最后指出一点，在文中课程编排的过程中以教学任务为基本单位． 1．2 排课约束条件 合理地排课需要满足一定的约束条件，一般包括以下3个层次：硬约束条件、优化约束条件、特殊约 束条件． 1．2．1 硬约束条件 硬约束条件是在课程编排的过程中，必须严格遵循的条件，主要包括： (1)每个教室在一个时问片最多只能有一个教学任务； (2)每位教师在一个时间片最多只能有一个教学任务； (3)每个行政班在一个时间片最多只能有一个教学任务(“全校选修”除外)． (4)属于同-1'3课程的不同课元(教学任务)不能安排在同一天； 1．2．2 优化约束条件 优化约束条件，旨在使课程的安排尽可能合理、科学．优化约束条件是在满足硬约束条件的基础上， 最好能够满足的条件，在某些特殊的情况下，也可以不满足．结合实际情况，为了 使编排的课表更加优 化、合理，排课时还应该考虑以下几条优化原则： 同-1'3课程的多个课元的时间要间隔均匀，而教室则尽可能相同．-1'3课如：果两个课元，最好分在 (一、二)与(四、五)之间，即一次放在(一、二)，另一次放在(四、五)，如果是三个课元，最好分在一、三、 五 ： 尽可能满足每个课元教学的合理要求，比如对多媒体教室、语音教室的要求．教室可以降级使用，可 维普资讯 http://www.cqvip.com 第5期 潘以锋：高校智能排课系统的算法 以设置教室降级次序；需要建立可替代教室类型关系表，该表主要维护某课程需要的教室类型不存在 时，可以使用该课程可以替换的教室类型；从某一个类型降成另一个类型，但不是任意降级； 每个教学任务可用的时间片和教室都不可能唯一，为了尽可能的避免死锁，通过动态计算待分配的 时间片和教室的优先级来合理分配资源． 选择时间时，尽量使学生的负荷趋于平均，从教学记录包含的行政班和任课教师在一个星期内最空 闲的一天开始查找； 选择教室时，尽量使教室资源的负荷趋于集中．在某些排课系统中，可能希望教室资源的使用尽量 趋于平均，这样便于排课．而有些高校为了在排课之后，多余教室可以另作他用，所以希望尽量使教室集 中使用． 2 数据库设计 在排课系统中，需要记录排课的初始数据，过程数据以及结果数据，具体的数据表有：教学执行计划 表、教学班表、课程表、课程类型表、教室表、教室类型表、教室使用情况表、行政班表、行政班学生关系 表．这些表各司其职，分别管理排课过程中的各个方面． 3 排课的过程 整个排课过程比较复杂，在自动排课之前需要进行初始化、参数设置以及教学班预排，在自动排课 之后需要人工调整排课结果．具体排课流程如下： (1)建立并完善教学执行计划．因为教学执行计划是生成教学班的基础，自动排课的主要目的就是 根据行政班的时间资源、教师的时间资源、教室的时间资源合理安排教学班的上课时间和地点． (2)排课初始化．清空行政班的时间资源、教师的时间资源和教室时间资源． (3)设置上课时间片．设置在一周中上课的天、以及一天中上课的时间片． (4)设定不可使用的时间资源．设置包括3个方面：某些教师的不可用时间资源、各个行政班的不 可用时间资源和具体教室的不可用时间资源． (5)设置一些排课特殊条件． ①设置教师一天上课的最大上课节数．一般来说，一个教师一天上课不超过5节，超过会影响教学 效果和教师的身体健康．这种设置既对自动排课有效，也对手工排课有效； ②设置教师跨校区上课的最小时间间隔．考虑到不同校区之间的距离，安排教师在不同校区继续上 课时，应考虑从一个校区上课结束到另一个校区所花费的最少时间．例如可以设置中间必须间隔至 少 2h． ③设置不能连续排课的两个教学楼．有些教学楼彼此之间相隔比较远，教师、学生为连续上课在这 两个教学楼之间需要一定的时间，可能会超过下课的时间间隔，所以这两个教学楼不能连续排课； (6)设置排课教学班组． 排课教学班组就是在排课过程中，把一些具有某些相同特征的教学班归并到一个组中，这样就形成 了一个个排课教学班组．接着设置这些组的排课优先级，在自动排课过程中，先排优先级高的组，再排优 先级低的组，这样就可以保证优先级高的教学班组优先获得资源，并且可以获得合适的资源，优先级低 的教学班组次之，优先级低的组可能会获得不是很满意的资源，甚至不能获得资源． (7)根据执行计划产生教学班，同时根据教学班组的属性设置新教学班的所属组．根据某专业年级 的执行计划中的课程，生成相应的教学班．同时根据课程的不同类型决定生成教学班的方式． (8)设置不需要自动排课的教学班． (9)根据教学班相关课程的要求分成不同的教学任务．一门5节课的课程可以分成3+2，3节课是 一 个教学任务，2节课也是一个教学任务．所谓教学任务就是一次上课的连续时间片．3节课、2节课就 维普资讯 http://www.cqvip.com 上海师范大学学报(自然科学版) 2006拄 是 2个课元． (10)设置教学任务的教室类型要求． ①一般讲授的课使用一般教室；②上机课使用机房；③ 语音课使用语音教室；④ 舞蹈课使用舞蹈 教室；⑤ 有些特殊的课程不但可以设置教室类型，而且需要指定特定的教室；( 有些特殊的课程也可 以不指定上课地点，因为体育课可以几个班级同时使用同一个操场． (11)安排教学班或教学任务的任课教师．从执行计划生成教学班时，可以根据计划中课程的任课 教师设置相应教学班的任课教师，但执行计划中的任课教师可能会发生变化，另外一个教学班会拆分成 多个教学班，所以需要设置某些教学班的任课教师． (12)手工预排．有些教学班不便于自动排课，还有些教学班比较重要，需要事先确定上课时间和地 点，所以需要在自动排课之前，让教务处和学院进行手工预排． (13)自动排课．把没有预排的教学班并且已经设置了自动排课的教学班进：，亍自动排课，即根据行政 班的时间资源、教师的时间资源、教室的时间资源，在避免冲突的基础上，自动安排各教学班的上课时间． (14)对自动排课不完善的教学班进行手工调整．自动排课结束时，可能有些教学班由于时间资源 冲突的原因不能自动排课，也有可能有些教学班排得不使用户满意，所以在自动排课结束时，检查自动 排课的结果，进行人工排课，调整自动排课的结果． (15)根据排课结果生成课程表．生成的课程表有以下4种：①行政班课程表；② 学生课程表；③ 教 室课程表；④ 教师课程表． 4 排课算法设计 4．1 设定教学任务排课优先级 排课是教务管理工作中的一个难点，原因在于排课需要考虑教师、教室、实验室、体育场地、课程分 布、时间分配、分合班、单双周、教师要求等多方面约束．所以排课首先要考虑的问题是冲突问题，程序在 判断各个约束条件时，怎么样做到主次问题的区分，这是整个系统的关键．排课冲突问题必须通过排课 算法来解决，为了减低课程编排的复杂性，设计合理的排课顺序是很重要的，就是使用优先级，即优先编 排某类课程． 4．2 符号及类型定义 为了方便描述算法，首先介绍一些符号设定：TeachTasks：表示教学任务的集合；TaskGroup：表示教 学任务的组；Task_i：表示第i个教学任务；Task．i_÷course：表示Task_i的课程编号(唯一课程标识)； Task_j_÷class：表示Task_i的行政班级的集合；Task—i---~LessonNum：表示Task_i拘上课总人数；Task_．i_÷ TeacherId：表示Task_i的任课教师；Task—i---~ContinueNum：表示 每一讲次的连上节数(9≥Taskj c0n— tinueNum≥1)；Task_j Rooms：表示满足教学要求的教室的集合；Task—i Room_j：表示Task—i_÷R0oms 中的第j个元素；Task—i---~TimePieceStr：表示Task_Ii的分配的教学时间片．用 112字节的字符串表示：7 ×16=112，某一位上是 1代表已占用，0表示未占用Task—i---~RoomType：表示Task_i的课程所要求的 教室类型．例如上机需要机房，语音课需要语音教室等； 4．3 靠边策略 考虑对课元c的安排，其周学时为P，在分配时空片簇时，任意大小 为P的空闲时空片簇都有可能 是其可行时空片簇．例如，某个最大空闲时空片簇如图1所示 l 2 3 4 5 图 1 靠边示意图 其大小为5．假定P=2，对于课元c而言，实际上它对应4个大小为2的空闲时空片簇：1—2，2—3， 维普资讯 http://www.cqvip.com 第5期 潘以锋：高校智能排课系统的算法 3 4，4 5．仅考虑靠边的两个空闲时空片簇 1—2和4—5，这就是时空片簇的靠边策略． 直观上看，采用靠边策略一方面可以缩小搜索范围，另一方面可以使得时空片的剩余空间更好利 用，为后面课元的安排留下更多的机会 ．在排课结束时，把4—5节课尽可能调整到3—4节课． 4．4 算法描述 在排课过程中，最难的子过程就是自动排课，有些自动排课系统在确定某一教学任务的课程表时， 是时问片和教室一同考虑，而本系统为了简化 自动排课程的过程，将排课问题看成两个子问题，即：(1) 教学任务时间的确定；(2)教学任务教室的确定． 4．4．1 教学任务时问的确定 按照每一个门课程的优先级，从高到低对所有课程进行遍历，排课，即安排合适的上课时间和上课 地点．为了降低排的难度，先为每一教学任务安排合适的教学时间，该教学时间的安排使教师的时间资 源不冲突，使相应行政班的时问资源也不冲突，待所有教学任务的时间安排好之后，再安排教学任务的 教学地点．算法描述如下： 4．4．1．1 教学任务分配教学时间 (1)遍历所有TaskGroup(教学任务组)．按TaskGroup的优先组从高到低进行遍历； (2)遍历当前TaskGroup中的所有Task—i(教学任务)； (3)针对当前Task—i(教学任务)找一个合适的教学时间，若找不到就把当前Task—i(教学任务)设 置成不能分配教学时间； ① 找出Task_i—class的所有可用空闲时间片集合，再找出Task—i---~TeacherId的所有可用空闲时间 片集合，求这两个集合的交集，这交集就是当前Task—i可用的时间片集合； ② 在当前Task—i可用的时间片集合中找出一个最适合的时间片，作为当前Task—i的教学时间； (4)设置Task_i—class(行政班)的教学时间，即设置该时间段为已占用； (5)设置Task—i---~TeacherId(任课教师)的教学时间，即设置该时间段为已占用； (6)继续进行下一教学任务的教学时问分配； (7)继续进行下一教学任务组的遍历； 4．4．1．2 查找教学任务的合适教学时间 针对当前Task—i(教学任务)找一个合适的教学时间的算法如下： (1)获取当前教学任务Task_i—class(行政班)的可用时问片集合，如果该集合是空集，就返回 NULL； (2)获取当前教学任务Task—i---~TeacherId(任课教师)的可用时间片集合，如果该集合是空集，就返 回NULL； (3)求行政班可用时间片集合与任课教师的可用时间片集合的交集，该集合就是当前教学任务可 用的时间片集合，如果该交集是空集，说明当前教学任务没有可用的时间片，为该教学任务排课失败，就 返回NULL； (4)在时间片集合中对时间片排优先级，判断哪些时间片是最优的，判断的主要依据：当前教学任 务所在教学任务组TaskGroup的优先排课时间表、教师的日平均负荷、同一门课程的时间片限制、学生 的平均日负荷等； (5)在教学任务可用时间片集合中取最优的时间片作为本教学任务的教学时间；把该教学时间添 加到已尝试的时间片集合中； (6)若找到合适的教学时间，就返回所找的教学时间，否则就返回NULL(代表未找到)； 4．4．2 教室的安排 当为所有教学任务指定了合适的时间后，剩下的工作就是指定教室．在为教学班安排教室时，也需 要设置一定的优先级，需要特定教室的教学班先安排，再安排需要特定教室类型的教学斑，教学班的人 维普资讯 http://www.cqvip.com 上海师范大学学报(自然科学版) 2006年 数越多，优先权越大．即对教室约束条件大的教学班安排教室的优先权越大，对教室约束条件越小的教 学班优先权越小．如果为教学班安排教室出现冲突时，即不能为某教学班安排教室时，可以考虑重新为 教学班安排其他时间片，最终使该教学班找到合适的教室． 4．4．2．1 为已经安排教学时间的教学任务分配教室 (1)遍历所有TaskGroup(教学任务组)．按TaskGroup的优先组从高到低进行遍历； (2)遍历当前TaskGroup中的所有Task—i(教学任务)； (3)针对当前Task—i(教学任务)找一个合适的教学地点，若找不到就把当前Task_i(教学任务)设 置成不能分配教学地点； (4)设置Taskj的分配的合适教室ID，即Taskj— Room~的值； (5)设置Taskj— Room j(教室)的时间段，即设置该时间段为已占用； (6)继续进行下一教学任务的教学地点分配； (7)继续进行下一教学任务组的遍历； (8)若存在不能分配教学地点的Task—i，继续遍历这些Task—i，为这些Task—i重新分配教学时间， 使分配了新的教学时间的教学任务能够分配合适的教学地点． 4．4．2．2 查找教学任务的合适教学地点 针对当前Task—i(教学任务)找一个合适的教学地点的算法如下： (1)根据当前Task—i---~LessonNum、Task—i---~TimePieceStr(分配的教学时间)、Task-．i_+RoomType(教 室类型)，得到满足Task—i教学要求的教室的集合； (2)若集合元素个数为0，看是否有可替代的教室集合，若没有就返回NULL，否则进行下一步； (3)对这些按空闲程度进行排序，找出最不空闲的 Room~，并返回 Room_j； 程序算法过程： A、建立行政班对象列表．根据行政班表建立行政班对象列表； B、建立教学任务组对象列表．根据教学任务组表建立教学任务组对象列表； c、根据每一个教学任务组，初始化建立该组下的所有教学任务对象，形成一个教学任务对象列表； D、在初始化某教学任务对象时，初始化任务教师对象，并设置教师对象和教学任务对象的关系； E、在内存中进行排课； F、显示排课结果； G、把排课结果存放到数据库的相关表中． 伪代码如下： ／／对需要 自动排课的课程教学班进行优先级排序 SortPri4CourseList()；／／ Foreach(Task—Course in CourseList)／／遍历课程教学班 { WeekDaySort()；／／将一周内各天次按照班级、教师占用次数升序排列，以便于时间安排时从该班 级、该教师一个星期之内最闲的一天开始查找，即模糊原则9 m = 0； WHILE(1TI，1TI)；／／针对当前任务的课：元安排合适的时间片 IF SetOneTimePiece(Task—Course<当前工作任务>，m)THEN{一次讲次安排成功，后有说明} { ModifyRoomuseNum(Task-j—Rn)；{修改Task_i—Rn的教室占用次数} 维普资讯 http://www.cqvip.com 第5期 潘以锋：高校智能排课系统的算法 INC(HasArrangeNum){成功安排的讲次加1} EXIT；{跳出FOR循环} } E E／／如果为该讲次安排不成功 { SetTimeFailFlag(Task—Course)；／／设置安排失败的讲次”时间安排失败”的标志 } m++；／／计数变量加1 } } 5 结束语 对于复杂的高校课表编排，合理地利用有限的教室和时间资源是非常重要的．通过对教学任务设置 排课优先级以及对时间资源、教室资源采取有效的优化查找，基本上解决了死锁问题．这样的排课结果 基本上满足了教务处排课工作的要求，而且也大大减轻了教务人员的工作量，提高了排课的效率．本文 作者提出的通过静态设置任务的优先级，分配资源时根据相关参数动态计算其优先级从而达到优化资 源查找的算法对于许多其他的需要安排时间表的场合，例如安排讲座、安排会议、火车调度、车辆调度等 也同样适用． 参考文献： [1] 王 健，董改芳，许道云．自动排课系统的模型与实现[J]．贵州大学学报，2004，21(2)：194． [2] 赵晓庆，熊璋，方义．高校智能排课系统的设计与实现[J]．计算机与现代化，2004，(11)：102． [3] 张健．基于图论的高校排课系统实现[J]．重庆师范大学学报，2005，22(1)：35． [4] 李冰颖，汪琳媛，张元仕，等．高校自动排课系统的分析[J]．中华素质教育，2004，(12)：l14． Algorithm of intelleigent course arranging system PAN Yi—feng (East China Normal University，Shanghai 200000，China) Abstract：Based on the basic units of course for computing the PRI of the course tasks，an algorithm of optimized resource searching used to schedule arranging system．To simplify the algorithm，first，course times are arranged，and then classroom are arranged．This paper designs and realizes an efficient course arranging system． Key words：intelligent course schedule arranging；course schedule arrang／ng；priority；algorithm (责任编辑：冯珍珍) 维普资讯 http://www.cqvip.com