（计算机应用技术专业论文）高校自动排课系统排课算法研究与应用.pdf

高校自动排课系统持课算法研究- j l , ；i 用 摘要 排课，是给学校各专业的教学计划中设置的课程安排合适的时间和地点， 也就是给每个班的课程安排时间和地点。排课工作在教学管理中很重要也很繁 琐，计算机自动排课系统，可以降低排课人员的工作量，减少排课中的人为因 素n 蝴1 。但排课问题属于n p 问题，即无法直接得到答案，只能通过猜测获取可 能结果。通常n p 问题虽无答案，却有算法，算法不能直接告诉答案，但可以用 来判断可能的结果是否j 下确可行。因此，要做好排课工作，提高排课效率，研 究排课算法是必不可少的。 本文在查阅大量相关文献的基础上，对高校的排课问题进行了分析，通过 对人工智能中的启发式搜索理论的研究，对优先权策略和分配策略加以分析和 应用，设计出排课算法启发式排课算法( h t a ) 。同时，又对h t a 算法中薄弱点( 主 要是对课程等对优先权过于敏感) 进行进一步改造，即在h t a 算法的基础上，应 用一些拟人的算法或策略，包括靠边策略、择劣策略、前景探测策略、学习策 略，减少算法中各因素对优先权的敏感，克服h t a 算法的缺陷，完善h t a 算法 内容。改造后的算法命名为e h t a 算法。通过实验，证明e h t a 算法在减少人工 干预排课次数、好时间好教室的利用、尽量满足约束条件、班级和教师的同负 荷均衡等方面，能够产生很好的效果，大大提高了排课效率。 论文还介绍了基于e h t a 算法的江苏海事职业技术学院自动排课系统构架， 并将系统应用的效果与人工排课进行对比，以科学的方式，证明e h t a 算法在提 高排课效率各方面的作用。 关键词：启发式算法，e h t a ，排课 高校自动排课系统排课算法研究j 心用 t h er e s e a r c ha n d a p p l i c a t i o no fu n i v e r s i t yc o u r s e s t i m e t a b l i n ga l g o r i t h m a b s t r a c t c o u r s e st i m e t a b l i n g , i st oa r r a n g et h ea p p r o p r i a t et i m ea n dt h ep l a c et ot h e c u r r i c u l u mi ns c h o o le a c hs p e c i a l i z e dp l a no fi n s t r u c t i o no ri sf o re a c hc l a s s s c u r r i c u l u ma r r a n g e m e n t e a c hs e m e s t e r , c o u r s e st i m e t a b l i n gw o r ki si nt h e t e a c h i n gs u p e r v i s o r yw o r kk e yp o i n ta n dt h ed i f f i c u l t y a u t o - c o u r s et i m e t a b l i n g c a nh e l pr e d u c ew o r k i n gp r e s s u r ea n dm a l l m a d ei n t e r r u p t i o n c o u r s e st i m e t a b l i n g , b e l o n g i n gt ot h en pq u e s t i o n ，i su n a b l et og i v et h ed i r e c ta n s w e r , b u tap o s s i b l e r e s u l tt h r o u g hg u e s s a l t h o u g ht h eq u e s t i o nd o e sn o th a v et h ea n s w e r ，h a st h e a l g o r i t h ma c t u a l l y ，t h ea l g o r i t h mu s u a l l yc a n n o tt e l lt h ea n s w e r , b u tc a nt e l lw h e t h e r t h es o m ep o s s i b i l i t yi st r u eo ff a l s e t h e r e f o r e ，i ti se s s e n t i a lt or e s e a r c ho f t i m e t a b l i n g i tm a yh e l pt oe n h a n c et h et i m e t a b l i n ge f f i c i e n c y ，p r o m o t et e a c h i n g m a n a g e m e n tl e v e le n h a n c e m e n t t h i sa r t i c l ei nt h ec o n s u l tm a s s i v ec o r r e l a t i o n1 i t e r a t u r ef o u n d a t i o nh a sc a r r i e do n t h ea n a l y s i st oc o u r s c st i m e t a b l i n g ，t h r o u g ht ot h ea r t i f i c i a li n t e l l i g e n c ei n s p i r a t i o n a l s e a r c ht h e o r yr e s e a r c h ，a p p l i e dt ot h ep r i o r i t ys t r a t e g ya n dt h ea s s i g n m e n ts t r a t e g y , h a sd e s i g n e dn e wa l g o r i t h mh e u r i s t i ct i m e t a b l i n ga l g o r i t h m ( h t a ) a tt h es a m e t i m e ，a l s ot oh t aa l g o r i t h mi nr e g a r d i n gc u r r i c u l u mt h ep r i o r i t yt o os e n s i t i v e s h o r t c o m i n gh a sm a d et h ei m p r o v e m e n t ，p r o p o s e dt h ee h t aa l g o r i t h m ，a p p l i e s s o m ep e r s o n i f i c a t i o n sa l g o r i t h mo rt h es t r a t e g y ，“k e e p i n gt ot h es i d e s t r a t e g y , “s e l e c t i n gt h ep o o r s t r a t e g y , “t h ep r o s p e c ts u r v e y s t r a t e g y , “s t u d y i n g s t r a t e g y ， r e d u c e si nt h ea l g o r i t h mt h ec u r r i c u l at ot h ep r i o r i t ys e n s i t i v i t y t h r o u g ht h e e x p e r i m e n t ，p r o v e dt h ee h t aa l g o r i t h mi nt h er e d u c e dm a n u a li n t e r v e n t i o nn u m b e r o ft i m e s ，t h eg o o dt i m eg o o dc l a s s r o o mu s e ，s a t i s f i e st h ec o n s t r a i n tc o n d i t i o n ，t h e c l a s sa n dg r a d ea n dt e a c h e r sd a t el o a da sf a ra sp o s s i b l eb a l a n c e da n ds oo nt h e 高校自动排课系统排课算法研究j 成用 a s p e c t s ，c a np r o d u c et h ev e r yg o o dr e s u l t s ，e n h a n c e dt h ec o u r s e st i m e t a b l i n g e f f i c i e n c yg r e a t l y t h ep a p e ra l s oi n t r o d u c e db a s e do nt h ee h t aa l g o r i t h mj i a n g s um a r i t i m e i n s t i t u t e sc o u r s e sa u t o m a t i cc o u r s et i m e t a b l i n gs y s t e mf r a m e w o r k i th a sa l s o r e c o r d e dt h i ss y s t e ma p p l i c a t i o ne f f e c tc a r r i e do nt h ep a s ta r t i f i c i a lt i m e t a b l i n gt h e c o n t r a s t ，b yt h es c i e n c ew a y ，p r o v e st h ee h t aa l g o r i t h mi nt h ee n h a n c e m e n t t i m e t a b li n ge f f i c i e n c yv a r i o u sa s p e c t sf u n c t i o n k e yw o r d s ：h e u r i s t i ct i m e t a b l i n ga l g o r i t h m ，e h t a ，c o u r s e st i m e t a b l i n g 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文 的全部内容或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密豳。 学位论文作者签名：j 杨 签字f 1 期：力谚年6 月尹同 导师签名： 弋毪墨 签字同期：。占年( ) 月c 7r 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 了锄 日期：力。艿年 6 月7 7 日 高校自动排课系统算法研究与应用 1 绪论 1 1 论文的研究目的 在我国高等教育中有两个主体：一是学生主体，二是教师主体。学生主体 是指学校教育一切为着学生，教育目的是为了将学生培养成既具备较高的专业能 力知识和技能，又有较好的道德修养，对社会有用的人才；另一个主体是教师， 因为在校培养学生的工作主要来源于教师，培养学生的大部分工作都包含在教师 对学生的日常教学工作中。高等院校的教学管理工作j 下是将两个主体有效结合 起来，保证教学工作能够顺利进行。 在高校各项教学管理工作中，排课一直是最基本的、最重要的工作，其实质 就是给教学计划中设置的课程安排合适的时问和地点，保证整个教学工作能够顺 利地进行；同时，排课工作也是一项很复杂的工作，排课是一个n p 问题，就是 始终找不到一个最优的方法能够解决的问题，因为这个问题涉及了多种因素进行 组合规划，有教师、学生的因素，也有教室的因素。尤其在目前各高校规模不断 扩大，教学资源面临紧张，教师总数不足的自订提下，排课工作问题更为凸出。 在学术界，大家对排课问题的研究由来己久，从上世纪6 0 年代到2 1 世纪的 现在，各高校都相继开发了自己的排课系统，但设计系统的算法不统一，有用模 拟人工算法、有用遗传算法，有用蚂蚁算法等掣5 圳】，每种算法各有特点，但殊 途同归，目的是设计出一个合理的排课系统，取代高校原本的人工排课的现状， 但目前还没有一个算法能够使设计出的计算机排课系统完全摆脱人工的干预，大 部分学校只是利用设计出的计算机排课系统产生出一个初始课表，然后，再由人 工调试。这种排课的过程，有时比完全人工排课更加耗时耗精力，因此，有些高 校干脆仍然继续进行完全人工排课。 本文详细研究了人工智能中的启发式搜索原理，提出了能够应用于排课问题 的启发式排课搜索算法，并运用运筹学中的分层规划，对启发式搜索算法进行进 一步的改进，提出了靠边策略、择优策略、前景探测策略和学习策略，并将此算 法应用在江苏海事职业技术学院的排课系统中，减少了人工干预排课的次数，提 高了系统的应用效果。 高校自动排课系统算法研究与应用 1 2 排课算法研究历史和发展 对排课算法的研究已经接近5 0 年之久。从二十世纪六十年代，国外就有人 开始对课程表问题进行了研究。直到1 9 7 5 年以前的一段时间里，人们主要从构 造算法模型入手，研究其解决方法，目的是找到一个解决排课问题的有效算法。 1 9 6 2 年，g o t li e b 提出了一个构造课程表的数学模型，接着人们对这个模型算法、 解的存在性等问题作了许多探索，并提出过一些新的算法模型，但始终未能找出 一个有效算法。1 9 7 5 年，e v e n 等人在美国s t a mj ，c o m p u t e r 上发表了“o nt h e c o m p l e x i t yo f t i m e t a b l ea n dm u l t i c o m m o d i t yf l o wp r o b l e m ”证明了课表问题是一 个n p 完全类问题。( n p 就是n o n d e t e r m i n i s t i cp o l y n o m i a l 的问题，也即是多项 式复杂程度的非确定性问题。这类问题的答案通常无法按部就班，直接计算出来， 只能通过问接的“猜算来得到结果。这类问题，虽无答案，却有算法，这个算 法不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案， 还是错误的，并在多项式时间内能够判断。) e v e n 等人的论述确立了课表编排问 题的学术地位，把人们对编排课表以及研究排课算法的问题提高到了理论的高 度。进入2 0 世纪9 0 年代以后，国外对课表问题的研究仍然十分活跃。比较有代 表的有印度的u a s t a p u 大学管理学院和加拿大m o n t r e a l 大学。杂志中讨论较多 的排课算法有模拟人工算法、蚂蚁算法、遗传算法等。 国内对排课算法问题也一直有研究【1 。4 1 1 3 9 】，设计出的排课系统，比如南京工 学院的u t s s ( au n i v e r s i t yt i m e t a b l es c h e d u l i n gs y s t e m ) 系统，清华大学的 t i s e r ( t i m e t a b l es c h e d u l e r ) 系统，大连理工大学的智能教学组织管理与课程调度 系统等，这些系统地运行大都是模拟人工排课过程。 模拟人工算法( s i m u l a t i v ea r t i f i c i a la l g o r i t h m ，s a a ) 是根据排课者人工排课 的思维和习惯，依次加入“班级、教师、课程”等信息和不同的限制条件，如： 班级是否合班、某教师有空的时白j 段、课程合适安排的时间段等等，制定算法， 设计排课系统。 蚂蚁算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) ，国外提及甚多，这是一种用来在 图中寻找最优路径的算法，也称图论算法。这个算法由m a c r od o r i g o 于1 9 9 2 年 在他的博士论文中引用，其灵感来源于蚂蚁寻找食物过程中发现路径行为。要让 蚂蚁找到食物，就需要让它们遍历空间上所有点；如果要找到最短路径，那么需 2 高校自动排课系统算法研究与应用 要计算所有可能的路径，并且比较大小。这个算法本身就很复杂。 遗传算法，由美国m i c h i g a n 大学教授j h o l l a n d 与1 9 8 5 年首先提出。这种 算法模拟生物发展进化的过程：遗传、变异和选择。生物学中提出每种种群由不 同基因编码的各种染色体组成。这个算法可以应用在现实中，种群即问题；每个 染色体对应问题的一个解；从初始种群开始，对适应值进行选择，然后变异成一 种新的种群；这样一代代演化下去，直到满足期待值为止。这种算法虽然能够解 决一定的问题，但染色体本身也是一个n p 问题。 目前，对排课算法问题的讨论依然很多，但还没有一个算法能够作为计算机 自动排课系统的依据，使这个系统能够真j 下摆脱人工干预，或许对排课算法的研 究可以从如何减少人工干预这一点入手，始终向完全自动排课方向迈进，排课系 统的设计才能越来越如人意。 1 3 论文的主要研究内容和结构 1 3 1 论文的主要内容 本文通过查找各种文献资料，对南京部分高等院校排课问题进行调研，以江 苏海事职业技术学院为例，分析了当前高校的现状，对排课问题进行深入研究和 分析；在算法方面，运用人工智能学中介绍的启发式搜索原理( h e u r i s t i ct h e o r y ) 和运筹学中的分层规划( h i e r a r c h i c a lp l a n n i n g ) 思想，研究出启发式排课算法 ( h e u r i s t i ct i m e t a b l i n ga l g o r i t h m ，h t a ) 并应用在实际排课系统设计中，以减少 计算机自动排课中的人工干预，提高排课效率。 启发式原理就是依据中间信息，有步骤、有顺序地搜索目标。分层规划思 想是对决策目标下的各种不确定性因素进行分类、分层，形成多准则，对各准则 下的混合最优解划分权重系数，进行再次规划，形成一个最优化的决策方案。 本文是在启发式原理应用在排课问题上，形成启发式排课算法( h t a ) 的同时， 对启发式排课算法再次进行改进，运用分层规划思想，提出靠边策略、前景策略 和学习策略，改进后的启发式排课算法( e h t a ) 应用在实际排课设计中，通过对比 实验，提高了排课效果。 高校自动排课系统算法研究与应用 1 3 2 论文的结构 本论文的结构包括5 章内容： 1 ) 绪论 阐述本论文研究排课算法的目的。排课就是将教学计划中所有设置的课程能 够合理地安排，保证学校的教学工作能够顺利进行。排课工作是一项组合规划工 作，是高等院校教学管理中的一项非常重要的工作。面对目前教学资源紧张的局 面，排课工作无法完全由计算机自动完成，仍然需要负责排课的教务员投入大量 的时| 日】和精力。在这样的情况下，本论文研究排课算法，虽无法达到计算机自动 排课目标，但可以在很大程度上减少排课工作的人工干预，达到提高排课效率， 促进教学管理改革进步的目的。 2 ) 高校排课系统的需求分析 详细分析高校排课系统在排课原则和功能、性能、运行环境及安全性方面需 要达到的要求。 3 ) 启发式搜索理论 对人工智能领域的启发式搜索理论进行分析，提出它可应用在排课问题的方 面。 4 ) 基于启发式搜索理论的排课算法 根据启发式搜索理论的启迪，建立启发式排课算法( h t a 算法) ；而后，又依 据运筹学中的分层规划思想，提出靠边策略、前景探测策略和学习策略，改进 h t a 算法，形成e h t a 算法。这一章对这h t a 和e h t a 算法进行了详细描述和 分析，也是论文的重点。 5 ) 基于j 2 e e 和m v c 的排课系统构架设计 介绍江苏海事职业技术学院自动排课系统的框架，将面向对象技术应用于高 校排课系统，突出软件设计流程，并对应用e h t a 算法的排课系统的效率进行 了评估。 4 高校自动排课系统算法研究与应用 2 高校自动排课系统的需求分析 应用自动排课系统是所有高校排课工作的趋势，它可以降低排课人员的工作 量，减少人为干预排课次数，提高排课工作的效率。合理地实施教学计划中的 课程安排，保证教学工作顺利进行，高校自动排课系统的设计也必须建立在院校 排课工作的基本原则之上，同时在功能、性能、运行环境、安全性等方面，满足 各高校的要求。 2 1 高校排课工作的基本原则 随着高等院校办学规模的不断扩大，办学层次的不断提高，高等院校排课管 理工作也显得越来越重要，学校要做好这项工作，关键要遵循科学的排课原则， 采取有效的管理办法，实现课表编排现代化。渺3 订 1 ) 有利于充分利用教学设备和条件的原则 设计排课系统的算法具有一定的复杂性，设计教师、教室班级、课程和时间 等信息对象，算法目标是为满足需求( 如班级、课程等) 进行合理资源( 如教室、 教师和时间等) 分配，核心问题是避免资源冲突。在学校的教学工作中，有些课 程需要共同使用学校的场地、设备、器材、实验室等。如公共体育课需要用到操 场、游泳池、体育器材等，专业课程需要用到实验室、阶梯教室。在排课中必须 根据实际情况给予科学的安排、周密的考虑，以提高设备的使用效率。规模较大 的高校，教师一般采用“穿插使用”的办法，这些学校许多课程如公共课是跨系、 跨专业进行的，一个班级没有固定的上课教室，一门课程或许是几个班级的学生 坐在一起，而另- - i - 课程却在其它教室早上，像这样不时地变换上课地点的课程， 排课是要避免“撞车”现象的发生。特别是近年来，随着各校招生规模的不断扩 大，学校教学设备和条件普遍吃紧的情况下，更要合理安排和充分利用好现有教 学条件和设备，避免“撞车”现象或闲置。 2 ) 科学的制定教学计划，保证课程顺利开设原则 教学计划是学校教育、教学的指导性文件，是编排课程表的唯一依据。它根 据学生的身心发展规律，按照教育原则和培养目标，根据学科的内在必然联系， 合理的、科学的、有序的编订了每学期要开设的课程。课掌教学是按固定的课程 5 高校自动排课系统算法研究与应用 表进行的，课程表是学校全面贯彻党的教育方针，培养具有一定规格的大学生的 具体反映。它应该按照教育学和教育心理学的原理科学的将教学计划固定下来， 并通过教学活动不断的得到实施和完成的。而且根据高职学校的教学特点，教学 计划要求满足以下几点： 既要有便于执行的相对的稳定性，又要顺应职业社会需求的发展变化甚 至要有超前意识； 既要明确理论教学的任务，又要规范技能训练的标准： 对于“复合型 专业，还要注意跨学科的各门课程之间的联系与衔接， 甚至先后顺序、深浅程度、课时比例都要反复向有关专家征询。在编排课程 表时，一定要严格按照教学计划制定，保证课程顺利丌设，不要随意改变或 停开某一课程。 3 ) 体现“以人为本”的原则 全校教师在教学活动中，应团结、协作和谦让，体现“以人为本”的原则， 尽可能的考虑学生的发展和教师本人的利益，创造一个和谐的工作环境。年轻教 师刚参加工作，只是具备一定的理论基础，在实践技能方面还有待于向有经验教 师学习请教。因此每天的课时，年轻力壮的教师可以集中安排，便于集中时间去 学习，年老体弱的教师分散编排，以利于劳逸结合，不影响身体和教学效果。新 老教师同时上课时，尽量把老教师安排在前面，新教师安排在后面，“以老带新”， 让新教师先听后讲有学习的机会。 要想提高学校的教学水平，必须先提高教师素质。近2 年，各高校，特别是 高职院校将“双师型”作为严格要求教师的标准，鼓励教师从事项目科研工作， 因此，在编排课程表时要充分考虑任课教师的教学与科研活动。要适当集中安排 任课教师的课时，让他们有一个相对集中的时间去学习、搞科研，也给教师有充 分休息和备课时间。但不要在一天或连续二天内安排很多课时，或者- - f 课程连 续安排，以防过度疲劳，影响教学效果和教师健康。 对身体健康状况不良的教师和家庭需要照顾的教师，安排课程时在合理的前 提下应尽可能的给予照顾。同一学科中新老教师的课应不在同一节课中安排，如 果教师外出参加活动，便于安排代课。 6 高校白动排课系统算法研究与应用 4 ) 有利于提高学生学习效率的原则 学生是学校教育的主体，教学的目的就是要让受教育者接受知识，理解和掌 握知识，发展学生的认识能力和体力，培养学生的世界观和道德品质。高等院校 不同于中、小学，除了要侧重专业学术的研究以外，也需并举学生实践技能的培 养和提高。面对不同性质的课程，如何根据学生的心理特点和身心健康发展规律 合理编排课程，提高学习效益，是值得研究的课题。为了提高学习效率，考虑需 要处理好以下几个方面： 一般编排两节连掌课，但至多不要超过三节。安排两节连堂课，一方面有利 于大学教学内容的合理安排，让一些理论知识和观点得到连贯的较全面的阐述； 另一方面，连续三节课以上的课程，时间较长，学生容易产生疲劳，容易产生“倒 摄抑制”和较大的“负迁移”效应，影响学习效果。 学习难度较大或主干课程应当安排在学生和教师精力最旺盛的时间。一般 讲，每天上午是最佳黄金时间，学生和教师精力充沛，大脑清醒，不易产生“前 摄抑制”现象，适宜安排难度较大或主干课程。每天下午和晚上学生容易疲劳， 精力易分散，适宜安排各种活动课程和易理解的课程，如实验、体育、选修课等 课程。 不同性质不同层次的课程适当搭配、交错编排。高校需要开设多类课程，这 些课程性质不同，层次也不尽相同，在排课时要尽量做到“适当搭配、交错编排”， 记忆课程与逻辑演绎的课程可以交叉混排。 实验课与理论课的编排，最好先上理论课，后紧接着实验课，时间隔的不要 太长。高职学校注重技能实践教育，但电不能因此排课将体育、实践技术等体能、 实践课程安排在同一天，以免学生过于疲劳。 2 2 自动排课系统的需求分析 2 2 1 数据需求 1 ) 静态数据需求 高校排课系统中涉及到的因素有4 个：教师、班级、课程、教室。排课就是 对这4 个因素进行组合规划，所以，这4 个因素的信息要完整和相对稳定。这些 7 高校自动排课系统算法研究与应用 因素的信息至少包含： 教师( 教师编号，教师姓名，所在系部编号，所教课程编号) 学生( 班级编号，所在系部编号、所在专业编号、班级人数) 课程( 课程编号，课程名称，所属系部编号，所属专业编号，课程性质，课时) 教室( 教室编号，教室类型，教室座位数，是否安排) 以上四个因素在组合规划时，不能发生冲突，即同一名教师在同一时间只能 安排同- f 7 课、同一个班级只能在同一时间一问教室安排一门课、同一问教室在 同一时间不能被两门课或两个班级占掘。满足了以上的要求，系统在排课逻辑上 的基本要求就达到了。 2 ) 动态数据要求 排课系统在对排课四要素：教师、班级、课程、教室进行组合规划时，还受 其他变数的影响，比如：合班班级编号，合班班级需要安排阶梯教室( 大教室) ： 需要安排在上午的课程，专业核心课程需安排在上午进行，以保证专业课程的教 学效果；特殊的原因，个别教师不能安排的时间段等等。这些数据在不同的学期 不同，数据通常在一些限制条件中，这些限制条件影响着排课的结果。 2 2 2 功能需求 高校排课系统在功能上需要实现以下6 个功能： 信息设置功能 信息查看功能 排课处理功能 课表管理功能 系统管理功能 系统帮助功能 1 ) 信息设置功能 该功能是完成系部信息、专业信息、班级信息、教师信息、教室信息、课程 信息等基本信息的输入。 信息设置还包括导入教学计划和限制排课条件。限制排课条件主要有： 高校臼动排课系统算法研究与应用 课程在本学期实施的周数( 第x 周一第x 周) 课程每周可以安排的时问 课程是否合班 课程需要的教室 信息设置由教务处或系部教务管理员操作。 2 ) 信息查看功能 此功能主要是对输入信息的查询，这项功能的权限也是有教务管理员所有。 3 ) 排课处理功能 自动排课是依据以上的输入信息，主要是课程、班级、教师和教室的信息， 在依据排课算法进行自动排课。 4 ) 课表管理功能 该功能包含对课表的查询、智能调课、课表的存档和删除、单课表和总课表 的导出和打印。排除的课表可以再依据一定的条件进行部分调整；对课表进行存 档或删除，是教务管理的要求，是教学资料归档的一个部分，归档使课表以文件 的形式进行保留；查询功能根据不同的权限适用于教务管理员、教师和学生。教 务管理员可查询任何教师的单课表、班级的单课表、全院( 系) 和所有班级的课 表；也可以查询各教室( 包含实验室、体育课场地等) 的安排情况和冗余情况， 以便于临时调课。 课表管理功能可将课表导入到e x c e l 表格中，不仅教务员，任何教室和学生 可根据自己的权限，从网上搜索到所需的单课表或总课表并进行打印。 5 ) 系统管理 这个功能实现资料备份、资料恢复、设管理员权限等。 ( 1 ) 数据备份和数据恢复 用户可以通过选择保存的路径把数据库保存在硬盘或其它盘中。如果数据 产生丢失或被破坏，用户可以通过选择路径将数据恢复。 9 高校自动排课系统算法研究与应埘 ( 2 ) 管理员设置 管理员设置仅限管理员，其中可以添加、修改、删除操作员工，设置他们的 权限、级别及密码。 ( 3 ) 系统整理信息 这个功能可以显示距离管理员整理系统的时间。 6 ) 系统帮助功能 系统帮助功能主要是提供帮助信息和“关于”信息。“帮助”信息可以详 细显示系统使用帮助。“关于”信息则提供系统的一些说明，如丌发时间等。 附：图2 - 1 自动排课系统功能结构图 图2 1 自动排课系统功能结构图 2 2 3 性能需求 1 ) 数据精确度 要按照严格的数据格式输入，否则系统不给予响应进行处理。查询时要保证 l o 高校自动排课系统算法研究与应用 查全率，所有相应域包含查询关键字的记录都应能查到。因为通常有文件的记录 会很多，可以采用了两种方法进行查询：直接查询和模糊查询。 2 ) 时间特性 一般操作的响应时间应在1 。2 秒内，对软磁盘和打印机的操作也应在可接受 的时间内完成。 3 ) 适应性 满足中高等院校使用的需求( 记录量控制在1 0 0 0 项内) ；对运行环境要求不 应存在困难。 2 2 4 运行环境和安全性需求 1 ) 运行环境需求 在运行界面上，排课系统应采用菜单界面驱动方式，能够给操作用户带来了 极大的便利，对用户友好。对鼠标和键盘单独支持。 在硬件接口上，排课系统不需要特定的硬件或硬件接口进行支撑，4 8 6 以上 p c 机均可运行此软件。 在软件接口上，排课系统只要能运行于w i n d o w s 9 5 及更高版本具有w i n 3 2 a p i 的操作系统之上即可。 j 下常使用中不应出错，若运行时遇到不可恢复的系统错误，也必须保证数据 库完好无损。具备异常处理机制，调试或运行时遇到的问题应通过异常处理代码 给予提示或解决。 2 ) 安全性需求 系统的重要数据都有密码保护，具有一定的安全性；用户输错数据都有提示 信息，具有较好的容错性能：用户基本上在提示信息下输数据，系统具有很好的 封闭性。 3 启发式搜索理论分析 搜索理论是人工智能中的基本理论，内容是说明基于一个起始点，如何搜索 高校自动排课系统算法研究与应用 到目标点。而排课问题正是可以运用这个理论中搜索的方法，将课程作为一个起 始点，运用合适的方法，最终找到合适的时间和地点( 教室) 。 3 1 传统的搜索理论 3 1 1 传统搜索理论的分析 以往我们的排课系统都是依据搜索理论。传统的搜索理论是立足一个起点， 根据一定的原则有步骤、有顺序地搜索到目标。搜索的方法或策略有很多，比 如宽度优先搜索、深度优先搜索等，它们均属于盲目搜索，或者称为无信息搜索， 就是它只是按照规定的路线或者规定的策略和方法进行搜索，在搜索过程中产 生了许多中间信息，这些中间信息对搜索动作并没有帮助，或者说，搜索理论并 不利用这些中间信息来改进搜索策略，以便尽早地达到目标。由于传统的搜索 方式总是按照既定的原则，不能很好地利用已产生的信息对搜索过程进行适当的 调整，使得这种搜索方法在复杂问题的求解上，搜索效率低，耗费过多的计算机 的空间与时间。另外，在搜索的过程中，可能存在多种可以扩展的节点，并且这 些节点没有先后和好坏次序，使得最终搜索方法带有很大的随意性，即在盲目中 寻找一个解或中间解，这样，即便在既定搜索方法的指引下能够达到一个目标， 也很难获得一个最优的解。所以，传统的搜素理论只适合应用在简单的求解上， 对于较为复杂的问题，往往需要更为有效的方法和策略加以解决。 3 1 2 传统搜索理论的应用 传统搜索理论首先要求取定问题的初始状态，目标状态、动作( 操作) ，然 后再进行搜索，采用状态空间搜索。 状态空间是指问题从初始状态到目标状态的一个搜索空问，在这个搜索空问 罩，包含了很多的状态和操作。状态用以描述问题求解过程中不同时刻的状况： 操作是产生状态的动力，每一次进行操作都是问题由一种状态进入到另一种状 态。 当到达目标状态时，由初始状态到目标状态所有的操作序列就是问题的一 个解。 状态空间搜索的基本思想是：首先把问题的初始状态( 即初始节点) 作为当 前状态，选择适用的“动作”对其进行操作，生成一组子状态( 或称后继状态、 后继节点、子节点) ，然后检查目标状态是否在其中出现。若出现，则搜索成功， 1 2 高校臼动排课系统算法研究与应用 找到了一个状态作为当前状态。重复上述过程，直到目标状态出现或不再有可供 操作的状念及“动作”时为止。 传统的搜索理论，思路比较直接，简单，容易理解：但是由于从初始阶段产 生了后继阶段开始，产生的中间状态就可能不只一个，那么它在继续搜索目标的 过程中，操作是随机的，这就可能它在进行若干搜索后，始终达不到目标状态； 或者即便最终搜索到目标状态，也不能控制住操作序列是一个最优的序列，也就 是说整个搜索过程，操作很被动。 3 2 启发式的搜索理论 3 2 1 启发式搜索理论的分析 启发式搜索( h e u r i s t i cs e a r c h ) 或称有信息搜索( i n f o r m e ds e a r c h ) ，它也 是根据一定的规则，逐步求得中间解，最终搜索到目标。但是它与传统的搜索理 论不同之处在于在搜索的过程中，对于搜索产生的中间解，不断进行分析和优化， 或者加入了与问题相关的启发式信息，用以调整搜索策略，指导搜索沿着最有希 望的方向前进，加速问题的求解过程并找到最优解。很明显，启发式的搜索方 法由于一般的搜索方法，它使问题的求解更加趋于理性，更加高效。 3 2 2 启发式搜索的评价函数 启发式的搜索关键在于如何寻找到有利的信息并对搜索方法进行优化? 在 搜索过程中，产生的子状态很多，可能可扩张的节点也很多，如何确立下一步的 节点，不同的方法产生不同的搜索结果。如果在确定节点时能充分利用与问题求 解本身以及求解过程中反映出的特性信息，估计出节点的重要性，就能在搜索时 选择重要性较高的节点，以利于求得最优解。像这样可用于指导搜索过程，且与 具体问题求解有关的特性信息称为启发性信息。用于估价节点重要性的函数称为 评价函数，其一般形式为：f ( x ) = g ( x ) + h ( x ) ，其中g ( x ) 为从初始节点x o 到节点x 已经实际付出的代价；h ( x ) 是从节点x 到目标节点x n 的最优路径的估 计代价，它体现了问题的启发性信息，其形式要根据问题的特性确定。例如，它 可以是节点x 到目标节点的距离，也可以是节点x 处于最优路径上的概率等。h ( x ) 称为启发函数。 高校自动排课系统算法研究与应用 对于问题p ，一种常用的得到启发式函数h ( s ) 的方法是通过将问题p 放松成 个相对简单的问题或者简单问题的集合p ，使得其最佳解决方案可以被更有效 的求得。而对于解决p ，的最优估价可以被看作是用来解决问题p 的启发函数。 4 基于启发式搜索理论的排课算法e h t a 的设计 启发式搜索理论运用在排课问题上，产生的算法要受到很多的很多限制条件 1 4 高校自动排课系统算法研究与应用 的影响，需要将这个理论和排课的基本原则结合起来，满足高校对自动排课系统 地要求，排课算法才能真j 下起到好的作用。1 2 4 - 2 7 1 4 1 已有的排课算法分析 高校排课问题是典型的n p 一难问题。即在p ! = n p 的假设下，找不到一个 算法能保证在多项式时间内得到最优解；同时，排课问题目标状态模糊，排课的 过程中，约束条件很多，约束条件有静态的条件，即排课一开始就要考虑和遵循 的条件；还有动态条件，即排课的过程中甚至是排课之后产生的约束。 因此， 为了实际应用的需要，对于这类问题，往往利用问题的一些启发式知识来探求能 快速求其近似最优解的算法，即启发式搜索算法。目前求解排课问题的启发式搜 索算法大致可分为两大类：_ 类是构造型搜索算法，另一类是改进型搜索算法。 构造型算法一般是按照某种次序逐步安排每门课程进而得到一张合法课表，常使 用的是一种称之为直接启发式搜索算法。它们一般是模拟人工排课的经验或实现 人工排课的设想，基本策略都是根据排课的约束条件随机地选择班级或者课程进 行排课；而困难在于随机的选择造成班级或者课程间的不合理性以及无法满足动 态约束条件。使用这种算法搜索到的结果很难是一张趋于合理的课表， 或者这 种算法只给出一张基本的课表，后期仍然要花费大量的人力和时间进行调整、 补充和完善。其实这种搜索算法只是起到一个辅助排课的效果。 另一种改进型算法是在( 合法) 课表上进行改进使得课表更加合理，如蚂蚁算 法、遗传算法等现代优化算法。这些算法都需要在预先产生的若干个初始合法课 表上进行工作。相比之下，直接启发式搜索算法，简单、直接、快速，其启发式 知识往往是针对具体问题的特点提出的，虽然通用性较差，但是如果启发式知识 得当，则往往能快速地得到较好的解，而且，这种搜索算法能够满足各高校不同 的需求；而现代优化算法尽管具有通用性和理论上的全局最优性，但是往往收敛 慢，不能满足一些院校具体的要求。因此目前的排课系统中大都是采用直接启发 式搜索算法。 本文考虑到启发式搜索算法的优势，吸收了构造型和改进型这两类算法的特 点，在启发式搜索算法上进行了进一步的改进，提出了启发式排课算法( h t a ) 。 t f f a 包含两个部分组成，即包含了两个算法：e x p l o r i n g 算法从效果上相当于是 一个局部搜索算法，它在构造课表的过程中同时也对课表进行了局部优化，所得 1 5 高校自动排课系统算法研究与应用 课表的质量明显高于直接启发式算法所得的课表；l e a r n i n g 算法是在前者的基 础上引入了拟人策略，使排课系统更加合理，进一步提高了课表的质量。 4 2 排课问题的分析和数学描述 由于高校排课问题的目标模糊性和约束条件的多样性和不确定性，本文首先 要将约束条件分层次及量化，并且不断地优化目标，使得目标更趋于合理。目 前在高职院校中，课程的安排有如下基本考虑和限定：一门课程可能包含了若干 班级，由于教学资源不足，往往会合班上课( 包括理论课和实验课) ，如何选择 合适的教室? 课程可根据周课时多次授课，但安排的时间对于不同性质的课程 ( 专业必修课、专业选修课、任意选修课等) 来说，时问是不同的。考虑到上午 的时间，可能学生精力比较充沛，注意力容易集中，因此，专业必修课和专业选 修课通常优先安排上午的时间即l 、2 、3 、4 节后，如果安排不过来，再考虑下 午5 、6 节课；而任意选修课通常安排在下午7 、8 节课或者晚上的时间。另外， 为了让学生更好地掌握课程的内容，在完成一次课后( 高职院校通常是2 节课) ， 下次同- - i - j 课程不会安排在同一天。教室是不固定的，但是有些教室的多媒体没 有落实，使得像计算机类的许多课程在上课时不易展丌，对于这样的情形，适当 考虑固定教室，也方便了教师的教学工作。 为了方便考虑和描述问题，本文将每次授课所包含的几个要素组成的4 元组 ( 课程，班级列表，教师，周学时) 称作课元。将一周内可供安排的每节上课时 间称作时间片，由时间片和课室构成的序偶( 时f b j 片，教室) 称作时空片。将教室 相同，时问在同一天上午、下午或晚上且连续的若干个时空片的集合称作时空片 簇。因此排课的任务即是为给定的每个课元合理地分配时空片簇。 不少高校从 上课的效果出发，不允许- - i 课程，尤其是专业课程一天之中不能连续讲授，比 如这门课程安排了1 2 节的时间，同一天在任何时间原则上不能再次安排，即不 能在时空片簇中连续安排。我们对影响排课的约束条件进行分类和量化，将约 束条件分成三个层次： 1 ) 硬约束条件 这个约束条件是保证排课系统能够安排出一张基本的课表。且这个条件是在 1 6 高校自动排课系统算法研究与应用 现有的教学资源大于学生规模的前提下进行。主要包括：( i ) 按课元及周学时分 配时空，做到一天之内部安排两次或两次v a _ i ：的课时；( i i ) 每个时空片最多只 能分配给一个课元；( i i i ) 每个班级在同一个时间片内最多只能有- - f - i 课程；( i v ) 每个教师在同一个时间片内最多只能有- - i - j 课；( v ) 其它必须满足的条件( 比如， 由于某种原因要求某些特定时间不能排课等) 。 2 ) 优化约束条件 旨在使