（计算机软件与理论专业论文）大学课程表问题中的算法研究与应用.pdf

摘要 课程表问题( u t p ) 是一个应用广泛的、典型的组合优化和不确定 性调度问题，并且已经被证明是n p 完全问题。随着高校规模的不断 扩大，和教学管理信息化的不断深入，传统的手工排课和计算机辅助 排课已经越来越难以适应现实的需求，而自动化排课系统，因其固有 的高难度和复杂性，它的研究与实现成为完善中南大学网络教学管理 系统十分重要的一环。本文从实际应用出发，基于动态规划的思想， 提出了一种解决大学课程表问题的混合算法，并基于此算法设计并实 现了自动化排课系统。 本文首先介绍了u t p 问题的研究现状、涉及的因素、各种约束条 件，及其数学模型，然后详细阐述了将课程表问题划分为时间片安排 和场地安排两个阶段，分别采用智能算法和最佳适应算法逐段求解， 并最终求得全局较优解的混合算法。然后，对混合算法与经典遗传算 法进行了对比实验分析，结果表明这种分阶段决策的算法在保证课表 质量的同时，能够有效的减小遗传算法在求解u t p 问题中的复杂度， 提高程序的运行速度，也有利于工程应用中对多目标优化的进一步扩 展。 随后，本文基于混合算法，根据项目的实际需求，并考虑到和网 络教学管理系统中其它子系统的集成，设计了排课系统的数据库表和 各个功能模块，结合图表和文字说明，给出了详细的系统实现过程， 并对系统实现过程中的关键技术进行了说明。 最后，总结了本文所做的工作，分析了当前工作的不足及需进一 步研究的工作。 关键词课程表问题，动态规划，遗传算法，排课 a b s t r a c t u n i v e r s i t yt i m e t a b l ep r o b l e m ( u t p ) i sat y p i c a lc o m b i n a t i o n o p t i m i z a t i o np r o b l e ma n du n c e r t a i nm a n a g e m e n tp r o b l e m ，w h i c hi s a p p l i e dw i d e l y ph a sb e e np r o v e dan p - c o m p l e t i o np r o b l e m w i t ht h e e n l a r g e m e n t o ft h e u n i v e r s i t y a n dt h e d e e p e n i n go ft h et e a c h i n g m a n a g e m e n ti n f o r m a t i o n ，t h et r a n d i t i o n a lw a y , a r r a n g i n gc o u r s eb yh a n d ， a n dt h ew a yb yu s i n gc o m p u t e ra s s i s t a n tc o u l dh a r d l ym e e tt h ec u r r e n t r e q u i r e m e n t t h ea n t o m a t i cc o u r s ea r r a n g i n gs y s t e m ，f o ri t si n h e r e n th i g h d i f f i c u l t ya n dc o m p l i c a c y , i t sr e s e a r c ha n dr e a l i z a t i o na r ev e r yi m p o r t a n t f o rt h ew h o l en e t w o r kt e a c h i n gm a n a g e m e n ts y s t e m i nt h i sp a p e r , w i t h t h et h o u g h to fd y n a m i cp r o g r a m m i n g ，am i x e da l g o r i t h mi sp r o p o s e dt o s o l v et h i sp r o b l e m a n da l la u t o m a t i cc o u r s ea r r a n g i n gs y s t e mi sd e s i g n e d a n dr e a l i z e db y u s i n gt h i sa l g o r i t h mi nt h ef o l l o w i n g t h i sp a p e ri n t r o d u c e st h ed e v e l o p m e n t ，m a i nf a c t o r s ，c o n s t r a i n t sa n d m a t h e m a t i cm o d e lo f u n i v e r s i t yt i m e t a b l ep r o b l e mf i r s t t h e ni te x p o u n d s am i x e da l g o r i t h mw h i c hd i v i d e st h ec o u r s et i m e t a b l i n gp r o b l e mi n t ot w o p h a s e s ，a r r a n g i n gt i m eb yi n t e l l i g e n ta l g o r i t h ma n da r r a n g i n gc l a s s r o o m b y b e s tf i ta l g o r i t h m ，a n dg e t st h ew h o l es o l u t i o nb yr e s o l v i n ge a c hp h a s e o ft h ep r o b l e m i nt h ef o l l o w i n g ，c o m p a r e dt h em i x e da l g o r i t h mw i t h c l a s s i c a lg e n e t i ca l g o r i t h m ，i ts h o w st h em i x e da l g o r i t h ma tt h es a m et i m e o fe n s u r i n gt h eq u a l i t yo fr e s u l t ，r e d u c e st h ec o m p l i c a c y , h a v eab e t t e r p e r f o r m a n c ea n de x p a n s i b i l i t y a f t e rt h a t ，t h ed a t a b a s et a b l ea n ds u bm o d u l e sa r ed e s i g n e db a s e do n t h em i x e da l g o r i t h ma n dr e q u i r e m e n t ，t h ei n t e r g r a t i o nw i t ho t h e rs u b s y s t e mo ft e a c h i n gm a n a g e m e n ts y s t e mi sa l s oc o n s i d e r e d t h ed e t a i l e d r e a l i z a t i o na n dt h ek e yt e c h n i q u ea r et h e ne x p l a i n e db yu s i n gt h e c o m b i n a t i o no ft e x ta n dd i a g r a m f i n a l l y , i ts u m m a r i z e st h er e s e a r c hw o r k ，a l s oa n a l y z e st h ep r e s e n t p r o b l e m sa n dt h ew o r ki nf u t u r e k e yw o r d s u n i v e r s i t yt i m e t a b l ep r o b l e m ，d y n a m i cp r o g r a m m i n g ， g e n e t i ca l g o r i t h m ，a r r a n g i n go fc u r r i c u l u ms c h e d u l e i l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特另t l d l ：i 以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名： 黄镜 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 硕士学位论文 第一章绪论 1 1 课题来源及应用背景 第一章绪论 本课题来源于“中南大学网络教学管理系统，主要是为了适应学分制教学 管理要求、改革教学管理手段、规范教学管理程序、提高管理效益而开发的基于 互联网络的信息管理系统，从而提高中南大学教学管理的效率，加快中南大学在 教学管理方面的信息化建设步伐。 中南大学9 0 年代初开始抓计算机教学管理，先后自行开发了教学评估管理 系统、学籍管理系统、教学计划和任务管理系统、排课系统等7 个单机管理系统。 在此基础上，1 9 9 8 年3 月教务处又开始着手网络管理系统的建设，经过一年多 的努力，于1 9 9 9 年8 月在教务处建立了n t 局域网连接各科室和5 栋教学楼，并 与校园网相连，设计完成了基于w e b 的教学管理系统。其中，排课系统基于大量 的经验常识，采用模拟手工排课的方式，其实现和运行，在当时及其后的几年， 大大的减轻了教务人员的工作量。 随着高校体制改革，中南工业大学、湖南医科大学、长沙铁道学院三校合并 后新成立的中南大学迫切需要建立在新体制下具有学校特色的教学管理模式，以 适应形势的发展。我们以原来开发的系统为参考模型，从2 0 0 2 年开始重新设计 教学管理网络系统软件，采用当时最新的信息技术和软件开发工具重新开发了基 于w e b 的教学管理网络系统。 这期间，高校扩招和教学改革的不断深入，在校学生、教师、教室及课程数 量上都有了大幅度增长，其它子系统也相继实现并投入运行，原有的排课系统仅 适用于原来的中南工业大学，即现在的校本部，而铁道校区和湘雅医学院依然采 用手工排课的方式；加之，课程表问题在理论研究方面也取得了一定的进展，因 此，一套结合最新理论成果，能够进行课表智能编排，适应各种要求的排课系统 变得越来越必要了 1 2 国内外研究动态 2 0 世纪5 0 年代末，国外就有人开始研究课表编排问题。1 9 6 2 年，g o t l i e b 曾提出一个课表问题的数学模型n 1 ，并使用匈牙利算法解决了三维线性运输问 题。此后，人们对课表问题的数学模型、课表问题的解及解的存在性等问题进行 了深入的探讨，但一直未能得到满意的结果。直到2 0 世纪7 0 年代中期，s e v e n 等人证明了课程表问题是n p 完全类问题乜1 ，人们才将注意力更多地转向课表编 硕士学位论文第一章绪论 排实用算法的探索与研究。之后，人们尝试着用各种方法求解此类问题，如整数 规划嘲、图着色h 1 、各种推理搜索方法嘲、启发式算法旧等等。9 0 年代初期， c o l o r n i 口3 等人首先尝试应用遗传算法( g e n e t i ca l g o r i t h m ，g a ) 来解决u t p 问题， 引进了矩阵表示方案及相应的交叉、变异算子。后来c o l o r n i 又将其成功地应用 到了意大利米兰市的一所规模较大的学校中。p a e c h t e r 阻1 等人对u t p 问题也进行 了研究，提出了时域置换法和放置一查找法，并针对较大规模的实际u t p 问题比 较了这二种算法的性能。b u r k e 阻1 对于将进化算法分阶段地用于u t p 问题做了初 步的研究，得到了一些颇有价值的成果。 我国对这一课题的研究起步比较晚，清华大学1 9 8 4 年在清华大学学报 上发表了林漳希和林尧瑞在该课题上的实验性研究成果n 们，接着当时的南京工学 院n 1 1 、大连理工学院n 2 3 等高等院校都相继开展了这方面的研究工作。 一方面，国内的排课软件系统很少，涉及到自动排课算法的系统更少，大部 分仅仅局限于辅助人工排课，并没有任何“智能 的成分。另一方面，仅有的几 套自动排课系统却由于产生了太多的“甩课( 因无法安排时间或者教室而不能 排入课表的课程) ，使得系统的实际使用非常困难，往往由于“甩课 太多，后 期人工调整的工作量并不比重新排课的工作量小很多。 即便如此，这其中一些在应用方面很友好的排课软件己经可以帮助排课人员 大大提高工作效率。例如西安交通大学自行设计开发的排课系统，以及清华大学 目前正在使用的t i s e r 系统。但是遗憾的是，所有这些系统只能在排课过程中辅 助工作人员进行排课，并没有一套完善有效的自动排课策略( 算法) ，它决定了这 些系统要么没有真正的排课功能，要么排完课后，会出现有的课程无法安排，仍 然需要工作人员进行大量的调整工作，而往往由于调整- n 课程会涉及到很多其 它的课程或者班级，很多时候这些调整工作并不比完全人工排课的工作量小。在 这种情况下，为了帮助教务人员从繁重的排课工作中解脱出来，高效实用的自动 化排课系统的研究与应用显得尤为重要。 1 3 课题的研究内容及意义 高等院校培养学生的主要途径是教学。在教学活动中，有一系列管理工作， 其中，教学计划的实施是一个重要环节。每学期管理人员都要整理教学计划，根 据教学计划下达教学任务书，然后根据教学任务书编排课程表。长期以来，人们 通过手工制表或借助于简单的软件系统来编排课程表，手工制表是最常用的办法 之一，即直接对前一年的课程表进行修改继续延用。实践表明这种办法在每年课 程设置、教师、学生及教室规模变化不大的情况下是有效的。但随着我国教育体 制改革的不断深入，特别在高校系统中连年的扩招、扩建、不断的改进专业设置、 2 硕士学位论文 第一章绪论 实行学分制的新形势下，在校学生、教师、教室及课程数量上都有大幅度增长， 学生在选择课程上有了更大的灵活性，这使得以前的课程表无法延用，而需要每 学期都重新编排课程表。教学的改革，招生人数的增加及教室设备的不足，不但 增加了工作的难度，而且要求管理工作更加快速、准确。在排课调度工作中，既 有大量繁琐的数据整理工作，更有严谨思维的脑力劳动。传统的排课方法，需要 填写大量的表格，工作非常繁重，还经常出现问题( 如教室座位不够、教师同一 时间重复安排上课等) ，尤其在个别课程需要调整时，整个课程表都要重新编排。 理论和实践都表明了只要课程表所涉及的信息量稍有增加就会导致“组合爆炸 ， 使得课程表编排方案剧增。因此，手工制表的方式，己无法处理如此巨大的信息 量，需要对课程表进行深入的研究，寻求行之有效的解决办法。为此，人们自然 希望用先进的管理手段完成这些工作。随着计算机技术的普及，办公室自动化的 先进管理手段被引进到教学调度工作中。计算机排课与人工排课有一定区别。人 的思维可以是收敛的，也可以是发散的，因而排课表时非常灵活，随机性很强， 没有严格的工作步骤，随情况而变，觉得怎么合理怎么做；但计算机就不同，它 并不具备人的大脑那样的发散思维能力，它的“大脑 里的一切信息都是由“数 据组成，每步工作是由人把人的思维抽象成计算机语言，通过程序进行控制。 因此，研究课程表问题，以科学合理的编排课程表，设计计算机自动排课系 统，能使学校教学系统运行得更加顺畅、合理，节约人力，并最大限度的利用学 校的各项资源，节省学校的各项支出，具有重要的现实意义。 同时，对最为典型的时间表问题，大学课程表问题的研究，一方面，可以通 过借鉴已有的研究成果，结合现实的应用需求，提出合适算法，从而得到一个既 充分利用现有资源，又高效实用的课程表问题解决方案，以处理当前由于高校扩 招，学分制推行而日趋复杂的排课问题；另一方面，它的研究对于各类考试的时 间安排，各类大型的会议、比赛、晚会、铁路列车时刻表的安排等n 3 1 也具有重要 的借鉴意义。 1 4 论文的内容安排和组织结构 论文共分为五章。 第一章绪论。首先介绍了本课题的课题来源、应用背景，然后介绍了国内 外研究动态，最后说明了本文的研究内容及本课题的研究意义。 第二章课程表问题。首先概述了课程表问题的基本内容，然后介绍了课程 表问题涉及的因素，各种约束条件，并给出了数学模型，最后介绍了课程表问题 的编排原则。 第三章基于动态规划思想的混合算法。本章首先介绍了最优化理论和动态 硕士学位论文第一章绪论 规划思想，并分析课程表问题的数学模型，给出了采用混合算法的原因。然后简 要介绍了遗传算法，并详细的阐述了如何基于遗传算法安排时间片，建立了遗传 算法优化的目标空间，对时间片安排进行了染色体编码，以及各个遗传算子的设 计。再次，阐述了最佳适应算法分配场地的方法，并对此阶段的优化目标及处理 过程进行了说明。最后，通过混合算法和经典遗传算法的对比实验分析，论证了 算法的可行性和运行效率。 第四章基于混合算法的排课系统。本章从工程应用的角度出发，首先对排 课系统的需求和设计原则进行了分析；然后，基于数据库原理，对排课系统的数 据库进行了设计；再次，概述了整个网络教学管理系统及排课系统所处的位置， 对排课系统与其他子系统的集成进行了说明；最后，从模块化设计和分层设计的 角度出发，给出了排课系统的详细设计与实现，并就实现过程中的一些关键技术 问题进行了研究。 第五章回顾和展望。总结本文所完成的工作，并提出了进一步研究方向和 研究问题。 4 硕士学位论文 第二章课程表问题 2 1 时间表问题概述 2 1 1 时间表问题及其分类 第二章课程表问题 所谓时间表问题( t i m e t a b l i n gp r o b l e m ) ，即是在一个固定的时间区间内( 一 般是一周) ，按照老师和学生的要求，在某些限定条件下，安排一系列课程。 t i m e t a b l i n g 问题是组合优化问题中的一个经典问题。根据各种限制条件， 大致可以将t i m e t a b li n g 问题分为以下三大类n 钔： 1 中小学课表问题( s c h o o lt i m e t a b l i n gp r o b l e m ) 所谓s c h o o lt i m e t a b l i n g 问题，是在一所学校( 一般指中小学或学院) 里， 为所有课程每周的上课时间和地点进行安排，以避免出现某位老师在同一个时间 上两个不同课程和其他一些限制条件。 2 大学课表问题( c o u r s et i m e t a b l i n gp r o b l e m ) 所谓c o u r s et i m e t a b l i n g 问题，是在一所大学里，为所有课程( 包括不同一 门课程的情形) 每周的上课时间和地点进行安排，以尽量避免出时间上两门或两 门以上课程包含相同的学生及其他一些限制条件。 3 考试时间表问题( e x a m i n a t i o nt i m e t a b l i n gp r o b l e m ) 所谓e x a m i n a t i o nt i m e t a b l i n g 问题，是在一所学校里，为考试课程安排避 免学生在同一时间考试不同的课程。 还有其他很多t i m e t a b l i n g 问题，但是基本上可以归结于或转换为上述三类 问题。本文中涉及到的是前两种问题，下面分别详细介绍。 2 1 2s c h o o l 蜀n n e t a b l i n g 问题 设有所个班级：c i , c 2 ，c 。，刀位老师：t l , t 2 ，t 。，p 个时间段1 ，2 ，p 。同时 我们可以给出非负整数矩阵天。，其中元素，表示老师f ，需要给班级q 上的所有 课程总数，我们称该矩阵为需求矩阵。 我们首先考虑最简单的情形。只要求安排所有课程，以使得没有一位老师或 者班级在同一时间需要上超过一门课程。e v e n 等人早在1 9 7 6 年就研究了这个问 题。但是完整的数学模型却由d ew e r r a n 5 1 给出： 回加d ( 删_ 1 m ；印) 5 硕士学位论文第二章课程表问题 j 口 s j x 始= 勺 ( f = 1 聊；= l 。刀) 公式( 2 1 ) ( i = 1 朋；七= 1 p ) 公式( 2 - 2 ) j ” 1 ( = l 朋；七= 1 p ) 公式( 2 3 ) l - 1 = 0 o r1 ( 江1 肌；= 1 刀；后= 1 p ) 公式( 2 4 ) 其中x u k = 1 当且仅当老师在时间尼给班级q 上课。 限制条件公式( 2 1 ) 保证每个老师预先上课的课时数，条件公式( 2 2 ) ，( 2 3 ) 分别表示每个老师或班级不在同一时间段上超过一个课程。e v e n 等人在1 9 7 6 年 研究了t t p l 问题的子问题，证明了在所有老师和所有班级上的课程数不超过p 的条件下，问题t t p l 总有解。即添加了两个限制条件： r , j p ( ，= 1 肌) i = i p ( f - 1 删) = l 公式( 2 5 ) 公式( 2 - 6 ) 求解问题t t p l ，可以将其转换为二部图的匹配问题。可以将班级和老师分 别视为二部图的顶点，班级c ，和老师f ，之间是否有边连接由决定。e v e n 等人在 1 9 7 6 年通过寻找二部图的最大匹配算法对上述问题的求解进行了研究。d ew e r r a 将其转化为图的染色问题：图的定义与上述二部图相同，给定p 种颜色( 每种颜 色对应一个时间段) ，对该二部图的边进行染色。其中x 妇= 1 当且仅当q 和f ，之 间的边的颜色是k 。求解t t p l ，只需寻找一个染色方案，使得两个相邻的边没有 相同的颜色。问题t t p l 是有多项式时间算法的。 t t p l 对课程并没有什么限制条件，一般情况下，实际中某个老师或者某个 班级会有必须在某些时间上课或者不能在某些时间上课的限制。j u n g i n g e r n 町在 1 9 8 6 年给出了这个限制条件下的模型。首先，他引进了两个0 一l 矩阵：瓦。和 g 。p ，其中k = 1 ( c 雎= 1 ) 当且仅当老i j i l i t 腑( 班级c 胁) 在时间k 有空闲。这样， t t p l 问题中的限制条件公式( 2 - 2 ) 和( 2 - 3 ) ，就变为公式( 2 - 7 ) 和( 2 - 8 ) ： 同 i 一 f i n dx 驰 ( 江1 朋；j f = 1 行；七= 1 p ) s j = r , j( f _ l 删；_ ，= 1 埘) k = l s k ( 汪1 朋；七= 1 p ) 公式( 2 7 ) 6 一 m 嘞 。同 硕士学位论文第二章课程表问题 胁 x 牡 ( = 1 埘；后= 1 妒) 公式( 2 8 ) f l l x 毋= 0 o rl ( f = 1 ，行；j f = l 。刀；七= 1 矽) 相对t t p l ，问题t t p 2 仅仅是限定条件上有些不同，但是，在复杂性上，它 们却存在本质差别。通过将这个问题规约为3 - s a t 问题，e v e n 等人在1 9 7 6 年已 经证明了t t p 2 是n p - c o m p l e t e 问题。 2 1 3c o u r s et i m e t a b l i n g 问题 c o u r s e t i m e t a b li n g 问题又可称为u n i v e r s i t yc o u r s et i m e t a b li n g 问题。 相对于s c h o o lt i m e t a b l i n g 问题，u n i v e r s i t yc o u r s et i m e t a b l i n g 问题需要 将所有课程安排在给定的教室和时间内。它们的不同主要在于，后者中的课程可 以包含有相同的学生。而前者一般都是以班级为单位，课程之间没有相同的学生。 而复杂的是，当有两门或两门以上的课程之间包含有相同的学生时，这些课在安 排过程中，就必须尽量保证它们没有冲突，否则将会有学生上课的冲突。同时一 般大学教师只教授一门或很少几门课程，而在中小学，一位老师一般需要教授很 多课程。最后，教室在大学排课问题中是个很重要的因素，而一般来说，中小学 不会考虑教室问题。 设有g 门课程k i ，k ：，k q ，对每个f ，课程k ，包含有k ，个课序号，即这门课 程开了k ，个不同时间的课。在所有课程中r 有，个课程组s ，& ，s ，其中每个 组包含相同的选课学生，即在组s ，中的课程必须安排在不同的时间。总的时间 段数为p ，设在时间段k ，最多可以安排屯门课，即在k 时间段，最多只有，。个 教室可用。 这个问题的模型如下： 同倒欺 o = l 川；七= l 印) i jl ， 豇儿= t o = 1 x ) y 业 ( 七= l p ) 瞻1 1 5 f = 1 ，；七= 却) f e s i 儿= 0 o r1 o = 1 g ；七= 1 p ) 其中y 业= 1 当且仅当课程k 。安排在时间段k 。 7 公式( 2 - 9 ) 公式( 2 1 0 ) 公式( 2 - 1 1 ) 公式( 2 - 1 2 ) 硕士学位论文 第二章课程表问题 限制条件公式( 2 - 9 ) 规定了每门课程的课时数是正确的，限制条件公式( 2 一l o ) 保证在任意时间段，上课数不多于可用时间数，限制条件公式( 2 - 1 1 ) 防止在同一 时间段出现课程安排冲突的情况。通过将问题t t p 3 规约为图的着色问题，可以 证明问题t t p 3 也是n p c o m p l e t e 问题。 2 2 课程表问题的因素及约束条件 课程表编排问题是一个解决时间和空间资源矛盾的多因素优化决策问题，即 对班级、教师、时间、课程、教室等五个相互制约的基本因素进行时空安排的问 题n 刀。这种安排问题需要满足一定的约束条件集，这些约束可以分为以下两类： “硬 约束：即可行课程表必须满足的约束条件，如果某一个约束不能满足 则不能作为可行的课程表。它包括有： ( 1 ) 一个教室不能同时安排两个以上的教师上课； ( 2 ) 一个教师不能同时上两门课； ( 3 ) 一个班级不能同时上两门课； ( 4 ) 教室必须能够容纳所有上课的学生； ( 5 ) 上课场地必须满足场地类型要求。 “软 约束：即希望所采用的课程表编排方案尽可能多的满足约束，虽然这 些约束不满足时仍是可实行的课程表。但满足“软 约束条件越多则课程表编排 越合理n 钔。例如： ( 1 ) 一门课在二周内尽可能的分散安排； ( 2 ) 每天的课时数差异不大； ( 3 ) 安排到教室中的人数应尽量和教室所能容纳的学生数吻合n 引； ( 4 ) 教师和班级接连两次上课地点尽量接近。 2 3 课程表的编排原则 课程表是学校教学工作的运行图，是提高教学管理水平、组织师生进行有序 教学的规范之一，对有效地提高教育教学质量有重要作用。如果课程表编排得不 合理、不科学，将影响课堂教学的效率和教学的整体效果。要想编排好学校的课 程表，需要综合考虑学校的教师、教室、学生、班级、时间等多方面因素，反复 调整，避免冲突。课程表的编排工作是一个系统工作，从专业设置、教学计划制 定到班级课程的设置、教师指定及各单位教室的使用权限、时间，都是环环相扣， 密切相关的。课程表编排好后的使用过程中，课程表的查询、调整也是重要的工 作。要科学、合理的编排课程表，必须明确并处理好以下几个问题： 8 硕士学位论文 第二章课程表问题 一、要认识到一张课程表往往是一种教育思想的体现，对有效地提高教育教 学质量有着重要作用。依据国家教委颁布的课程计划，编排课程表是学校教导处 的重要工作之一，是一项原则性、科学性和技术性都很强的工作。因此，应当从 教育学、自理学、生理卫生学和学校管理等方面通盘考虑，科学合理地编排课程 表。学校要按课程计划开齐课程，开足课时，不随意增减，使之符合教育教学规 律，有利于提高教学效率，有利于全面实施素质教育。 二、要根据学生大脑皮层的机能活动规律编排周课表，以利于提高教学效率。 1 时间生物学理论认为，每个人在一天中的精力和注意力如潮汐般起落。人 体内部的节律感，对课堂学习能力和作业质量有直接影响。学生在一节课、一天、 一周里各段时间的学习负担量与效果是有差异的。因此，在安排教学工作时，应 把难度大的课程安排在神经活动的兴奋高潮期。具体到编排周课表，应该注意： ( 1 ) 在一天内，上午的第一、二节是教学的最佳课时，应把难度大、费思考 的课程安排在这些时间上。而把费脑筋较少的课程安排在其他时间。 ( 2 ) 在一周中，周二、周三、周四是最佳学习日，应安排较难的课程：周一、 周五安排较容易的课程。从大脑的活动节律来看，每一节课的第6 至2 5 分钟是 最佳的教学时间。有经验的教师一般都充分利用这一最佳时间讲授完新课内容， 然后转入训练。 2 由大脑皮层活动的优势规律和脑功能的分工定位规律可知，大脑处于兴奋 状态的区域反应能力强，学习效率高。进行一种学习或工作时，只有相应的区域 处于兴奋状态( 活动区) ，其他区域则处于抑制状态( 休息区) ；随着学习内容或工 作性质的改变，活动区与休息区随之相互轮换，使大脑皮层各区域轮换休息，从 而能使大脑长时间工作。这应是我们交替编排课程的理论依据。因此，编排周课 表时应当做到： ( 1 ) 文理科要交替编排。把人文学科与自然学科课程交错安排，可减轻大脑 因相近刺激引起的疲劳，防止同类科目内容引起的干扰，以利于变换脑力活动， 提高学习效率。 ( 2 ) 脑力课( 理论课) 与体力课( 实践课) 要交替编排。把脑力消耗较多的学科 与体力消耗较多的学科轮换安排，可使学生避免过度疲劳，提高学习效果。 ( 3 ) 作业多的课程与作业少的课程交替编排。学生每天作业量的多少，周课 表起着重要的调节作用。一般不把作业量多的几门课程排在同一天，而是把它们 同作业量少的其他课程交替安排，以利于平衡学生的学习负担，避免同类学科间 的相互干扰。 ( 4 ) 每门课程一般不应连排。同一课程连排两节以上时，相同或相近的教学 内容极易引起学生大脑皮层的抑制，从而降低学习效率。 9 硕士学位论文第二章课程表问题 三、要根据教师的授课情况统筹编排周课表，使之既合理又科学。 1 “一科多班授课的教师宜在同一天里上“同头课 。在平行班级担- i - 1 课的教师，最好让其在同一天里上完同一进度的课：即使一天轮不完，也应尽量 在第二天轮完，或者前半周排一个进度，后半周排一个进度。这样编排有利于教 师的教学工作。 2 对教“多头课 的教师，最好每天只安排一种教材的课程。这样有助于教 师减轻脑力负担，提高讲课效率。 3 每个教师的教学时间应保持适当的间隔，以便教师有时间备课、辅导和批 改作业。学生也有时间复习、消化。 4 对教平行班“同头课 的教师，要尽量照顾到相互听课之便。一般把老教 师的课排在青年教师的课之前，便于“以老带新 ，互相学习，取长补短，共同 提高。 5 要尽量使每位教师每天的教学工作量大致均衡。对年老、体弱的教师的课 程，既不宜排得过于集中，又不宜太分散，以便他们有时间休息、看病或处理其 他事务。 6 根据体育场地与体育器材，电教器材，各课程的实验室( 计算机房、语音 室) 等设备情况，将相关学科科学地排入周课表。如果设备跟不上，就不能同时 安排两个或多个班上“同头课”。 7 对于有的教师确有特殊情况需要调课的，也应尽可能在较小的范围内适当 调整。要尽量控制课程表的变动次数与幅度，以保持课程表的合理性与科学性。 总之，编排周课表有很强的原则性、科学性和技术性。要使课程表编排得科 学、合理，真正成为全面贯彻教育方针的运行图，促使教学工作优化、轻负、高 效，为全面实施素质教育创造有利条件。 l o 硕士学位论文第三章基于动态规划思想的混合算法 第三章基于动态规划思想的混合算法 3 1 最优化原理和动态规划 3 1 1 多阶段决策最优化问题 在现实生活中：有一类活动过程，由于它们的特殊性，可将过程分成若干个 互相联系的阶段，每一阶段都需要作出决策，从而使整个过程达到最好的活动效 果。各个阶段的决策不能任意确定，它依赖于当前面临的状态，又影响以后的发 展。当各个阶段决策确定后，就组成一个决策序列，从而也就确定了整个过程的 一条活动路线。这种把一个问题看做是一个前后关联，具有链状结构的多阶段过 程就称为多阶段决策过程，这种问题称为多阶段决策最优化问题。 多阶段决策问题，不论其本身是否与时间有关，由于分为阶段来依次解决， 这便具有了明显的时序性。一些静态模型，只要人为地引进“时间 因素，分成 时段，就可以将其转化为一个动态的多阶段决策问题。 3 1 2 最优化原理 1 9 5 1 年美国数学家r b e l l m a n 等人，提出了解决一类多阶段问题的“最优 化原理 ( p r i n c i p l eo fo p t i m a l i t y ) 啪1 ：“一个过程的最优决策具有这样的性质： 即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的状态 作为初始状态的过程而言，必须构成最优策略 。简言之，一个最优策略的子策 略，对于它的初态和终态而言也必是最优的。 这个“最优化原理 如果用数学化一点的语言来描述的话，就是：假设为了 解决某一优化问题，需要依次作出刀个决策n ，皿，见，如若这个决策序 列是最优的，对于任何一个整数k ，l n k ，不论前面k 个决策是怎样的，以 后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策d ， 皿+ ：，d 。也是最优的。 最优化原理是动态规划的基础。任何一个问题，如果失去了这个最优化原理 的支持，就不可能用动态规划方法计算。 硕士学位论文第三章基于动态规划思想的混合算法 3 i 3 动态规划理论 动态规划是解决多阶段决策最优化问题的一种方法。动态规划把比较复杂的 问题划分为若干个阶段，通过逐段求解，最终求得全局最优解。这种方法在一些 较难解决的问题中显示出优越性，尤其是离散型问题用动态规划的方法去处理， 比用线性规划或非线性规划方法有时更有效。 动态规划是运筹学的一个分支。与其说动态规划是一种算法，不如说是一种 思维方法来得更贴切。因为动态规划没有固定的框架，即便是应用到同一道题上， 也可以建立多种形式的求解算法。许多隐式图上的算法，例如，求单源最短路径 的d i j k s t r a 算法、广度优先搜索算法，都渗透着动态规划的思想。还有许多数学 问题，表面上看起来与动态规划风马牛不相及，但是其求解思想与动态规划是完 全一致的。因此，动态规划不像深度或广度优先那样可以提供一套模式，需要的 时候，取来就可以使用，它必须对具体问题进行具体分析处理，需要丰富的想象 力去建立模型，需要创造性的思想去求解。 准确地说，动态规划不是万能的，它只适于解决一定条件的最优策略问题。 但是，这并没有削减动态规划的光辉，因为属于上面范围内的问题极多，还有许 多看似不是这个范围中的问题都可以转化成这类问题。 上面所说的“满足一定条件主要指下面两点： ( 1 ) 状态必须满足最优化原理； ( 2 ) 状态必须满足无后效性。 所谓的无后效性是指：“过去的决策只能通过当前状态影响未来的发展，当 前的状态是对以往决策的总结 。它说明动态规划适于解决当前决策和过去状态 无关的问题。 动态规划的最大优势在于它具有极高的效率，另外还有其他的优势，例如： 动态规划可以得出一系列解，算法清晰简便，程序易编、易调，等等。 ( 1 ) 优点： 1 ) 易于求得全局最优解。动态规划把复杂的问题分成若干个相互联系的阶 段，每个阶段求解的问题相对简单，而通过逐段求解这一递推过程便可得到该问 题的全局最优解； 2 ) 可以得到有价值的相关信息。 ( 2 ) 缺点： 1 ) 没有统一的标准模型可供采用，不同的实际问题，其动态规划模型也随之 不同，因而，实际问题的动态规划模型的建立往往需要丰富的想象力和灵活的技 巧： 1 2 硕士学位论文第三章基于动态规划思想的混合算法 2 ) 存在所谓的“维数障碍 ，即当问题的变量个数( 维数) 太大时，受计算机 存储器容量和计算速度的限制，常常无法解决。 3 2 混合算法设计 3 2 1 算法的总体设计思想 课程表问题，就是对课程进行时间和空间分配，以充分利用时空资源，达到 尽可能好的优化目标。以回溯算法眦1 ，贪心算法唿1 为代表的非智能算法，不管是 否划分了等价类，或者把排课问题转化为一个个的子问题例，基本上都是按照任 务，逐个的分配时间段和场地；而遗传算法秘。嚣1 ，模拟退火算法陟删，禁忌搜索 聆玎等智能算法，在产生初始解时，也有一个类似的过程，只是在得到初始解之后， 会根据从其它领域所得来的启示，调整、优化初始解，以最终得到一个全局最优 解或较优解。而从动态规划的思想出发，课程表问题就将划分为时间安排和场地 安排两个阶段，先对所有的任务，逐个分配时间，得到一个分配好时间的中间结 果，然后再对中间结果进行场地安排，最终获得一个全局最优解或较优解。这种 算法将复杂的问题分成若干个相互联系的阶段，每个阶段求解的问题相对简单， 既有利于在理论上分段进行优化，又有利于工程上分段进行扩展，也降低了实现 的复杂度。 在时间安排阶段，由于不用考虑场地的因素，从数学模型上分析，大学课程 表问题虽然得到简化，但根据2 1 节给出的时间表问题概述，此阶段仍可以归结 为一个更为复杂的s c h o o lt i m e t a b l i n g 问题。由于带某个老师或者某个班级会 有必须在某些时间上课或者不能在某些时间上课限制的s c h o o lt i m e t a b l i n g 问 题已经是一个n p c o m p l e t e 问题，因而时间安排阶段也是一个n p - c o m p l e t e 问题， 对于这类问题，只能利用智能算法求得满意解，以满足最优化原理。从已有的研 究成果来看，早在上世纪9 0 年代，c o l o r n i 等人首先尝试应用遗传算法( g e n e t i c a l g o r i t h m s ，简称g a s ) 来解决课程表问题，其后不断的研究，遗传算法在解决大 学课程表问题的理论和实践方面均取得了很大的进展，而禁忌搜索删，蚂蚁搜 索嘲1 ，人工免疫协1 等算法，基本还是停留在理论研究方面汹1 由于时间安排阶段 的求解和整个课程表问题的求解，具有一定的相似性，因此，本文采用遗传算法 来安排时间。但是，由于动态规划思想要求状态必须满足无后效性，时间安排后 所产生的中间结果，对于之后的场地安排就必须是有解的，这也就要求在进行时 间安排时消除潜在的场地安排无解冲突。特别是对于有特殊课程类型要求的任 务，必须检测在同一时间所需的教室数是否会超过该类教室的总数。 通过时间安排阶段，得到中间结果，就可以针对场地优化目标，进行场地的 1 3 硕士学位论文第三章基于动态规划思想的混合算法 分配。因为场地的优化目标主要是教室的利用率，属于单目标优化问题，有多项 式的算法，故本文采用最佳适应算法分配场地。 3 2 2 算法描述 混合算法主要是分两个阶段进行。第一阶段，以智能算法分配时间，本文采 用的是遗传算法，它包括了遗传算法求解问题的典型步骤，即包括有初始化种群， 适应度计算，选择、交叉、变异操作，冲突检测与消除等部分；第二阶段，以最 佳适应算法分配场地，它是一个简单的根据场地类型、大小等要求进行分配的过 程。此外，考虑到课程表问题需要从数据库中得到数据，并根据算法的要求做一 定的处理，而分配完场地后，需要能够显示课表和一些性能指标，因而，算法在 开始时有一个数据获取和预处理的阶段，在结束时，有一个结果的生成和显示的 部分。具体流程如图3 1 所示。 图3 - 1 混合算法流程图 1 4 硕士学位论文第三章基于动态规划思想的混合算法 3 3 基于遗传算法分配时间 3 3 1 遗传算法概述 1 遗传算法的基本概念 遗传算法是j o h n h h o l l a n d 阱1 根据生物进化的模型提出的一种优化算法。自 然选择学说是进化论的中心内容。根据进化论，生物的发展进化主要有三个原因， 即遗传、变异和选择。 遗传是指子代总是和亲代相似。遗传性是一切生物所共同的特性，它使得生 物能够把它的特性、性状传给后代。遗传是生物进化的基础。 变异是指子代和亲代有某些不相似的现象，即子代永远不会和亲代完全一 样。它是一切生物所具有的共同特征，是生物个体之间相互区别的基础。引起变 异的原因主要是生活环境的影响、器官使用的不同，以及杂交。生物的变异性为 生物的进化和发展创造了条件。 选择是指具有精选的能力，它决定生物进化的方向。在进化过程中，有的要 保留，有的要被淘汰。自然选择是指生物在自然界的生存环境中适者生存，不适 者被淘汰的过程。通过不断的自然选择，有利于生存的变异遗传下去，积累起来， 使变异越来越大，逐步产生新的物种。 生物就是在遗传、变异和选择三种因素的综合作用过程中，不断地向前发展 和进化。选择是通过遗传和变