（计算机应用技术专业论文）多校区排课系统的研究和实现.pdf

摘要 高等院校教务管理工作的内容相当复杂，排课是其中的一个重要环节。手工排课不 仅占用大量的人力、花费太多的时间，而且排出的课表往往不尽人意。因此如何利用 计算机快速、有效地编排出合理且满意度较高的课表，是一项值得研究的工作。 排课问题是一个有约束的、非线性的、多目标优化的n p 完全问题；而遗传算法借鉴 生物界自然选择和遗传机制，使用群体搜索技术，尤其适用于处理传统搜索方法难以解 决的复杂的非线性的问题。 本文对遗传算法进行了初步研究，并针对多校区排课问题，提出了基于遗传算法的 课表编排算法。该算法根据课表编排的三种约束条件：基本硬约束、硬约束和软约束。 确定了课表编排过程中的一些关键因素，并给出了排课过程中产生冲突的解决方案。 最后，通过对多校区教学现状的分析，实现了基于遗传算法的课表编排原型系统， 并将该系统应用于实际排课过程，经理论和实践表明该系统具有良好的自适应性，且效 率较高。 关键诃：遗传算法，课表。冲突，甩课，适应度 a b s t r a c t c u r r i c u l aa r r a n g e m e n ti sa ni m p o r t a n tp a r to ft h ec o m p l i c a t e dm a n a g e m e n t o ft e a c h i n ga f f a i r si nu n i v e r s i t i e s i tt a k e sm u c ht i m ea n de n e r g yt oa r r a n g e c u r r i c u l am a n u a l l yo n l yt ob eu n s a t i s f a c t o r y ，s oi ti sw o r t h w h i l et om a k ea r e s e a r c ho nh o wt o p r o d u c em o r es a t i s f a c t o r y c u r r i c u l ae f f i c i e n t l yw i t h c o m p u t e r b a s e dm e t h o d s c u r r i c u l aa r r a n g e m e n ti sa c t u a l l yam u l t i p l eo b j e c t i v ep r o b l e mo f 。n p c o m p l e t e ”w h i c hi so p t i m i z e d ，r e s t r i c t e da n dn o n l i n e a r i na d d i t i o n ，g e n e t i c a l g o r i t h m ，b a s e do nt h eb i o l o g i c a lm e c h a n i s m so fn a t u r a ls e l e c t i o na n d i n h e r i t a n c e ，m e a n sm a k i n gu s eo fg r o u ps e a r c ht e c h n o l o g y ，e s p e c i a l l yt os o l v e t h et h o s ep r o b l e m sw h i c hc a nh a r d l yb ew o r k e do u tt h r o u g ht r a d i t i o n a ls e a r c h m e t h o d s g e n e t i ca l g o r i t h m sa r es t u d i e dp r e l i m i n a r ya n dc u r r i c u l aa r r a n g e m e n t a l g o r i t h m sa b o u tm u l t i - c a m p u sa r ed e s i g n e db a s e do ng e n e t i ca l g o r i t h m s t h e s o l u t i o nt ot h ec o n f l i c t si nt h ec u r r i c u l aa r r a n g e m e n t ，a sw e l la si t sr e a s o n s 。 f i n d si t sw a yo u to fk e yf a c t o r s ，w h i c ha r ed i v i d e di n t ot h r e et y p e s - - b a s i ch a r d r e s t r a i n t s 。h a r dr e s t r a i n t sa n ds o f tr e s t r a i n t s f i n a l l y b a s e do na c c o r d i n gt ot h ea n a l y s i so fe x i s t i n gm u l t i c a m p u s t e a c h i n gc o n d i t i o n s ，p r o t o t y p ec u r r i c u l as y s t e ma r ed e s i g n e da n da p p l i e dt ot h e c u r r i c u l aa r r a n g e m e n t ，w h i c hi nt u r np r o v e st h e o r e t i c a l l ya n dp r a c t i c a l l y s e l f a d a p t a b l ea n dr u n se f f i c i e n t l y k e yw o r d s ：g e n e t i ca l g o r i t h m ；c u r r i c u l u m ；c o n f l i c t ：n e g l e c to fc l a s s e s 。 a d a p t 8 b i l i t y n 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生签名； 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电 子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文 被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理 j 第一章引言 1 1 研究背景和意义 第一章引言 高等院校教务管理工作的内容相当繁杂，而教学执行计划的实施是其中的一个重要环 节。每学期教务管理人员都要整理教学执行计划。并根据计划按人工或网络途径让教师选课， 最终在手工长时间调整的基础上生成课表。这种手工排课方式，有大量的数据( 如教师选课 信息、班级信息、教室信息、课程信息等) 需要处理；有若干冲突需要调整( 例如校区、时 间、教室等资源的冲突) 。这既是一种脑力劳动，更是一种体力劳动。如今随着高校招生规 模的不断扩大，高校硬件资源( 如教师、教室等) 相对缺乏，许多高校还有多校区办学的现 象，这些都对教务管理工作提出了更高的要求：即必须以更快、更准确的方式进行管理。排 课作为教务工作的一个重要环节，显然也需改变这种手工编排方式。手工编排方式不仅周期 长( 从上学期末开始排，到下学期初仍在调整中) 。而且教务人员辛苦排出的课表需要调整 的部分相对较多，结果无法令人满意。因此，如何利用计算机快速而有效地编排出合理且满 意度高的课表，是一项值得研究的工作。自动排课可以将教务人员从繁杂的手工排课中解放 出来，这也是高校教务管理工作自动化的重要一环。 但是，目前的课表编排系统中，还没有对多校区排课问题的研究。本文拟实现在多校区 环境下利用遗传算法的并行性实现课表的自动编排。本文在遗传算法和多目标优化理论的基 础上，提出了一个课表方案的随机生成和优化算法，能够较大程度地反映实际排课情况并实 现了多个目标的最优化。 1 2 国内外研究现状 排课问题又称时间表( t i m e t a b l e ) i 司题，是一个多因素的整体优化问题。7 0 年代中期，s e v e 等人论证了课表问题是n p 完全类问题。从那以后，有很多人对该问题进行了研究，但由 于各学校的具体情况有很大差别，无法找出通用的算法，只能在此基础上求得近似最优解。 二十世纪五十年代末、六十年代初国外就有人开始对课表问题进行了研究，1 9 6 2 年， g o t l i e b 提出了一个构造课程表的数学模型吲，接着人们对这个模型算法、解的存在性作了许 多探索【3 】1 4 j ，并提出一些新的算法模型但始终未能找出一个有效算法。在直到1 9 7 5 年的这段 时间里，人们的研究都主要从构造算法模型入手，研究其解决方法。 国内一些高等院校也进行了很多相关软件的开发研制工作。例如，西南交通大学在分析 高校课表编排所遵循的基本原则和模糊性原则的基础上，定义了课元之间关于教师的相关关 系和关于自然班的相关关系，提出以课元相关运算和课元的候选时空片计算为核心的计算机 排课算法p ；延边大学根据高校课程表的制作特点，设计了计算机自动排课的数据结构与算 法1 6 】；沈阳电力高等专科学校研制了基于c l i e n t s e r v e r 的开放式智能排课系统1 7 ；山西大学在 总结排课工作经验的基础上提出了一种解决问题的形式化描述，并实现了基于知识推理的捧 课系统哪等等。 9 0 年代后期，人们开始使用数据库技术、人工智能领域的专家系统技术作为技术支持来 解决这一问题。随后产生了不少各种类型的排课系统，解决了一些问题。但是还存在一定的 局限性，还有一些新产生的问题需要解决，例如： a ) 现有的排课系统采用传统方法进行程序设计，以程序为系统核心，捧课所用的数据 与程序结合过于紧密。系统不便于扩充和升级。 b ) 现有排课系统重点考虑了一般性捧课规则，初排后的课表往往需要针对各种特殊情 东南大学硕士学位论文 况再进行手工调整。 排课系统中并行问题的解决。 m 如何更好的提高排课的效率。 e ) 更多的特殊要求导致复杂性指数爆炸，如何能尽量多地满足特殊要求。 为了解决上述问题。人们又开始研究更有效的算法。遗传算法就是一种比较有效的算法。 它可以实现多点同时搜索，加快了排课的速度，并利用决策因子编码的方法，能模拟人类的 遗传染色体，方便地进行交叉和变异，有效地避免冲突的产生和解决已存在的冲突 遗传算法用来编排课表，也有不少先例，如： ( 1 ) c h upc 和b e a s l e yj e 在1 9 9 5 年e u r o p e a nj o u r n a lo f0 p e r a t i o n a lr e s e a r c h 上发表的文章c ag e n e t i ca l g o r i t h mf o rt h eg e n e r a l i z e da s s i g n m e n tp r o b l e m 中，提 出了对一般安排问题的处理”1 ：对一般的安排问题使用了遗传算法来进行解决，着重于遗传 算法的全局最优解搜索能力，避免了问题的局部最优解。 ( 2 ) 日本的s i g e r u 在1 9 9 9 年的e n g i n e e r i n g 上所发表的文章( i n c o r p o r a t i n g c o n s t r a i n tp r o p a g a t i o ni ng e n e t i ca l g o r i t h mf o ru n i v e r s i t yt i m e t a b l ea p p l i c a t i o n s o fa r t i f i c i a li n t e l l i g e n c e ，p l a n n i n g 中，讨论了具有控制约束的遗传算法来解决大学 课表安排问题“”：在遗传算法中加入控制约束的方法，提高了遗传算法的搜索的效率。 ( 3 ) 唐勇，唐雪飞，王玲在2 0 0 2 年的计算机应用上所发表的基于遗传算法的排课系统 中，讨论了多约束条件下用遗传算法解决高校课表编排问题“”：在多约束条件下，首先对初 始种群进行优化，改善了搜索速度，但在搜索最优解附近却不能立即得到最优解。 ( 4 ) 田岭在2 0 0 6 年的软件开发与应用上所发表的大学自动排课算法与设计中，讨 论了遗传算法、禁忌搜索算法、回溯算法相结合的方法“：利用多种算法，取其所长，所设 计的大学自动排课系统中利用启发式算法通过总结人工排课的宝贵经验，大大地加快了课表 的搜寻速度，在最短的时间内形成可行解。最后再结合禁忌搜索和回溯算法对可行解进一步 地优化形成最优解，禁忌搜索和回溯计算可以最大限度地产生较优的可行解范围，因此该 算法具有比较高的可用性和收敛性。 ( 5 ) 韩承双、张春梅、王开友在2 0 0 5 年合肥学院学报上所发表的自动排课系统迭代算法 设计与实现中，对用自适应的遗传算法求解大学课表安排问题进行探讨“”：对大学课程进 行了分类，并对不同的课程使用具有自适应能力的遗传算法进行了不同的安排 1 3 研究目标和内容 就排课问题的实质而言，它是一个有约束的( 其中包括硬约束和软约束) 、非线性的、 模糊多目标化的、难解的、时空组合的数学问题。即只能在满足预知的约束条件情况下找到 一组较优的时空组合。 根据对本校各种客观现状的分析，以及多年来参与手工排课经验，本文拟用排课系统达 到下列三个目标： 第一个目标：课表中没有硬性冲突。 课表符合基本的课程安排原则，没有无法消解的冲突。例如，一个教室不能在同一时间 安排两门不同的课程，一个班级不能在同一时间安排两门不同的课程，同一名教师在同一时 间不能上两门不同的课程等，同一名教师在较短时间单元内不能在不同校区授课( 至少相隔 一个排课元以上) 第二个目标：课表具有较高的质量。 一套高质量的课表，在时间、教室资源、课程安排等很多方面都应该做到合理地安捧， 2 - 第一章引言 并且应该具有人性化的考虑。因此，它应有能够满足以下几点要求： ( 1 ) 教师、学生在不同校区上课时要预留一定的时间用于往返不同校区。尽量同一天 内不安排不同校区的课程给教师或学生。 ( 2 ) 繁难的课程应尽量安排在上午，难度较易的课程可以安排在下午。 ( 3 ) 避免学时数较多的课程连续安排，应间隔安捧。 ( 4 ) 基础课( 如大学英语、高等数学等) 先行安排，专业课后安排，以利于基础课合 班上课，节约资源；合班上课的课程先于单班上课的课程安排。 ( 5 ) 课程设计类课程应排在下午。 ( 6 ) 连续的课程安排的教室不能间隔太远。 ( 7 ) 每个系上课的地点相对固定等。 ( 8 ) 考虑教师的某些特殊要求( 如某时间段不排课) ，课表中尽量满足要求。 第三个目标：课表中不存在或者存在非常少的“甩课”现象( 即有些课无法安排上课时 间和地点) 。 。甩课”现象的出现通常是由于课程安排中没有充分考虑后面课程的要求而导致的。一 套完整的课表，如果需要调整某门课程。往往会牵扯到非常多的课程、班级，甚至改变了大 部分己排好的课程。因此，如何将“甩课”现象减少到最低限度是排课系统要考虑的一个重 点。 本文将采用新的染色体编码方案，充分利用现有数据，将已定因素与待定因素分离，并 考虑多校区教学、合班上课、基础课与专业课穿插等情况，利用多点搜索，大幅度减少种群 规模，在较好的时空规模内完成排课任务，并期望得到教师较高的满意度。 1 4 论文组织结构 本文应用遗传算法研究并实现多校区环境下的课表编排问题。本文主要从遗传算法理 论、算法的改进、冲突消解的策略以及系统实现等几个方面进行探讨，全文共分为六章： 第一章引言：介绍国内外课表编排问题的研究现状，提出本文研究目标和内容。 第二章遗传算法分析：本章主要介绍遗传算法的概念、性质及其重要理论，并对基本 遗传算法提出改进措施，并阐述本文对遗传算法的三个基本操作所采取的方法。 第三章排课问题相关知识：首先对排课中的各种约束进行分析，然后对排课过程中的 关键因素进行分析并提出确定方案，最后论证了排课原型系统采用遗传算法的原因。 第四章应用遗传算法编排课表：首先对课表编排过程中常用的计算过程( 子算法) 进 行介绍，然后提出应用以上各子算法解决冲突的策略，最后引出本文的重点一用遗传算法编 排课表。 第五章排课原型系统的实现：以例作为编程语言，后台采用s q ls e r v e r 2 0 0 0 数据库， 实现排课系统，并给出主要界面。对排课结果进行性能分析。 第六章总结与展望：对本文不足之处进行分析，提出对该系统的完善方案。 3 东南大学硕士学位论文 第二章相关知识介绍 七十年代中期，美国s e v e o 等人在s i a m l c o ，u r e 杂志1 1 4 1 上发表了题为关于时闻 表和多物流问题的复杂性一文，首次论证了课表编排是n p 完全问题，将课表编排问题理 论化。n p 完全问题目前还没有明确的多项式算法。像排课这类整体优化问题一般依靠搜索 求解技术。搜索求解技术主要包括基于微分的搜索技术、随机搜索技术、启发式搜索技术和 枚举技术。图21 对有关搜索算法进行了大致分类。遗传算法属于进化算法，而进化算法及 进化算法中的每一个分支均属于启发式随机搜索方法。 图2 - 1 遗传算法与搜索技术的分类 与传统的启发式优化搜索算法相比，遗传算法的本质特征在于群体搜索策略和简单的遗 传算子。群体搜索使遗传算法得以突破邻域搜索的限制，可以实现整个解空间上的分布式信 息探索采集和继承：遗传算子仅仅利用适应值度量作为运算指标进行染色体的随机操作，降 低了一般启发式算法在搜索过程中对人机交互的依赖。这样就使得遗传算法获得了强大的全 局最优解搜索能力、问题域的独立性、信息处理的并行性、应用的鲁棒性、操作的简明性， 是一种具有良好普适性和可规模化的优化方法。 验证结果表明遗传算法最适合应用于组合优化问题。 遗传算法作为一种随机的优化与搜索方法。存在两个非常重要的特性：l l 习 1 智能性即遗传算法在确定了编码方案，适应值函数及遗传算子以后，算法将利用演 化过程中获得的信息自行组织搜索。适应值大的个体具有较高生存效率，它是具有“潜在学 习能力”的自适应搜索技术。 2 并行性由于遗传算法采用种群的方式组织搜索，从而可以同时搜索解空问内的多个 区域，并相互交流信息。这种搜索方式使得它虽每次执行与种群规模成比例的计算，而实质 上，据g o l d b e r gd e 推算已进行了大约o ( n ) 次有效搜索。这使得遗传算法能以较少的 计算获得较大的收益 4 第二章相关知识介绍 正是由于具备两个有效的特性，遗传算法广泛应用于求解组合优化问题。实践已经证明， 目前遗传算法对于解决组合优化中n p 完全问题是非常有效的。如：遗传算法已经在求解旅 行商问题、背包问题、装箱问题、图形划分问题等方面都得到了广泛的应用。故本文拟采用 遗传算法来对多校区排课问题进行探讨。 2 1 基本遗传算法介绍 2 1 1 遗传算法概念及特点 遗传算法是模拟生物在自然界中的遗传和进化过程而形成的一种自适应全局优化概率 搜索算法。它最早由美国密执安大学的h o l l a n d 教授提出l j m ，起源于6 0 年代对自然和人工 自适应系统的研究。 遗传算法是一类可用于复杂系统优化的计算的鲁棒搜索算法，与其他一些算法相比，它 主要有下述几个特点：i l ” 遗传算法以决策变量的编码作为运算对象。这种对决策变量的编码处理方式，使得我们 在优化计算过程中可以借鉴生物学中染色体和基因等概念，可以模仿自然界中生物的遗传和 进化等机理，也使得我们可以方便地利用遗传操作算子。 遗传算法直接以目标函数值作为搜索信息。在此我们可以直接利用个体适应度，可以把 搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。 遗传算法同时使用多个搜索点的搜索信息。遗传算法从由很多个体所组成的一个初始群 体开始晟优解的搜索过程，对这个群体进行选择、交叉、变异等运算，产生出新一代群体。 遗传算法使用概率搜索技术。遗传算法属于一种自适应概率搜索技术，其选择、交叉、 变异等运算都是以一种概率方式进行，从而增加了其搜索过程的灵活性。 2 1 2 基本遗传算法的形式化定义 基本遗传算法( s i m p l eg a ，s g a ) 可以定义为一个八元组 s g a = ( c ，e ，p o ，m ，o ，r ，v ，t ) 【1 6 】( 2 - 1 ) 其中： 阱体的编码方法；s g a 中使用固定长度二进制串的编码方法。 晰体适应度评价函数； p 0 _ q 9 始群体； m 一群体大小：即群体中所包含个体的数量，一般取为2 0 - 1 0 0 。 o 选择算子，s g 使用比例选择算子； r 交叉算子，s g a 使用单点交叉算子； v 变异算子，s g 使用基本位变异算子； t 一遗传运算终止代数，一般取为1 0 0 - 5 0 0 ； 基本遗传算法的伪代码描述： p r o c a 缸u r es g a 岫 i n i t i a l i z ep ( o ) ； t - - 0 f w h i l e ( t r p 。( 其中p 。为变异概率) ，则该位不发生变异否则，该位发生 变异。当某一位发生变异时，首先产生一个 1 n ( n 为基因长度) 之间的随机整数p ，然 后使该位处与第p 位处的基因进行交换。 例如：对于个体23 4 5 78 9l6 ，假设对第4 位( 该处的基因为5 ) 进行变异，产生一 个l 至9 之间的随机整数，若为6 ，则对该位的变异就是把该位的基因与第6 位的基因进行 交换，经变异后的个体为：234 墨7 主- 916 。显然，经变异后的个体仍然在所讨论的遗传空 间内。而“培养型变异”策略，即：当个体被变异后产生了新的个体，比较新的个体的适应 度与父个体的适应度，若新个体比父个体的适应度高，则用新个体替代原有个体。否则，再 进行一次变异，而第二次变异对对适应度再作检查。改进后的变异策略，一方面保持了变异 的随机性，另一方面含有向适应度高的方向发展的趋势 2 4 本章小结 本章主要介绍了遗传算法的相关知识。阐述了基本遗传算法的概念、特点；遗传算法的 定义；以及遗传算法应用于排课问题中所用到的一些重要理论。基本遗传算法求解组合优化 问题存在许多不足，本章提出对基本遗传算法进行改进，从初始种群到交叉、变异的过程， 以及并行性运用遗传算法几方面提出改进意见，提出了应用遗传算法实现课表编排问题的三 个基本步骤所采用的方法。 东南大学硕士学位论文 第三章排课问题分析 一般来说，作为教师接受一门课程时，会收到一张类似表3 1 的开课计划表。 表3 - 1 具体某门课程的开课计划表 开课 课程课程课程 开课起止开课校区教室教师 班级 编号 名称学时时间周数院系姓名 0 60 6 0 0 1 信息 6 0 周三1 2 0信息技江宁1 1 5 0 6陈爱萍 计信技术i - 3 节术学院授区 由表3 1 可以看出，课表所受的约束条件很多。时间、校区、教室、学生、教师本 人都会对课表提出一定的约束，课表本身也要满足一定的要求，比如基础课、合班课先 行安排；不同校区的课程尽可能不要排在同一天授课，若因资源紧张，无法安排多天授 课，必须预留一定的时间用于往返不同校区；一门课若既有理论、又有上机实践，应该 穿插安排等等。如此多的约束和要求，显然有轻重缓急之分，必须对它们作具体分析， 进行归类，哪些是必须满足的，哪些是可以商量调整的，这样在以后的编程中区别对待， 才能生成有效的课表。 3 。1 排课问题的约束分析 在进行各种约束分析之前，我们先给出一些定义： 定义1 教学任务：一门课程的一次教学工作称为一项教学任务； 定义2 教学资源：为完成教学任务所必需的教师、班级、教室、实验室、体育场以 及教学时间等称为教学资源： 定义3 冲突：两项( 或以上) 教学任务争夺某一教学资源的现象称为冲突； 定义4 冲突课程：两门( 或以上) 课程若关联着相同的教师或上课班级，则称这些课 程为冲突课程： 定义5 甩课：因资源冲突而无法安排课程的现象，称为“甩课”。 排课实际上就是将教师与学生在时问和空间上根据不同的约束条件进行排列组合， 以使教学正常进行。这里约束条件主要为避免冲突，它所包含的内容很广泛，几乎发生 在所有两个或多个排课涉及因素之间。而避免冲突也是排课问题中要解决的核心问题。 只有在满足全部约束条件和避免所有冲突的基础上。才能保证整个教学计划合理正常进 行。而对教师、教室、学生及时问等几部分资源进行最优化组合配置，才能保证充分发 挥各资源的优势和提高教学质量。本文把排课过程中的约束条件分为三类：基本硬约束、 硬约束和软约束。其中基本硬约束是指教师、学生和教室在时间片上产生冲突，它是排 课过程中最基本的约束条件。也是众多排课模型中都涉及的约束条件；硬约束是根据学 校的实际情况，排课时必须遵循的原则，否则将会导致排课结果无意义；软约束是指捧 课过程中若能满足更好，不满足也并不影响有效课表生成的约束条件，它们的违反与否 往往是与排课实际情况相关。在三类约束条件之中，前两者是衡量排课方案是否切实可 行的标准，软约束是衡量排课方案优劣的标准。排课过程中常见的基本硬约束如表3 2 所示 1 2 第三章捧课问题分析 表3 - 2 捧课过程中常见的基本硬约束 基本硬约束 1 每位教师在同一时间段内至多安排一门课程： 2 每个班级在一个时间段内至多安排一门课程； 3每个时间h 教室对至多安排一门课程。并且其 教室的类型和容量应满足待排课程需求； 4每门课程只能安排一次。不能被重复安排 常见的硬约束如表3 - 3 所示。 表3 - 3 排课过程中常见的硬约柬 硬约束 1 教室容量必须足够大。能够容纳上课的学生。 2 某些课程可以先行手工排定时间和教室。 3 教师、学生在不同校区上课时要留一定的时间 用于往返。 4 某些教师、班级或教室在某些时间段上不安排课 程。 常见的软约束如表3 - 4 所示。 表3 - 4 捧课过程中常见的软约束 软约束 l 同一课程安排在同一个教室授课。 2 学生每天的必修课课时趋于平衡。 3 学生在连续的两次授课之间更换教室所用时间 少。 4 每门课程在一周内的上课时间分布合理。 由以上分析可知，基本硬约束和硬约束必须满足，否则生成的课表没有实用价值。 而软约束则是衡量课表是否令人满意的一个尺度。 3 2 排课过程中关键因素的确定 通过以上分析可知，在排课问题中的关键因素是：时间、班级、教室、教师、课程。 下面我们逐一讨论，以确定两两冲突的解决方案。 3 2 1 时间问题 在排课问题中，时间是教学任务得以实施的载体。时间的安排不仅直接决定教师或 学生的上课时间，也是衡量教室利用率的重要参数。排课表质量的好坏很大程度上取决 于时间安排得是否合理在此我们首先讨论时间安排问题，高校排课一般使用周课表。 在周课表中，我们引入三个参数来决定一周内总的节数： 1 3 - 东南大学硕士学位论文 m ：一天内的最多节数m ( m 1 ) 。 n ：一周内的工作天数n ( 1 n 5 ) 。 p ：连排节数p ( 1 p 5 ) 。若一门课程一天内连续上三节课，则连排节数为3 表3 5 为一张周课表模板( 在此只考虑白天授课，晚问不安排课程的情况) 。 表3 5 一周五天授课制的周课表模板 时段节数周一 周二周三周四周五 l1 12 13 14 1 5 1 21 22 - 23 - 24 2 5 2 上午 3l - 32 33 34 35 3 4l - 42 43 4 4 _ 45 - 4 51 52 53 54 - 55 5 61 62 6 3 64 65 6 71 72 73 7 4 75 7 下午 81 82 83 - 84 85 8 9 1 92 93 94 95 9 1 0 1 1 02 1 03 1 04 1 05 1 0 其中，i - 1 表示周一的第一节课。i - 2 表示周一的第二节课，依此类推，5 - l o l l p 表示 周五的第十节课。 这里我们用一个3 2 位无符号整数来表示课时安排的节信息。每位的含义如图3 1 所 刁i ： 1 3 2 1 3 1 1 3 0 1 2 9 1 2 8 1 2 7 1 2 6 1 2 5 1 2 4 1 2 3 1 2 2 1 2 1 1 2 0 1 1 9 1 1 8 1 1 7 1 1 6 1 1 51 41 31 21 1l o98 765432l 卜一一卜节数一卜捧 图3 - 1 节次时间安排信息表 假如我们要表示“周二的第1 4 节有课”这样一个信息，则用3 2 位无符号整数表示 如图3 2 所示： 3 1 1 3 0 1 2 9 1 2 8 1 2 7 1 2 6 1 2 52 42 3 1 2 2 1 2 , 1 2 0 l , 9 1 , 81 7, 6 h 5 1 1 4 1 1 31 21 1l o l 9 l 8 i7 i6 l5 l4 i32 | l o0000 l 00000 l0000000000 0 0000ll11 此段第二位为i( 1 0 0 ) 2 = ( 4 ) i o 最后四位为1 ，表示1 4 节有课 表示周二有课 表示有四节课 图3 - 20 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 | 对应表示图 由于有些课程并非每周都开设。故此处又引入了一个3 2 位的无符号整数来表示周信 息，如图3 3 所示第0 位至第2 5 位表示第1 周到第2 5 周，若某位的编码为“1 ”，则表示该 周有课，若为“0 ”则表示该周没有课。第2 7 位到第3 0 位表示计划号，是指某门课程需在 一周内开课多次，对每次安排所作的顺序号标志。例如，某课程一周内需授课两次，则 有计划号0 0 1 ( 对应十进制数1 ) 和计划号0 1 0 ( 对应十进制数2 ) 。 1 4 第三章捧课问题分析 3 d 3 0 2 9 1 2 8 1 2 v2 6 1 2 5 1 2 4 1 2 3 1 2 2 1 2 1 1 2 0 1 1 9 1 1 8 1 1 7 1 1 6 1 1 5 1 1 4 1 1 3 1 1 2 1 1 l l l o 9 8 7 6 5 4 3 2l 1 ，。田 一计划号一 图3 - 3 周次安捧信息表 假如我们要表示这样的信息“信息技术课程，理论安排为5 1 8 周，每周授课一次， 实践安排为8 1 7 周，每周授课一次”，则对应信息表示为图3 4 和3 5 。 3 l3 0 2 9 i2 8 l 2 7 2 6 1 2 52 4 2 32 2 2 12 0 l l o l , 8, 7 1 , 6 1 , 51 4 1 1 3 1 2 1 l1 09 l876 l5 t ls l2 i 00001 。1 0 0 0 二二。 ( o o 0 0 1 ) 2 = ( 1 ) l o 该课程第1 次开课 圈3 45 1 8 周开设理论课 3 l3 02 92 8 2 72 62 52 42 32 22 l2 01 9 1 8 1 7 1 6 1 51 4 1 3 1 2 l l 1 09 8 7 6 5 4 3 2l 0 00 l 0o00 000000 1ll1lllll1000 0000 ( 0 0 0 1 0 ) 2 = ( 2 ) 1 0 第8 一1 7 周有课 该课程第2 敞开谭 图3 - 58 - 1 7 周开设实践课 这样，我们就可以用这两个3 2 位无符号整数来表示时间问题。本文中我们用一个二 元组来表示时间，即正= ( m ，d j ) 。其中叶为周信息的3 2 位无符号整数，d j 为表示节信 息的3 2 位无符号整数。 3 2 2 课程、教师问题 对于某班级而言，一个学期所要开设的课程是固定的，讲授这些课程的老师也相对 固定。因此，我们可把课程和教师当作同一变量考虑。某班级的课程可用相应的教师编 号描述但是这样的处理可能会出现以下的问题： ( 1 ) “多课头”问题：同一教师可以只上一门课，也可讲多门课，如果同一教师在同 一个班级教授多门课程，那么把课程和教师作同一变量考虑就会引起混乱，此问题须分 情况解决。本文采用“教师编码+ 课程编码+ 班级编码”来表示给教师所安排的具体课 程。如给陈爱萍老师( 其教师编码为0 0 1 4 3 ) 安排商学院某两个班级的信息技术课程( 该 课程编码为0 6 1 0 1 ) ，则表示为0 0 1 4 3 0 6 1 0 1 0 8 1 0 1 和0 0 1 4 3 0 6 1 0 1 0 8 1 0 2 。为了缩短染色体的 编码长度，加快其搜索及交叉速度，本文将“教师编码+ 课程编码+ 班级编码”这样的 编码串进行预处理，以教师编号附加自然数的方法来实现教师和班级课程的对应关系。 o o l 4 3 0 6 1 0 1 0 8 1 0 1 和o o l 4 3 0 6 1 0 1 0 8 1 0 2 则对应陈爱萍老师所教的第一门课和第二门课，表 示为0 0 1 4 3 1 和0 0 1 4 3 2 。 ( 2 ) “多学时”问题：对于一门课程可能一周内只授课一次，也可能授课多次，如周 学时数为4 、6 学时等，多学时的课程如何处理也是在编排课程表时必须解决的问题。对 于一门课一周内只授课一次的只对应执行计划的一条记录，一门课一周授课n 次的情况， 1 5 东南大学硕士学位论文 则由执行计划拆分出n 个排课元。含实践课的课程还需先进行拆分，然后再进行安排。这 将用4 1 2 中所述的课程拆分算法来解决。 ( 3 ) “特殊课”问题：如体育课、自习课等，这类课程在课程表中的位置也要妥善地 安排好。系统中我们采用人机交互方式上让教务人员以选择的方式添加此排课要求。 另外，有的教师可能因为某些原因需要特定的教学时段不安排课程，我们在编排课 程表时必须满足，即“特定时段”问题。 3 2 3 班级问题 学校安排各班级的理论课程相对固定在某教室上课，上机实践课在相对固定的机房 上课，英语口语课在语音室上课。因此，我们也可把班级和教室当作一个变量等同考虑， 比如0 4 计网班在白下：1 l 5 0 6 教室上课，则把0 4 计网和白下北5 0 6 教室对应起来。这样就可 避免同一时间有一个教室同时上- - f - j 以上课程的冲突了。班级和教室的相对固定，也省 去了学生课间的奔波。但是，对于机房、语音室等特定资源的使用上，可能会出现多个 班级同时使用的冲突，即“特定资源”冲突问题，在编排课程表时也必须解决此类冲突 遇到此类冲突问题，详见4 2 中的冲突转移算法。 3 2 4 适应度计算 课表问题中，对某种排课方案是否为最满意的判定很复杂，其中包含众多因素。适 应度函数可用来衡量具体某方案是否适应于应用场合。对于本系统而言，则体现为排课 方案是否合理、教师满意度的满足情况。因此，适应度函数的设计是课表问题遗传算法 设计的关键。 大多数组合优化问题中，适应度函数都是固定的。但是在课表问题中，固定的适应 度函数显然是不适用的，因为随着排课的进行，遗传环境( 课表空间) 在不断变化( 即前 面所述的组合爆炸问题) 。同样一个个体，放在不同的环境中，它的适应程度完全不同， 甚至相差很大。因此，如何设计一个具有自适应性的适应度函数显得非常重要。 捧课问题的适应度函数需考虑以下因素：校区变换满意度、日组合优度、节次优度。 下面我们分别讨论： 校区变换满意度 校区变换满意度是教师在不同校区问往返频率的一种量化表示( 例如，某教师本学 期只有- - i - j 课程，则该教师肯定只在一个校区上课，此时校区变换满意度为最高值，即 为1 0 ) ，也表示了教师对课程安排中校区问题的满意程度。具体分析如表3 - 6 所示： 表3 - 6 校区变换满意度( 以周学时数为基准) 泌 34 56 1 0l l - 1 51 6 - 2 0 次数 l1 01 01 00o 25581 01 0 3oo588 4oo255 5oo00o 表3 - 6 中，列表示某教师所教课程在该校区的周学时数，行表示这位教师去该校区 1 6 - 第三章捧谭问题分析 的次数，交叉点表示教师对系统所安排去该校区的满意程度( 最满意用1 0 表示) 。如： 某位教师在某校区的周学时数为5 节，安排其一周只去一次该校区，该教师的满意程度 对应表3 - 6 第一行第二列的值，即为1 0 ，表示该教师满意此安排方案。表3 - 6 通过本人 随机调查多位教师获得。 日组合优度 日组合优度是日组合方案优劣程度的一种量化表示( 若一周只开一次课，则不存在 日组合问题，日组合优度最高值为1 0 ) 。考虑到一门课程所开学时数最多为1 0 0 学时。 若有效开课周数约2 0 周，则周学时数为1 0 0 2 0 = 5 ，故一周内最多为此课程安排两次授 课任务。本文主要讨论每周开课两次的情况。 假如一周安捧两次授课，那么哪两天的组合比较好? 每周上两次大课( 一天只能上一 次课) ，五天中所有的两天组合数为货= 1 0 ，各课次组合优度值采用如下方法计算：已安 排课程的日次用1 表示，未安排课程的日次用0 表示，将相邻两位进行异或，异或值按 大小进行量化表示，具体如表3 7 所示： 表3 7 日组合优度表 编码组合异或结果相对优度 1 1 0 0 00 1 0 0 ( 5 ) 2 1 0 1 0 0l l l o ( 2 )8 1 0 0 1 01 0 l l ( 3 )6 1 0 0 0 11 0 0 1 ( 4 )4 0 l 1 0 01 0 1 0 ( 4 )4 0 1 0 1 01 1 1 i ( 1 )l o o 1 0 0 l l l o l ( 3 ) 6 0 0 1 l o0 1 0 l ( 4 )4 0 0 1 0 l0 1 l l ( 2 )8 0 0 0 1 l0 0 1 0 ( 5 )2 在表3 7 中，0 1 0 1 0 表示周二和周四有课程安排。相邻位异或结果为1 1 1 l ，在此十 种排列中对应的十进制值最大( 为1 5 ) ，则设置其相对优度最大，以l o 表示。 根据表3 7 ，能够对每种组合进行优度判定。例如，每周开两次的课。周二上一次、 周四上一次比较理想，间隔一天。学生能较好复习、预习而对于周四上一次、周五上 一次的组合，学生和教师都不会太满意，故组合优度较低。 节次优度 节次优度是对一节课“有多好”的量化表示，是大部分同学愿意上这节课的程度， 或者上这节课效率的高低。表3 - 8 是在一份网络调查的基础上得到的节次优度表结果， 当然这个结果含有一定的人为因素，每个人的评价可能有些差别，这也正是为什么课袭 千差万别的原因之一。在我们的排课算法中。该信息是由排课人员自己维护的。它可以 实时地体现不同阶段的学生、不同学期的要求。 1 7 一 东南大学硕士学位论文 表3 - 8 节次优度表 四五 19 59 99 7 9 4 9 2 29 59 9 9 79 49 2 39 59 99 79 49 2 4 8 58 98 78 48 2 58 5 8 98 78 48 2 66 56 9o 6 13 0 7 6 56 906 l3 0 86 56 9 o6 13 0 95 56 5o5 l 1 0 1 05 56 50 5 11 0 在表3 - 8 中，反映教师对每一小节时间安排的满意程度，本文根据金陵科技学院授 课计划，上午1 - 3 节为一个单元，4 - 5 节为一个单元，6 8 节为一个单元，9 1 0 节为一个 单元。通过对教师调查。得到表3 - 8 。 在表3 - 8 中，列表示星期几，行表示每天所开出的课程节次，则行与列交叉处表示 学生和教师对该节次的满意程度。其中最满意程度用1 0 0 表示，最不满意用0 表示。 根据表3 8 ，可以对每一节次的课程进行优度设置。例如考虑本校实际情况。周三 下午所有老师需开会，故人为将此优度设为0 ，以使该段时间不排课。若一门课程n 节 连排则其节次优度= c ，n 。 1 - 1 通过上面分析，适应度函数的计算公式为； f = k i + a + k 2 b + k 3 * c ( 式3 - 1 ) 其中，a 表示教师对不同校区往返的满意程度，b 表示日组合优度。c 表示节次的优度。 k l ，k 2 。k 3 为系数，满足k l + k 2 + k 严1 。可以根据这三个系数调整适应度中各决定因素 的权重。 3 3 排课问题采用遗传算法的理由 3 3 1 组合爆炸问题 下面的表格说明：随着论域范围的膨胀，即组合方案数的增加。规划问题将会变得 十分复杂，就算借助于现代计算机的亿次，秒的工作速度，其耗时也很惊人。 假设工作日为周一到周五，一天内有四个上课单元，上午的i - 3 节，4 - 5 节，下午的 6 - 8 节，9 - 1 0 节，则课程安排的过程类似空格填充，变为4 * 5 的表格，如表3 - 9 所示： 1 8 - 第三章捧课问题分析 表3 92 0 种捧课单元示意图 星期一星期二星期三 星期四星期五 1 - 3 节1 3 节1 - 3 节1 - 3 节 1 3 节 4 5 节4 - 5 节4 5 节4 - 5 节4 5 节 6 8 节6 s 节6 8 节6 8 节6 8 节 9 - l o 节9 1 0 节9 1 0 节9 1 0 节9 1 0 节 假设表的空格数为n ，一个开课任务( 即具体某一门课的安排计划) 的计划课次个 数为m ，则此门课程的组合方案数