（计算机软件与理论专业论文）禁忌搜索求解排课问题的应用研究.pdf

摘要 摘要 排课问题是涉及班级、教师、教室等因素的决策优化问题，也是组合规划中 的典型问题。在自动排课系统中，处理排课问题所用的算法处于核心地位，由于 排课问题本身的复杂性，寻找这样一个有效算法还是有相当的难度。本文课题来 源于自动排课问题的求解算法研究。 本文借鉴以往的成功经验并结合本学校的实际情况，提出了一种基于禁忌搜 索算法的排课问题解决方案。首先，使用网络最大流算法预处理，把授课任务分 成若干组，同组的任务可以同时进行而不发生冲突，而且保证教室需求量不大于 供应量。然后，使用禁忌搜索寻求任务组与时间的最优组合方式。最后，给任务 分配教室输出课表。本文先给出了算法的总体框架，然后对如何建立网络流模型 以及禁忌搜索的各个要素进行了详细的说明，最后使用真实数据进行了仿真测试。 + f这种方案结合了经典的网络流算法与禁忌搜索算法，使两种算法优势互补， l 带来了较好的处理问题能力。经实际数据的仿真验证，该算法具有一定可行性和 适用性。 关键词：排课问题组合优化网络流禁忌搜索 a b s t r a e t a b s t r a c t c o u r s e - t i m e t a b l i n gp r o b l e m ，a l lo p t i m i z a t i o nd e c i s i o n - m a k i n gp r o b l e mi n v o l v i n g f a c t o r ss u c ha s c l a s s e s ，t e a c h e r sa n dc l a s s r o o m se t c ，i sat y p i c a lp r o b l e mo f c o m b i n a t o r i a lp l a n n i n g i na na u t o m a t e d - c o u r s e - t i m e t a b l i n gs y s t e m t h ea l g o r i t h mo f c o u r s et i m e t a b l i n ge n j o y st h ec o r es t a t u s ，b u ti ti sr a t h e rd i f f i c d tf o ru st of i n da n e f f e c t i v ep r o c e s s i n ga l g o r i t h md u et ot h ec o m p l e x i t yo ft h ec o u r s e f i m e t a b l i n gp r o b l e m i t s e l f t h es u b j e c ts t u d i e di nt h i sp a p e ro r i g i n a t e sf r o mt h er e s e a r c ho nt h ea l g o r i t h mo f a u t o m a t i cc o u r s e - t i m e t a b l i n gp r o b l e m t h i sp a p e ri n t r o d u c e dam e t h o dt os o l v et h ec o u r s e - t i m e t a b l i n gp r o b l e mb a s e do n t a b o os e a r c h f i r s t ，u s e st h en e t w o r km a x f l o wa l g o r i t h mi np r e p r o e e s s i n gt od i v i d et h e t e a c h i n gt a s k si n t os e v e r a lg r o u p s , i nw h i c ht h et a s k sc a nb ec a r r i e do ns i m u l t a n e o u s l y w i t h o u tc o l l i s i o n sa n dt h en u m b e ro ft h er e q u i r e dc l a s s r o o m sn o tl a g e rt h a nt h en u m b e r o ft h es u p p l i e do n e s s e c o n d ，s e e k sab e s tc o m b i n a t i o nb e t w e e nt a s kg r o u p sa n dt i m e s l o t su s i n gt a b o os e a r c h l a s t , a s s i g n sac l a s s r o o mt oe v e r yt e a c h i n gt a s ka n do u t p u t s t h ec o u r s et i m e t a b l e t h i sp a p e rp r o p o s e sa no u t l i n eo ft h ea l g o r i t h ma tf i r s t t h e n , a d e t a i l e de x p l a n a t i o ni sg i v e no nb o wt oe s t a b l i s ht h en e t w o r k - f l o wm o d e la sw e l la s h o wt 0u s et h ee s s e n t i a lf a c t o r si nt a b o os e a r c h f i n a l l y , u s e st h er e a ld a t at oc a r r yo u t t h es i m u l a t i o nt e s t 1 1 1 ei m p l e m e n t a t i o no ft h ep l a n , w h i c hu n i f i e st h ec l a s s i c a ln e t w o r kf l o w s a l g o r i t h ma n dt h em o d e r nh e u r i s t i ct a b o os e a r c ha l g o r i t h m ，c a u s e st h es u p e r i o r i t i e so f t w oa l g o r i t h m ss u p p l e m e n t i n ge a c ho t h e r , a n di m p r o v e st h ea b i l i t yo fp r o c e s s i n g p r o b l e m s a f t e rc o n f i r m e dt h r o u g ht h er e a ld a t as i m u l a t i o n ，t h ea l g o r i t h mw h i c ht h i s p a p e rp r o p o s e di so f c e r t a i nf e a s i b i l i t ya n dt h es e r v i c e a b i l i t y k e y w o r d s ：c o u r s e - t i m e t a b l i n gp r o b l e m c o m b i n a t o r i a lo p t i m i z a t i o n n e t w o r kf l o wt a b o os e a r c h 声明 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 兰! 塞。 日期：塑! ：! 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即；研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文( 保密的论文 在解密后遵守此规定) 。 本人签名：兰! 堑 导师签名：豳 日期：兰翌! ：! r 期：翌：! ：z 第一章绪论 第一章绪论 1 1 排课问题简述 在高校中，教学是培养学生的主要途径。排课的实质足为老师、学生的教学 活动合理安排时间上和空间上的教学资源，以保证教学活动有计划有秩序地进行。 因此在一系列的管理工作中，课表的编排是最基础、最复杂同时也是最核心的工j 作。其主要任务是给课程安排时间、分配教室，同时要保证没有冲突发生( 所谓 冲突就是同一个班或同一老师在同一时间内被安排了两个或多门课程，或为同一 教室在同一时问内安排了多门课程等情况) 。在保证教学资源时间空间的合理分 配以及教学秩序有条不紊的前提下，课表的安排也要保证教学质量，例如数学、 英语等必修课程尽量安排在上午，尽量不要安排在周末的下午；同课程的两次 讲课的间隔尽量在一天以上，以保证学生有充足的作业、消化时间。除此以外还 有许多细节问题，例如同一个班的课程尽量安排在同一个教室或相距不远的教室 里，避免课间休息时间内出现大规模、长距离的人员流动等等。在教学改革不断 深化，招生人数逐年增加的情况下，做好有限教学资源的分配调度工作是有积极 意义的。 课表编排具有规模大、约束条件复杂以及执行过程中不断变化等特点，难以 实现自动化。目前很多学校的排课工作还只能靠教务科的管理员凭经验手工完成， 这一般需要花费大量的时间和精力，而且每学期初的调课换课也是教务科必须的 额外工作负担。要想使各类资源优化利用，排课时需考虑涉及全校上上下下、方 方面面的因素，而人脑处理数据的能力有限，很容易出错，一旦出错就会打乱正 常的教学秩序导致教学事故。所以，完全以手工为主的排课管理已远不能适应新 形势的要求，这就需要有一个较为实用的排课系统使学校课表编排工作能够实现 自动化、高效化、人性化等特点。应该如何实现这样的系统已成为教学管理人员 和技术专家共同面对的一个令人困扰的难题，这也是当前研究的热点。 排课系统的核心是处理排课问题所用的算法。使用有效的算法才能事半功倍， 而且这也是保证排课系统可行性、运行稳定性、结果正确性的必要条件。由于排 课问题本身的复杂性，寻找一个有效的处理算法还是有相当的难度。在求解排课 问题算法上的基础研究工作也为众多科研机构和研究者所关注，这也是本文研究 课题的来源。 2禁忌搜索求解排课问题的应用研究 1 2 1 排课闷题的历史 1 2 国内外研究现状 排课问题也可称为课程时间表问题( c o u r s e - t i m e t a b l i n gp r o b l e m ) ，是一个涉 及多种因素的基于时间规划和组合优化的问题。由于问题具有的难度和挑战性， 许多研究者在这上面投入了大量精力，并取得了丰硕成果。从二十世纪五十年代 以来，国际上就有人开始研究计算机自动排课问题。1 9 6 2 年，g o t l i e b c c 教授就 对课程表问题进行了形式化描述，即一系列规划组合问题。到了7 0 年代，s e v e n 等人将排课表问题理沦化。1 ，证明该问题是一个n p 完全类问题，根据计算理论和难 解性理论，排课表问题没有多项式算法。当问题的规模增大时，解的数目呈指数 函数增长，在一般的实际情况中是不可能准确地求出最优解的。随着算法复杂性 理论的完善，人们不再强调一定要求得最优解，更多的研究转向实际应用的角度， 能够得到较好的解得近似算法，或以一定的概率保证解的质量的随机算法的研究 越来越受到重视。于是兴起了现代智能优化技术，出现了崭新的智能优化算法， 诸如人工神经网络、遗传算法、蚁群算法、进化计算、模拟退火、禁忌搜索及其 混合优化策略等。自从2 0 世纪8 0 年代以来，这些优化技术在诸多领域得到了成功 应用，使得排课问题的研究也出现了崭新面貌，直到今天仍有巨大的发展。 1 2 2 排课问题的求解方法 早期的计算机自动排课技术是基于模拟人工的做法，被称为“直接启发式” ( d i r e c th e u r i s t i c s ) 的连续增广方法。3 ，把课程逐步添入现有课表，直到所 有课程都被排入课程表或者没有不违反约束条件的课程可排。显然，这种方法缺 乏理论的指导和普遍的适用性。 后来有研究者把排课简化为人们熟知的经典问题求解，出现了整数规划“1 ( i n t e g e rp r o g r a m m i n g ) 的方法，另外还有基于网络流嘲( n e t w o r kf l o w ) 和基于 图染色o m ( g r a p hc o l o r i n g ) 等的算法。这些方法建立在排课模型极大简化的基 础之上，一般只考虑寻找可行解而忽略了其他优化条件。 再后来，随着现代智能优化技术的出现和发展，出现了关联规则算法、分支 定界算法、分组优化决策算法、启发式数值算法、模拟退火算法、遗传算法、蚁 群算法等新方法，它们在排课问题的求解上取得了较大成功。下面对这些研究成 果进行简单介绍。 ( 1 ) 关联规则算法 文献 9 介绍了采用布尔( b o o l e a n ) 型关联规则f p g r o w t h 算法的思想来处理 第一章绪论 排课问题。考虑了班级冲突、教师冲突和教室的冲突，避免了排课冲突，能够基 本满足需求，但对于多学时课程的离散性问题、好的教学日和教学时间点如何合 理分配等问题没有很好的解决。 ( 2 ) 分支定界算法 文献 1 0 描述了采用枚举法进行搜索。在对一棵庞大的树进行搜索时，大胆 地将无可行点的大量分支去掉，即采用分支定界法来剪枝。这棵树的根就是排课 的起点。定界采用一种判别原则，即在排课程表时，定义一种抽象的界，使得在 排到某个课时，判断它是否超过了这个界。如果超过了这个界，就把它剪掉。这 是一种非完全的穷举法，有可能过早产生可行解而进入局部最优解的陷阱。 ( 3 ) 分组优化决策算法 文献 1 1 介绍了分组优化决策算法。这是模拟人工排课表的一种方法，按先 难后易的原则，分组逐次排课。在待排的课程集合中挑选排课难度大的课程组先 排；其次对课程组排课时，先搜索本课程组的课程在当前的阶段课表条件下的所 有可用的时间和教室，并用优化方法抉择出其中的特定时间，将本课程组各个课 程排入课表。优化抉择的原则是，所选择的某个时间，应使与本课程组相关的课 程，在后续排课时产生的不利影响要小。由于利用这种算法在编排课表时是对全 部的课程的一个部分进行编排，这样最终形成的课程表就可能是局部的最优解， 而不是全局的。 ( 4 ) 启发式数值算法 文献 1 2 提出了求解排课表问题的启发式数值算法，就是根据排课问题特性， 通过构造典则型运输网络，把课表问题转化为典则型运输网络中求最小费用最大 流问题。具有易于编程实现、收敛性好等优点。这种方法是建立在约束条件极大 简化的基础上，只解决教师、班级时间上的冲突，不考虑课程对教室的要求以及 课程对上课时间的要求。处理的情况较为简单，主要适用于中小学的排课表问题。 ( 5 ) 模拟退火算法 模拟退火算法是一种启发式的随机搜索算法，往往能在较短的时间和较大的 解空间内找到最优解，对解课表这样的组合优化问题是很有效的。文献 1 3 介绍 了用模拟退火算法实现交互性的课表问题求解方法。其目标函数诸因数的权值可 以由用户设定和修改，从而使退火结果所获得的解尽可能满足不同用户对课表质 量的要求。 ( 6 ) 遗传算法 遗传算法是一种智能性的算法，具有本质并行、自组织、自适应和自学习等 特性。用遗传算法来解决排课时间表问题有较多的应用m 邬州川“”哪1 。在现 有的遗传算法求解排课问题中，能够对其所使用的学校的排课问题进行求解，在 一定程度上取得了很好的成果。 4禁忌搜索求解排课问题的应用研究 ( 7 ) 蚁群算法 蚁群算法是通过模拟蚁群在觅食过程中寻找最短路径的方法来求解优化问 题。文献 2 2 提出了基于二部图的排课问题模型；并揉合蚁群算法a s 、a c s 、m 姒s 三个不同模型的优点，提出一种面向排课问题的改进型蚁群算法。算法中先把大 部分课程都安排好，再解决所遇到的冲突，一步步地接近最优解。 1 2 3 当前研究趋势及存在的问题 由于排课问题充满挑战性，加上优化技术的不断发展，近年来关于排课算法 的研究活动及研究成果可谓层出不穷。m e t a h e u r i s t i c sn e t w o r k 于2 0 0 2 年举办了 以求解时问表问题为目标的程序设计竞赛t t c o m p 呦1 ( i n t e r n a t i o n a lt i m e t a b l i n g c o m p e t i t i o n ) 。此项赛事由p a t a t ( i n t e r n a t i o n a lc o n f e r e n c eo f f t h ep r a c t i c e a n dt h e o r yo fa u t o m a t e dt i m e t a b l i n g ) 赞助，这为各种新颖思想提供了交流与 展示的平台，而且获奖者将得到p a t a t 的与会邀请。 这里简要介绍一下t t c o m p 竞赛获奖者及他们所用的方法。 冠军是p h i l i p pk o s t u c h ，他使用了基于模拟退火的启发式方法1 。把求解过 程分为两个阶段：先用基于图染色的方法构造出一个可行的课表，然后用模拟退 火算法来调整这个课表，调整的依据是一个目标函数值。 亚军是b r i g i t t ej a u m a r d 、j e a n f r a n g o i sc o r d e a u 和r o d r i g om o r a l e s ， 他们使用了禁忌搜索算法哺1 。一先构造出一个可行解，然后使用禁忌搜索算法改善 这个可行解，以获得更优的目标函数值。 第三名y u r ib y k o v 使用了g r e a td e l u g e 局部搜索算法嘲旧1 。 排课问题属于时问表问题的一类，在p a t a t 国际会议上它是研究讨论的热点和 重点。在2 0 0 6 年8 月第六届p a t a t 上向人们展示的求解技术手段主要有”1 ：限制策 略( c o n s t r a i n t b a s e dm e t h o d s ) ，进化计算( e v o l u t i o n a r yc o m p u t a t i o n ) ， 人工智能( a r t i f i c i a li n t e l l i g e n c e ) ，图染色( g r a p hc o l o r i n g ) ，专家系统 ( e x p e r ts y s t e m s ) ，启发式搜索( t i e u r i s t i cs e a r c h ) ，知识系统( k n o w l e d g e b a s e ds y s t e m s ) ，模拟退火( s i m u l a t e da n n e a l i n g ) ，局部搜索( l o c a ls e a r c h ) ， 数学规划( m a t h e m a t i c a lp r o g r a m m i n g ) ，软计算( s o f tc o m p u t i n g ) ，禁忌搜 索( t a b us e a r c h ) ，元启发式( m e t a - h e u r i s t i c s ) ，超启发式( 1 l y p e r h e u r i s t i c s ) ， 超大规模邻域搜索( v e r yl a r g en e i g h b o r h o o ds e a r c h ) ，蚁群算法( a n tc o l o n y m e t h o d s ) ，混合优化策略( h y b r i dm e t h o d s ) ，多目标决策( m u l t i _ c r i t e r i a d e c i s i o nm a k i n g ) ，模糊推理( f u z z yr e a s o n i n g ) ，组合优化( c o m b i n a t o r i a l o p t i m i z a t i o n ) 等等。 可以看出，当前求解排课问题方法的研究趋势，是使用经典搜索算法与现代 第一章绪论 5 智能优化算法相结合的方式求解；使用这些方法求出的一般不是最优解，但是常 常能满足实际的需求。 尽管研究的成果颇丰，但是在各种具体情况的应用中，排课问题具有以下一 些共同难点： ( 1 ) 没有确定的多项式时间算法，它在计算理论上属于n p 完全问题。 ( 2 ) 很难设计出有效的启发算法，即使用上各种高级的启发式搜索技术，进 行高效的状态空间剪枝，仍无法保证找到最优解。 ( 3 ) 不存在通用算法，适用于某些情况的算法的方法可能不适用于其他情况， 特定的条件往往只适用于特定的实例。 ( 4 ) 现实世界中的时间表安排问题常常需要考虑许多约束条件，必须考虑到 个人的特殊情况和政策管理的规定，这是无法精确描述或表达的。 这些难点说明，别人的成功算法只是较好解决了他们特定情况下的某一类问 题而已，方法不具备通用性，仅仅是提供参考。针对我们具体的实际问题，只能 自己寻找并设计满足要求的求解方案。 1 3 本文的研究意义及所做工作 排课问题是对教师、班级、教室、时间等因素进行配置的决策优化问题，在 计算理论上属于n p 完全问题。大量实践经验表明，使用现代启发式优化算法来求 解n p 问题足一种可行的选择。禁忌搜索足局部邻域搜索算法的扩展，是人工智能 在组合最优化算法中的一个成功应用。与模拟退火、遗传算法等启发式优化算法 相比，禁忌搜索算法的性能是较好的”3 。为了研制自动排课系统的需要，本文借 鉴以往的成功经验并结合本学校的实际情况，提出了一种基于禁忌搜索算法的排 课问题解决方案，所做的工作如下： ( 1 ) 分析了本学校( 西安电子科技大学) 教务流程的特点以及制定课表的原 则，对排课需求进行了分析描述，建立了排课问题的组合优化数学模型。 ( 2 ) 介绍了组合优化问题的一般概念以及求解这类问题的启发式算法理论， 并对禁忌搜索算法进行了较深入的探讨。 ( 3 ) 提出一个比较符合实际情况的基于禁忌搜索的排课问题求解方案。首先， 基于二部图以及网络流的理论，提出一个对授课任务分组预处理的方法。然后， 使用禁忌搜索算法寻找授课任务与时间的最优化组合。最后，使用基于贪心算法 的思想安排上课教室。这个方案大大简化了教师、学生、教室这三者的冲突处理 过程，提高了禁忌搜索算法的收敛速度，并易于程序的实现及功能的扩展。 6禁忌搜索求解摊课问题的应用研究 1 4 论文结构 本文共分为五章： 第一章绪论。提出论文研究的对象以及国内外相关研究发展现状，介绍本文 工作及其意义。 第二章排课系统模型的建立。对西安电子科技大学教务流程以及排课工作特 点进行介绍。并且对排课系统进行需求分析，建立求解模型。 第三章禁忌搜索算法理论研究。对组合优化问题进行描述，对现代启发式优 化算法进行介绍和分析，并着重介绍了禁忌搜索算法。 第四章求解排课问题的禁忌搜索算法。首先对算法进行设计，提出实现方案， 然后进行实例执行分析。 第五章总结与展望。对全文所做工作进行总结，并提出需要改进之处和进一 步研究方向。 第二章排课模型的建立与分析 7 第二章排课模型的建立与分析 2 1 1 教务流程简介 2 1 西电教务流程及排课特点简介 教务工作目的在于为教学活动分配时间上和空问上的教学资源，教学资源的 调度是否合理，关系到全校师生的学习工作能否正常进行。课表的编排在教务工 作中处于核心地位。教务工作步骤简单介绍如下： ( 1 ) 制定专业教学计划。本科专业教学计划是各专业指导学生按照一定的进 度分学期修读课程的计划，也是学生毕业资格审核和获取学位的依据。教学计划 里安排有八个学期，每个学期的课程包括基础课、专业课、实践环节等等。 ( 2 ) 制定教学实施计划。教学实施计划( 执行纪要) 是对教学计划的执行过 程管理。各学院每学期都按班制定下一个学期的实施计划，即确定学生应该上什 么课。实施计划制定好后向教务处提交。 ( 3 ) 制定教学任务书。教务处根据实施计划把全校教学任务汇总，并制定教 学任务书。任务书向学院下达，由学院根据教学任务安排执行教师，安排好之后 再交回教务处。教务处只负责制定并下达低年级( 一、二年级) 的任务书，因为 公共课比较多。例如全校各学院都要上英语课，而全校英语课的上课任务只能由 人文学院外语系安排。对于高年级( 三、四年级) 的任务书，各学院可以自己制 定，因为专业课上课老师一般来自本学院。 ( 4 ) 编排课表。管理部门根据任务书进行课程表编排。教务处负责排低年级 的课程表，各学院自己排高年级的。特殊课程由相应管理部门编排好，再报送教 务处汇总。因为上课的地点比较特殊，需要专门的调度管理。例如体育课的课表 由体育部安排，金工实习课表由工程训练中心安排。课表是具体到本学期每一天 的日课表，编排好后由教务处统一印发各单位。如果学生、老师有意见可以提出 并让管理部门修改。 ( 5 ) 制定教室调度表。为了对教室进行管理，每个学期要根据课表制定教室 调度表，每个教室一张，也是课表的形式，记录本教室所有时问的内的使用信息， 包括是否被使用，使用班级、老师，是否使用多媒体设备等。这样可以在课程需 要调整时间或者安排临时活动时，很方便地找到可用的空闲教室。 教务工作的简要流程啪1 如图2 1 所示。 8禁忌搜索求解排课问题的应用研究 图2 1 教务工作简要流程图 从流程图中可以看出课表在教学教务工作中的核心地位。目前，编排全校两 百多个班的课表有专门的老师负责，大约要花3 至4 个月的时间；然后制定教室 调度表，至少要花1 个月时间。为满足老师或学生提出的特殊要求，可能要对排 好的课表进行调整。由于课表中错综复杂的关联关系，调整某个班一门课的时间 地点，就会带来其他课程的连锁的调动。完成这些工作，不仅劳动时问长、强度 大，而且要求管理员具备一定的经验和耐心。 2 1 2 教学教务信息系统简介 随着i n t e r n e t 和信息技术的发展，我国高校教育信息化建设成为信息化建设的 第二章排课模型的建立与分析 9 前沿阵地和信息时代的弄潮先锋。教育部( 2 0 0 3 - - - 2 0 0 7 年教育振兴行动计划进 一步明确做出了实施“教育信息化建设工程”的战略部署。在新的形势下，西安电子 科技大学加大了信息化建设工程的力度，希望通过教育信息化建设对转变教育思 想和观念，促进教学改革，加快教育发展和管理手段的现代化起到积极作用。西 安电子科技大学教学教务信息系统是整个信息化建设工程中的一个重要组成部 分。 教学管理信息化是系统的一个重要功能模块。本系统构造了一个基于网络的， 数字化和智能化有机结合的教育环境和管理环境，并且在这个环境中架起了一座 新的、无限开放的教学教务管理工作平台。在这个平台上，所有的教育资源将得 到沟通，新的教育教学规律将要在这个平台上产生并得以运行。教学教务管理人 员可以利用现代化的信息手段，以全新的观念和理论去重新审视和指导教育教学 活动的各个领域和环节，提高了教育教学的效率。 目前教学教务信息系统第一期工程已经完成。在教务工作模块中，实现了从“制 定教学计划”到教学任务书相关工作的信息化管理，教务相关的数据信息可以完 全使用计算机存储控制。这些工作的完成为下一步研制自动排课系统打下了坚实 基础。 2 2 课表的制定原则 课表编排的科学与否，直接影响到教学活动的有序和效果，必须在充分认识 课表功能的前提下，依照编排原则，进行科学地编制。”。 课表的功能包括内部功能和外部功能。 内部功能： ( 1 ) 课表是教学活动的总调度，是学生在校活动的有序排列。 ( 2 ) 课表是教学计划在时问和空问上的具体体现。 ( 3 ) 课表是在校教师、学生、管理人员与教室、教学设备及各种教学器材等 诸多事物相互联系、相互作用的纽带与桥梁。 外部功能： ( 1 ) 课表是学校教学思想、改革措施的外在反映。 ( 2 ) 课表是学校教学体制、管理体制的一种特殊表达形式。 ( 3 ) 课表是优化教学秩序和教学环境，充分合理地利用学校的一切入力、物 力资源，提高教学质量的重要保证。 课表编排涉及学校上上下下、方方面面的工作。编排部门要协调好教学、科 研等各种关系；处理好教师、学生、教室、场地、时问多种矛盾；最大可能满足 各院系、部门、各教研室的不同要求。因此，课表编排过程就是完成一个动态的 1 0 禁忌搜索求解排课问题的应用研究 闭合系统工程，在制定和执行课表过程中，需要坚持多方面原则。 ( 1 ) 整体化原则 课表要为完成教学计划服务，为提高学校教学质量和实现培养目标服务。学 校的中心工作是教学，课表要从教学需要出发，使教师、教室、场地、时问等首 要保证教学需要。课表要面向全体学生，一切为学生的德智体全面发展德复合型 人才服务。课表要照顾教师和学生的利益和要求，但必须局部服从全局，在整体 利益不受到损害德前提下，局部和个体利益可给以照顾。 ( 2 ) 最优化原则 学校管理的目标是以最少的资源( 人力、物力、财力和时间等) 达到最好的社 会效益，这就是最优化原则。编排课表要从最优化原则出发，对现有的教师、场 地、教室、设备及学生状况等进行调查和研究，以寻求各种教学活动的最佳编排 组合方式。要达到课表科学、合理、周密、可控，以创造出最优的教学环境和教 学次序，使教师发挥最优的教学效果，使学生的学习效果和质量达到最优。 ( 3 ) 有序性原则 任何系统都有其自身存在的具体的时空形式。时空形式不同，构成不同的系 统结构作为动态闭合系统存在的课表，根据教学计划的要求，各学制、各专业、 各年级、各班都有自己的课程编排方式，由于教师、场地、教室、时间、班级的 相互联系而形成一个有机会的整体，相互作用、相互制约、相互影响、使课表系 统按照固定有的规律井然有序地运行着。 ( 4 ) 开放与闭合原则 课表在编排过程中应该表现为开放式。编排部门应广泛征求学校各院系、各 部门、各教研室的意见。了解他们的要求和愿望，对于上课时间、场地安排学科、 术科课程的搭配充分尊重教师的意见。但是，课表在管理形式上有是闭合的。正 式课表下达后，它就成为指挥教学活动的总调度、总权威、任何人、任何部门未 经教学管理部门同意不得擅自更改和调整。否则正常的教学次序就会被打乱，打 破稳定和平衡。当然，个别课程的调整在所难免，但这只能是在统一指挥下的调 度，是局部的、暂时的。只有这样才能保证课表结构的稳定性，维持系统的动态 平衡，保证教学活动的有序。 ( 5 ) 反馈原则 在控制系统中，控制与反馈互为前提，处于统一体中，由于反馈的方向是由 被动系统到主动系统，所以它是一种反作用。课表确定之后成为一个控制系统， 管理部门要及时听取执行过程中的反映，了解教学活动、教学次序、教学效果， 形成多条反馈渠道，及时、全方位收集反馈信息。例如，由教师到教研室到院系 到教学管理部门的反馈渠道；由学生到铺导员到院系到教学管理部门的反馈渠道。 利用反馈信息，最大限度地把课表在执行过程中暴露出的矛盾解决在萌芽之中。 第二章排课模型的建立与分析 情况是复杂的，外界变化因素很多，实践中总有一些意想不到的问题出现，课表 编排不可能十全十美，也不可能适应外界的一切变化，因此信息反馈是课表控制 系统的必不可少的过程和手段。 2 3 排课系统的基本需求分析 排课系统是教学管理系统的子系统，最基本的要求，就是能够结合学校的实际 情况，按照排课的一般原则，通过自动排课算法排定可行的课程表。排课的过程 就是用一定的处理算法，为每一项任务安排时间、地点的过程。排课系统的逻辑 模型图如2 2 所示。 | 输入羹誉任务l 一1 排课算法i 1 输出课农l 图2 2 排课系统逻辑模型图 在“制定教学实施计划”这一步骤中，得到的数据是授课信息集合，这信息是 一个四元组，包括：班级、课程、所需教室类型、周学时。接下来“制定教学教 学任务书”以明确每一项授课任务的执行教师，于是在实施计划的授课信息中再 增加一个上课教师信息，于是得到五元组：班级、教师、课程、所需教室类型、 周学时。系统的输入就是教学任务书中确定下来的“授课任务”五元组信息集合。 系统的输出是课表单元集合，课表单元是确定了上课教室和时间的授课任务，因 此它们也是五元组，包括：班级、教师、课程、教室、时问。 根据排课人员的经验，考虑的问题主要有以下7 条： ( 1 ) 同一学生( 或班级) 在同一时间只能上一门课程。 ( 2 ) 同一老师在同一时间不能安排两门课程。 ( 3 ) 同一教室在同一时间不能安排两门课程。 ( 4 ) 教室容量应略大于上课人数，并且教室类型要满足课程要求。 ( 5 ) 同一个班的各课程应该安排在相距不远的若干个教室里。 ( 6 ) 课程节次安排。课程的教学效果与上课的节次是有联系的，尽量将课程 安排在教学效果较好的节次中。譬如，学生精力在上午比较充沛，这时尽量安排 难度较大的或比较重要的必修课；而下午最后一节课，学生大多疲劳而且精神不 太集中，安排人文素质课或选修课比较好。 ( 7 ) 课程周次组合。对于周学时大的课程( 大于等于4 课时) ，每周至少要安 排两次课。应该避免这两次课安排在同一天，最好将其进行隔天安排，具备较好 的分散度的课程才有好的教学效果。 根据上述要求，我们可以得出下面结论。首先，满足前4 条要求的课表才是可 以执行的合法课表，否则会因时问地点发生冲突或教室不合适而出问题。因此前4 禁忌搜索求解排课问题的应用研究 条是必须满足的约束条件，可称为硬约束( h a r dc o n s t r a i n tc o n d i t i o n ) 。其次，满 足从第5 到第7 条的要求才是令人满意的课表。这些条件不是强制性的，可称为软 约束( s o f tc o n s t r a i n tc o n d i t i o n ) 。只要能排出课表，就能根据需要输出各种形式的 表格，譬如班级课表、教师课表或教室使用表。如何根据约束关系建立模型并求 解是下面的工作重点。 2 4 1 符号约定 2 4 排课问题模型 考虑以下几类资源以及相关函数： 课程集合：l = ，乞，l p9o * 9 l r ) ； 班级集合：c = c i ，c 2 ，c n ，c n ；n u m ( 已) 表示取班级q 的人数； 教师集合：h = ( 啊，如， ； 教室集合：r = o ， 其中t a s k = ( c ，h ，s ，们，表示教师h 给班级c 讲授课程，需要使用类型为的s 教室，讲授w 课时。t r t y p e ( c ，h ) 表示获取教师h 给班级c 上课所需要的教室类型 ( s = t r t y p e ( c ，) ) 。 课表单元集合：c t = c t l c t = ( c ，h ，t ，r ) ，c c ，h h ，厶t t ，r 。其中 c t = ( c ，h ，t ，) ，表示元任务( 教师h 给班级c 讲授课程，) 安排在t 时间r 教室里。 课表单元集合是最终输出结果。 2 4 2 建立组合优化模型 排课问题的求解目标是寻找一个从授课任务到时间教室二元组的映射关系： f ：t a s k t a s k ( f ，r ) e t x r 这个映射关系满足约束条件，并且具有最优的目标函数值。 2 4 2 t 约束条件定义 这里把满足合法课表的强制约束( 硬约束) 作为本模型的约束条件。把4 个约 束条件定义描述如下： 第二章排课模型的建立与分析 。f1 班级巳在时间0 在教室吒上教师k 的课程0 首先，令_ k ，弛2 1o 4 9 否贝i “ ( 1 ) 同一班级在同一时间只能上- - f q 课程。 墨：矗k ，鸺1 ，( 胛= l ，2 ，nq = 1 2 ，q ) m = lp = lk = l ( 2 ) 同一老师在同一时间只能安排一门课程。 r ：k 协1 ，( p = l ，2 ，p , q = 1 ，2 ，q ) ( 3 ) 同一教室在同一时间只能安排一门课程。 恐：k 鸺m = 1 ，2 ，kq = 1 2 ，q ) n = lm = lp = l ( 4 ) 教室容量应略大于上课人数，并且教室类型要满足课程要求。 蜀：n u m ( c , ) c a p ( r k ) ，k 铆白= l ， ，并且t r t y p e ( c , ，) = t y p e ( r k ) ，= l 2 4 2 2 目标函数定义 排课过程中，一般要在满足硬约束的基础上尽量满足软约束条件，因此这里 把软约束作为目标函数。由于这些约束情况比较复杂，难以用符号精确描述，暂 且先用取) 表示，并假定最优解能使得坟x ) 值最大。目标函数估值需要特殊的计算 处理过程，留在具体问题中再做具体处理。 2 4 2 3 模型描述 排课是在约束条件下的决策优化问题。根据目标函数和约束条件，建立模型 如下： m a ) 厂( x ) “r r 1 r 2 r 3 r 2 5 本章小结 本章首先介绍了西电教务工作特点以及课表的制定原则；然后提出了一个捧 课系统的逻辑模型，并对其功能进行了需求分析；最后建立了排课问题的决策优 化模型。该模型的求解方法将在后面章节讨论。 第三章禁忌搜索算法理论研究 i s 第三章禁忌搜索算法理论研究 3 1 1 组合最优化概念 3 1 组合优化问题的求解 组合优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) 是通过对数学方法的研究去寻找离散事 件的最优编排、分组、次序或筛选等，是运筹学( o p e r a t i o n sr e s e a r c h ) 中的一个经 典并且重要的分支，所研究问题涉及信息技术、经济管理、工业工程、交通运输、 通信网络等诸多领域。组合最优化问题数学模型的一般描述为1 ： r a i n 厂( 曲 s j g ( 工) 2 0 x d 其中f ( x ) 为目标函数，g ( x ) 为约束函数，x 为决策变量，d 表示有限个离散点组成 的集合。 因此，一个组合最优化问题可用三参数( d ，f ，) 表示，其中d 表示决策变量 的定义域，f 表示可行解区域f = p l g ( x ) 0 ，x d ) ，f 中的任何一个元素称为该 问题的可行解，f 表示目标函数，满足f ( x ) = r a i n f ( x ) i x f 的可行解x 乖家为该 问题的最优解。组合优化问题的特点是可行解集合为有限点集。由直观可知，只 要将d 中有限个点逐一判别是否满足g ( x ) 的约束和比较目标值的大小，该问题的 最优解一定存在和可以得到( 除非可行域为空集) 。因为现实生活中的大量优化问 题是从有限个状态中选取最好的。首先要定义状态的转移规则，然后才能遍历这 些状态并从中选出最好的。由于状态空间规模的巨大，不可能对其进行完全的遍 历，下面介绍一个可行的简单邻域搜索策略。 3 1 2 邻域及邻域搜索 3 1 2 1 邻域的概念 对于组合最优化问题( d ，f ，力，d 上的一点到d 的子集的一个映射 n ：x e d ( 曲2 。 称为一个邻域映射，其中表示d 所有子集组成的集合。0 ) 称为x 的邻域， y ( 曲称为x 的一个邻居。例如在k 个城市t s p 问题中，假设x = ( 而，而，黾) 表 示一条经过所有城市的路线，则n ( x ) 可定义为 1 6禁忌搜索求解排课问题的麻用研究 n ( x ) = ( 而，x j ，气) if ，1 f ，j k ， 这表示x 中交换两个不同元素而产生的新状态集合。 邻域的定义是状态的转移规则。邻域的构造依赖于决策变量的表示，邻域的 结构在现代优化算法中起很重要的作用。局部最优、全局最优概念跟邻域结构的 定义密切相关。 3 1 2 2 简单的邻域搜索算法 邻域搜索是遍历组合状态并从中选最优的过程。对于组合最优化问题 ( d ，f ，力，假设其邻域结构已确定。设d 为解集合( 这里假设它就是可行域f ) ， f 为d 上的费用函数，n 为邻域结构，邻域搜索( 1 0 c a ls e a r c h ) 算法如下： ( 1 ) 任选一个初始解d 。 ( 2 ) 在n ( s o ) 中按一定规则选择一个s ；若，( s ) 0 ) 。它作为“预处 理”步骤的输入，其中t a s k = ( c ，h ，j ，们，表示教师h 给班级c 讲授课程，需要使 用类型为的s 教室，讲授w 次课( w 是正整数) 。 任务组：g r o u p = 豫i g = ( c ，h ，f ，s ) ，c c ，h h ，三，j s ) 。其中g 称为任务元， 含义基本同t a s k ( 相比之下去掉了课次信息w ) 。 任务组的集合：g l i s t = g r o u p 是“预处理”步骤的输出。 课表单元集合：c