２００９年第９期 大众科技 Ｎｏ．９，２００９ （总第１２１期） ＤＡＺＨ０ＮＧ ＫＥＪ （Ｃｕｍｕｌａｔｉｖｅｌｙ Ｎｏ．１ ２１） 几种自动排课 算法的比较 魏丽丽 （沈阳工业大学，辽宁辽阳１１１００３） 【摘要】排课问题是涉及班级、教师、教室等因素的决策优化问题，也是组合规划中的典型问题。在自动排课系统中， 处理排课问题所用的算法处于核心地位，由于排课问题本身的复杂性，寻找这样一个有效算法还是有相当的难度。文章给出了 高校排课中需要遵循的条件、因素，并且分析了几种当前比较常用的排课算法，对排课性能做了对比，为今后的各种排课需求 提供指导。 【关键词】排课；条件；排课算法；比较 【中图分类号】Ｇ４２３ 【文献标识码】Ａ 【文章编号】１００８—１１５１（２００９）０９—０１７０—０２ 排课是高校教学管理中的一项重要而且难度和复杂度都 学。在能够进行正常教学的情况下还应考虑到教学效果，学 极高的基本工作。近年来，随着我国高校的扩招和合并，学 生学习效率，教师、学生的便利等其他因素。２．排课可以选 校的教学资源如教室、实验室、语音室等愈显紧张；同时， 择的条件。（１）优先安排教室数量有限的课程，如体育课场 在学分制的制度下，课程的类别越分越多，有公共必修课、 地数量少、某类实验室数量少等腰优先考虑，避免出现学生、 公共选修课、专业基础课、专业必修课、专业选修课等等； 教师有空而教室被占用的情况。（２）优先安排合班数大的课 上课教师的一些特殊情况需要考虑，因此能否排出质量好、 程，便于有更多能容纳大量学生的备选教室和避免以后安排 效率高的课表，直接影响着学校的教学质量以及教学资源的 多个班级合班上课时产生时间冲突。（３）优先安排周学时数 合理利用率。课程表的编排就是解决对时间和空间资源争夺 大的课程，将该课程均匀地问隔分散在不同的日期内，让学 而引起的冲突，理论和实践表明，只要课程表所涉及的信息 生有充分的课余时间消化教学内容、完成作业，教师也有充 量稍有增加，就会导致“组合爆炸”使得编排方案剧增 目 足的时间备课、批改作业 （４）优先安排有多门课程的教师， 前，一方面原因是作为一个很复杂的系统，排课要想面面俱 避免出现学生有空、教室有空而教师没有空的情况。（５）优 到是一件很困难的事；另一方面每个学校由于其各自的特殊 先安排有特殊要求的教师，便于找到合适的时问来排课，否 性，自动排课软件很难普遍实用，特别是在调度的过程中一 则可选择的时间位置将会受到很大的。（６）优先安排“考 个很小的变动，要引起全部课程的大调整，这意味着全校课 试”类型课程，对“考查”类型课程的安排可放到后面进行。 程大变动，在实际的应用中这是很难实现的事。 （７）安排上课教室时，以学生或教师为主，相对教室固定不 （一）排课中需遵循的条件 动或在邻近教室，避免在课间换教室时较大人流量，为学生 在课表编排问题中涉及到班级、教师、时间、课程、教 和老师提供方便。（８）排课时可注意文科类课程和理科类课 室等５个相互制约的因素，要求将课程、教师、班级、教室 程交叉安排，避免使学生产生倦怠感，有利于提高学习效率。 安排在一个相同的空闲时间，避免冲突且尽量满足一些其它 （９）不要在一天中给教师或学生安排太多课程，最好不要连 条件。１．排课必须满足的条件。（１）不能在同一时间给一位 续上课超过６节， 有利于提高教学效果和学习效率。（１０） 教师安排多个班级课程（合班除外）或同时讲授多门课程。（２） 避免在晚上、周六、周日安排课程，周三下午不排课。 不能在同一时间给一个教室安排多个班级上课（合班除外） （二）排课算法的比较 或多位教师授课。（３）不能在同一时间给一个班级安排多门 有关排课的算法有很多种，比较常用的有遗传算法、贪 课程或同时在不同的教室上课。（４）不能在安排教室时使教 心算法、动态规划法、回溯算法等，选择一个合适的排课算 室容纳人数小于上课学生人数。（５）对于需要特殊场所的课 法不仅可以缩短排课时间还可以增强课表适应度，使其更人 程，如体育课、实验课、外语课、绘图课等，应安排相应的 性化，提高教学效果。 场地、实验室、语音室、绘图室上课。否则无法进行正常教 １．遗传算法（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ，简记ＧＡ）是１９７５年 美国Ｍｉｃｈｉｇａｎ大学Ｊ．Ｈｏｌｌａｎｄ教授首次提出的，并逐渐发 【收稿日期】２００９—０６—１４ 【作者简介】魏丽丽（１９８１一），女，辽宁辽阳人，沈阳工业大学辽阳校区计算机系讲师。 一１７０． 展成为一种迭代自适应启发式概率性搜索算法。近年来，遗 传算法在求解优化问题中得到了成功的运用。ＧＡ是一种抽象 于生物进化过程的、基于自然选择和生物遗传机制的优化技 术，是一种全局优化策略，能避免陷入局部最优。按照“优 胜劣汰、适者生存”的原则，通过快速随机搜索力求找到最 优解或次优解。遗传算法因在解决各类非线性问题时表现出 的鲁棒性、全局最优性、可并行处理性及高效率而深受实际 工作者的喜爱。利用遗传算法解最优化问题，首先应对可行 域中的点进行编码，一般采用二进制编码，然后在可行域中 随机挑选一些编码组作为进化起点的第一代编码组，并计算 每个解的目标函数值，也就是编码的适应度，接着就像自然 界中一样，利用选择机制从编码组中随机挑选编码作为繁殖 过程前的编码样本。选择机制应保证适应度较高的解能够保 留较多的样本；而适应度较低的解则保留较少的样本，甚至 被淘汰。繁殖过程中，遗传算法提供了交叉和变异两种算子 对挑选后的样本进行交换，交叉算子交换随机挑选的两个编 码的某些位，变异算子则直接对一个编码中的随机挑选的某 一位进行反转，通过选择和繁殖就产生了下一代编码组，重 复上述选择和繁殖过程，直到结束条件得到满足为止，进化 过程最后一代中的最优解就是用遗传算法解最优化问题时所 得到的最终结果。遗传算法是基于生物进化理论的原理发展 起来的一种广为应用的、高效的随机搜索与优化的方法，具 备以下特点：（１）处理对象不是参数本身，而是对参数集进 行编码的个体：（２）同时处理群体中的多个个体，即对搜索 空间的多个解进行评估，减少了陷入局部最优解的风险，同 时实现了并行化；（３）不需要搜索空间的知识和其他辅助信 息，而且仅用适应度函数值来评价个体，在此基础上进行遗 传操作，适应度函数不仅不受连续可微的约束，而且其定义 域可以任意设定，这一特点使得遗传算法的应用范围大大扩 展；（４）采用概率变迁规则来指导搜索方向；（５）具有自组 织、自适应和自学习性。利用进化过程获取的信息自行组织 搜索，适应度大的个体具有较高的生存概率，并获得更适应 环境的基因结构。但是算法本身比较复杂，在变量多，取值 范围大或无给定范围时，收敛速度下降，排课耗时较长，当 约束条件太苛刻时，可能没有可行解。 ２．贪心算法是指在对问题求解时，总是做出在当前看来 是最好的选择，也就是说，不从整体最优上加以考虑，所做 出的仅是在某种意义上的局部最优解。贪心算法不是对所有 问题都能得到整体最优解，但对范围相当广泛的许多问题能 产生整体最优解或者是整体最优解的近似解，是一种改进了 的分级处理方法，逐步构造最优解。从问题的某一个初始解 出发，在一定的标准下做出一系列的贪心选择，选择一旦做 出，就不可再更改，即当前状态下看上去最优的选择，逐步 逼近给定的目标，以尽可能快的速度求得更好的解。当达到 算法中的某一步不能再继续前进时则停止。贪心算法的核心 是在所选择的策略中选一个权值最优的策略作为当前策略， 因此贪心算法的好坏主要决定于权值的确定。贪心算法是从 排课问题的某一初始状态出发，依据给出的贪心策略朝最终 排好全部课程这个目标前进一步，判断是否可以求出可行解 的一个解元素，如果可以则继续依据贪心策略向给定目标前 进，求出下一个解元素，直到前进不能再继续时停止，最后 由所有得到的解元素组成问题的一个可行解。贪心算法的缺 点在于解的效果比较差，而最大优势在于极低的时间复杂度， 能做到某种意义上的局部最优，具有不可后撤性，可以有后 效性，一般情况下不满足最优化原理，并且不适用于解决可 行性问题，仅适用于较容易得到可行解的最优性问题。为了 尽量减小贪心算法带来的副作用，使得最后得到的解更接近 最优解，可以在算法尽可能多的地方使用有效的最优化算法 如动态规划。 ３．动态规划法是２０世纪５０年代由贝尔曼（Ｒ．Ｂｅｌｌｍａｎ） 等人提出，用来解决多阶段决策过程问题的一种最优化方法。 所谓多阶段决策过程，就是把研究问题分成若干个相互联系 的阶段，由每个阶段都作出决策，从而使整个过程达到最优 化。基本思路是：按时空特点将复杂问题划分为相互联系的 若干个阶段，在选定系统行进方向之后，逆着这个行进方向， 从终点向始点计算，逐次对每个阶段寻找某种决策，使整个 过程达到最优，故又称为逆序决策过程。动态规划的实质是 分治思想和解决冗余，因此，动态规划是一种将问题实例分 解为更小的、相似的子问题，并存储子问题的解而避免计算 重复的子问题，以解决最优化问题的算法策略。动态规划法 与贪心法类似，都是将问题实例归纳为更小的、相似的子问 题，并通过求解子问题产生一个全局最优解，其中贪心法的 当前选择可能要依赖已经作出的所有选择，但不依赖于有待 于做出的选择和子问题，因此贪心法自项向下，一步一步地 作出贪心选择。但不足的是，如果当前选择可能要依赖子问 题的解时，则难以通过局部的贪心策略达到全局最优解，解 决上述问题的办法是利用动态规划。动态规划法主要应用于 最优化问题，这类问题会有多种可能的解，每个解都有一个 值，而动态规划找出其中最优（最大或最小）值的解。若存 在若干个取最优值的解的话，它只取其中的一个，但是首先 要保证该问题的无后效性，即无论当前取哪个解，对后面的 子问题都没有影响，在求解过程中，该方法也是通过求解局 部子问题的解达到全局最优解，但与贪心法不同的是，动态 规划允许这些子问题不，即各子问题可包含公共的子子 问题，也允许其通过自身子问题的解作出选择，对每一个子 问题只解一次，并将结果保存起来，避免每次碰到时都要重 复计算。因此，动态规划法所针对的问题有一个显著的特征， 即所对应的子问题树中的子问题呈现大量的重复。动态规划 法的关键就在于对重复出现的子问题，只在第一次遇到时加 以求解，并把答案保存起来，让以后再遇到时直接引用，不 必重新求解。 ４．回溯算法有“通用的解题法”之称。用它可以求出问 题的所有解或任一解。概括地说，回溯法是一个既带有系统 性又带有跳跃性的搜索法，在包含问题所有解的一颗状态空 间树上，按照深度优先的策略，从根出发进行搜索，搜索每 到达状态空间树的一个节点，总是先判断以该节点为根的子 树是否肯定不包含问题的解，如果肯定不包含，则跳过对该 子树的系统搜索，一层一层地向它的祖先节点继续搜索，直 到遇到一个还有未被搜索过的子的节点，才转向该节点的一 个未曾搜索过的子节点继续搜索；否则，进入子树，继续按 深度优先的策略进行搜索。回溯法在用来求问题的所有解时， 要回溯到根，且根的所有子都已被搜索过才结束；而在用来 求问题的任一解时，只要搜索到问题的一个解就可结束。回 溯算法解决排课问题时首先要描述解的形式，定义一个解空 间，包含问题的所有解；其次构造状态空间树，这棵树的每 条完整路径都代表了一种解的可能；再次是构造约束函数， 通过描述合法解的一般特征用于去除不合法的解，从而避免 继续搜索出这个不合法解的剩余部分；然后通过ＤＦＳ思想完 成回溯，（１）设置初始化的方案（给变量赋初值，读入已知 数据等）；（２）变换方式去试探，若全部试完则转（７）；（３） 判断此法是否成功（通过约束函数），不成功则转（２）；（４） 试探成功则前进一步再试探；（５）正确方案（下转第１５３页） 一１７１． 还完成了企业委托的废水治理工程项目３０余项，为淮河、太 湖和长江流域的污染物限期达标治理做出了重要贡献，见表 １。因此，环境工程本科培养的专业特色为利用生物技术来解 决复杂的环境污染问题，即环境生物技术。 表１环境工程学科重要在研项目表 设和社会发展需要，培养政治素质好、具有较高科研生产能 力和组织管理水平的高级技术人才。环境工程发展在强化轻 工特色的同时，注重常规环境工程专业素质教学，将环境工 程基本理论同轻工特色教学有机结合，走特色鲜明、学科交 叉、知识面宽的复合型专业人才培养道路。（１）建设高素质 教师队伍。把加强师资队伍建设，不断提高教师队伍的整体 素质，作为环境工程专业建设的重要方面。加强师德建设， 倡导教书育人、为人师表、严谨治学、甘于奉献：加大教师 校内外培训进修力度，通过选派优秀青年教师进修、出国交 流等方式增强师资力量，培养和造就具有创新能力的中青年 教师，积极引进高层次人才，形成可持续发展的优秀人才梯 队；积极为教师创造良好的教学、科研条件。（２）加强产学 研结合，实行人才培养与科学研究模式创新。积极参加学校 创新科研团队，并加强与科研机构和企业进行产学研合作， 建立多渠道、多形式的紧密合作关系，共同培养具有创新精 神和实践能力的学生。依托申请的科研项目，支持教师参与 科技创新；积极沟通，促使企事业单位为学生实习提供支持 和帮助；与研究院所单位联合培养学生。（３）扩大教育交流 在２Ｏ年的发展历程中，从环境工程硕士点的建立，到本 科生教育、博士点的建立和博士后流动站的筹划申请，标志 着江南大学环境工程专业在科学研究、人才培养等方面已逐 步走向成熟、完善，以环境生物技术为发展主体的环境工程 学科逐步得到了同行的认可。回顾２０年的发展历程，特色鲜 明的研究方向设置，高层次、高水平的教师队伍，先进的实 验仪器，完善的教育培养体系和丰富的国内外学术交流在环 与合作，以宽广的视野培养创新人才。以培养特色人才和提 高教育质量为扩大教育开放的指导思想，创造条件，使更多 的师生接触到国内高等教育领域和科学研究的前沿。加强外 部联系，扩展沟通渠道，同清华大学、哈尔滨工程大学、浙 江大学、同济大学、南京大学等院校建立联系，获得参与国 内竞争的机会，开阔视野，提高素质，培养科技创新人才。 【参考文献】 境工程学科发展中起着决定性作用。在人才培养方面，以知 识、能力、素质协调发展为培养目标，积极探索适合新形势 【１】李潜，储金宇，刘宏．有特色的环境工程专业建设的探讨Ⅲ． 大众科技，２００８，１２：１９８－１９９． 的人才培养方案，体现了国家的教育方针，体现了新时期对 人才培养的新要求，为社会输送了一批又一批环境工程专业 人才。 ２．以点带面，促进环境工程学科全面发展。环境工程专 业的建设和发展需要以理论和“三个代表”重要思想 为指导，坚持和落实科学发展观，全面贯彻落实党的教育方 针；不断进行教育观念的更新，以人才培养为根本任务，积 极进行教育教学改革和创新，强化特色，走教学、科研、生 产三结合道路，不断提高教学和科研水平；主动适应经济建 １２江南大学教务处．２Ｉ环境与土木工程学院本科人才培养方 案．２００８，８． 【３】华兆哲，陈坚，堵国成，等．以特色求创新以科研促教学—— 江南大学环境工程本科培养模式的研究与实践【『１．江南大 学学报（人文社会科学版），２００５，３（２）：６９－７３． 【４】李秀芬，李寅，华兆哲，等．从环境工程学科的发展看学科建 设卟无锡教育学院学报，２００４，２４（１）：４２—４４． 【５】何德丈柴立无彭兵，等．特色环境工程专业创新人才培养模式的 探索与实践Ⅱ】．高等教育研究学｛艮２０ｏ７，３ｏ（１）：４７—４９． （上接第１７１页）还未找到则转（２）；（６）已找到一种方案 则记录并打印；（７）退回一步（回溯），若未退到根则转（２）； （８）已退到根节点则排课结束或打印无排课结果。回溯法适 用于解的组合数相当大但仍然有限的那一类问题，一个重要 表问题显得束手无策。遗传算法等后启发式算法在各个问题 领域都取得了很不错的效果，而且都能够处理各个级别的问 题，既可以是简单的问题，也可以是复杂的大型问题，但是 也有自己的问题需要注意，在使用的时候不同场合参数的初 的特性是在搜索执行的同时产生解空间，在搜索期间的任何 时刻，仅保留从开始节点到当前节点的路径。因此，回溯算 法的空间需求为一个常数，即从开始节点起最长路径的长度， 这个特性非常重要，因为解空间的大小通常是最长路径长度 的指数或阶乘。缺点是时间复杂度较大，因此在采用时还需 要谨慎，最好是和其它的算法结合使用。 始化往往不同，这是一个既重要而又难以处理的问题。因此， 把多种算法结合在一起排课会有更好的效果。 【参考文献】 【１】朱莉娟，李冬计算机排课问题中几种算法的探讨田．新乡教 育学院学报．２００７，（９）． （三）结束语 至今为止有很多的方法技术和算法都已经被用来尝试解 决时间表问题或者大学课程表问题，效果各不相同，有的完 成很出色，有的则只在某些特定情况下才能有不错的效果。 传统的算法比如说回溯算法和动态规划在应付简单时间表问 题和课程表问题时可以较容易的编码，通常情况下可以 地完成任务，但是通常对于大型的复杂约束时间表或者课程 ｉ２１郭东伟．遗传算法运行机理的研究【ＤＩ．．长春：吉林大学， ２００２：８２９． ［３】赵光哲．大学排课问题中的遗传算法设计［Ｄ１ｌ＿占林：延边大 学，２００６．３． 【４］周培德．算法设计与分析ｆＭ】．北京：机械工业出版社， １９９６：９１－９２． 【５】吴志斌，陈淑珍，孙晓安．回溯算法与计算机智能排课田．计 算机工程，１９９９（３）． ｌ５３． 一
