（计算机软件与理论专业论文）基于优先级的自动排课系统的研究与设计.pdf

硕士学位论文 m a s t e r st h e s i s r e s e a r c ha n d d e s i g no ns y s t e m o f a u t o m a t i cc o u r s ea r r a n g e m e n t b a s e do np r i o r i t y i i v at h e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t f o rt h em s d e g r e ei nc o m p u t e rs c i e n c e b y z h o uz h i y u n p o s t g r a d u a t ep r o g r a m d e p a r t m e n to fc o m p u t e rs c i e n c e c e n t r a lc h i n an o r m a lu n i v e r s i t y s u p e r v i s o r ：w a n gj i n g h u a a c a d e m i ct i t l e ：a s s o c i a t ep r o f e s s o r s i g n a t u r e a m a y 2 0 1 1 肌74 舢6脚8舢98 舢哪丫 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：司织玉 日期：如，年月日 学位论文版权使用授权书 学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借阅； 学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手 段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密，在年解密后适用本授权书。 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名：j 司乏& 云 导师签名： 日期：舢i f 年月f 日 日期：山t 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程 ，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布，并可按“章程 中的 规定 日 硕士学位论文 m a s t e r st h e s i s 中文摘要 排课问题即课表编排问题是教学管理中备受关注的信息处理问题之一，是多 目标的决策优化问题。因排课设计因素繁多，数据量极大，约束条件复杂，传统的 手动排课方法在速度和结果的科学性及合理性上无法保证。随着计算机广泛应用到 信息处理问题上以及高校课程体系的日趋丰富和完善，用计算机来辅助排课成为一 种趋势。目前，部分高校运用自主研发的排课系统进行排课管理，但由于课表编排 问题是一个n p 完全问题，各高校的实际情况和需求有异，因此开发出完全符合要 求并且通用的排课系统是非常困难的。 本文首先讨论了华中师范大学的排课现状，分析了排课的基本问题和目前常见 的排课算法的优缺点，针对我校手工排课效率低下而排课结果又不够理想等问题， 基于本校以教学班为单位授课的特点，研究和设计了适合我校选课和排课实际情况 的自动排课算法。算法首先设置了教学班的优先级，并按教学班优先顺序进行排课， 以求减少和避免教学班间的冲突；在安排每一个教学班时采用分治算法的思想，先 安排上课时间后安排上课地点，降低了算法的复杂性；算法结合贪婪算法的思想， 对不同周学时的课程进行了时间模式优先级的设置，在安排时间时总是在教学班的 可用时间单元中选择优先级最高的时间模式进行匹配，以求取得最佳的上课效果； 考虑合理利用教学资源，算法预先对教室进行了等价类的划分，在安排教室时，按 教室类型选择容量最接近的可用教室；算法还结合了回溯法的思想来处理自动排课 过程中的部分死锁问题。本文随后详细介绍了系统的设计和实现环节，对系统架构、 各个功能模块、系统的基本框架和数据库的设计等进行了详细的描述，并且主要针 对自动排课的时间死锁问题设计了交互性良好的手动排课和调课界面，解决了以往 单凭经验手动排课和处理冲突的复杂问题，极大地减轻了教务部门的排课工作量。 目前该排课系统已基本实现其功能，并处于试用阶段，试用结果表明，该系统具有 较好的排课结果和响应时间。 关键词：排课算法；优先级；教学班；死锁；排课系统 m a s t e r s t h e 溺 a b s t r a c t c o u r s es c h e d u l i n g ，n a m e l y ，a r a n g e m e n to fc u r r i c u l u ms c h e d u l ec u r r e n t l yw h i c hi so n e o ft h ep r o b l e m so fi n f o r m a t i o np r o c e s s i n gr e c e i v e sm u c hc o n c e r n i ti sam u l t i - o b j e c t i v e d e c i s i o no p t i m i z a t i o np r o b l e m ，b e c a u s em a n yf a c t o r s ，ag r e a ta m o u n to fd a t aa n dm a n y c o n p l e xc o n s t r a n t sa r ei n v o l v e di nc o u r s es c h e d u l i n g ，b yu s i n gt h et r a d i t i o n a lm a n u a l a r r a n g e m e n to fc u r r i c u l u ms c h e d u l e ，t h es p e e d ，r a t i o n a l i t ya n ds c i e n t i f i c i t yo f i t sr e s u l t c a nn o tb eg u a r a n t e e d w r i t l lc o m p u t e r s e x t e n s i v ea p p l i c a t i o no ni n f o r m a t i o np r o c e s s i n g p r o b l e m sa n dt h ee n r i c h m e n ta n dc o m p l e m e n to fo u rc o l l e g ec u r r i c u l u ms y s t e m ，u s e i n g c o m p u t e rt oa s s i s t 、杭mc o u r s ea r r a n g e m e n tb e c o m e sat r e n d c u r r e n t l y , t h ee x i s t i n g u n i v e r s i t yc o u r s es c h e d u l i n gs y s t e m sp l a yt h e i rr o l ei naf e wu n i v e r s i t i e s ，b u td u et o a r a n g e m e n to fc u r r i c u l u ms c h e d u l ei sa n p p r o b l e ma n db e c a u s eo fd i f f e r e n tu n i v e r s i t i e s 嘶t l ld i f f e r e n tp r a c t i c a ls i t u a t i o na n dn e e d s ，d e v e l o p i n gau n i v e r s a ls y s t e mm e e t i n g 谢t l l d i f f e r e n tn e e d si sah a r dw o r k t h e p a p e r f i r s tc o n s i d e r s t e a c h i n g r e a l i t y o fc e n t r a lc h i n an o r m a l u n i v e r s i t y ( c c n u ) ，t h e n i t a n a l y z e sf u n d a m e n t a lp r o b l e m s o fc o u r s e s c h e d u l i n g ， d i s c u s s e sm e r i t sa n df a u l t so ft h ep r e s e n tc o m m o nc o u r s es c h e d u l i n ga l g o r i t h m ，b a s e do n t h ef a c to ft a k i n ge x t e r n a lt e a c h i n gs i t ea sau n i tt of i te l e c t i v es y s t e mo ft h eu n i v e r s i t y , i t r e s e a r c h e sa n dd e s i g n san e wc o u r s es c h e d u l i n ga l g o r i t h m t h ea l g o r i t h mf i r s ts e t s p r i o r i t i e so fe x t e r n a lt e a c h i n gs i t e s ，t h e na r r a n g e st h e mb yp r i o r i t i e sf o rr e d u c i n ga n d a v o i d i n gs i t e sc o n f l i c t s w h e na r r a n g i n gas i t e ，w eu s ec i r c u l a t i o na l g o r i t h mt h i n k i n g st o r e a c hg o a lo fr e d u c i n gt h ec o m p l e x i t yo ft h ep r o b l e m , f i r s ta r r a n g ec l a s st i m e ，t h e n a r r a n g ec l a s s r o o m t l i sa l g o r i t h mi sc o m b i n e d 、航mg r e e d ya l g o r i t h mb ys e t t i n gd i f f e r e n t t i m e dm o d e sp r i o r i t e s ，w h i l ea r a n g i n gc l a s st i m e ，a l w a y sm a t c h i n gw i t l lt h eh i g h e s t p r i o r i t ym o d ef i r s ti no r d e rt or e c e i v et h eb e s tt e a c h i n ge f f e c t b yc o n s i d e r i n gu s i n g t e a c h i n gr e s o u r s e sr e a s o n a b l y , i td e v i d e sc l a s s r o o m st os e v e r a lp a r t s ，c h o o s e sp r o x i m a l c a p a c i t yw h e na r r a n g e sc l a s s r o o m t 1 1 ea l g o r i t h mi sa l s oc o m b i n e dw i t l lb a c k t r a c k i n g m e t h o dt od e a lw i mp a r to fd e a d l o c kp r o b l e m s w h e r e a f t e r , t h ep a p e ri n t r o d u c e sc o u r s e s c h e d u l i n gs y s t e md e s i g na n di m p l e m e n t a t i o n f a c e d 、) l ，i t ht i m ed e a d l o c kp r o b l e m ，i t g i v e ss e v e r a lk i n d o ff e a s i b l es o l u t i o n s a n dd e s i g n sa ni n t e r a c t i v em a n u a lc o u r s e s c h e d u l i n gs u r f a c ew h i c hr e d u c e sw o r k l o a do fa c a d e m i cs t a f fa n dd e a l s 、析t l ld i f f i c u l t i e s m u c hm o r ee f f i c i e n tt h a nm a n u a ls c h e d u l i n gw h i c hu s ee x p e r i e n c eo n l y c u r r e n t l y , t h e c o u r s es c h e d u l i n gs y s t e mi sb a s i c a l l yc o m p l e t e da n di sn o wi no p e r a t i n gc y c l e b y t e s t i n gt h es y s t e m ，i ts h o w st h a tt h es y s t e mf u n c t i o n sw e l la n di s 晰t i lg o o dr e s p o n s e t i m e k e y w o r d ：c o u r s es c h e d u l i n ga l g o r i t h m ；p r i o r i t y ；e x t e r n a lt e a c h i n gs i t e s ； d e a d l o c k ；c o u r s es c h e d u l i n gs y s t e m 目录 中文摘要i a b s t r a c t 第一章绪论 1 1 1 研究背景及意义。l 1 2 排课问题研究现状1 1 3 我校的排课现状3 1 4 本文主要工作4 第二章排课问题分析及常用算法 2 1 排课的基本问题6 2 1 1 排课因素6 2 1 2 排课约束条件7 2 2 排课系统功能需求“8 2 3 各种常见的排课算法9 第三章基于优先级的自动排课算法研究 1 2 3 1 排课预处理1 2 3 1 1 分批排课：1 2 3 1 2 教学班优先级的确定1 3 3 1 3 时间预处理1 4 3 1 4 教室预处理l8 3 2 自动排课18 3 2 1 对公共选修课的编排1 9 3 2 2 对非公共选修课的编排：1 9 3 2 3 自动排课算法步骤及流程图2 2 硕士学位论文 m a s t e r st h e s i $ 3 3 手动排课2 5 第四章排课系统设计及实现2 6 4 1 系统架构：2 6 4 2 系统功能模块2 6 4 2 数据库设计2 8 4 2 1 概念结构设计2 9 4 2 2 逻辑结构设计3 0 4 2 3 物理结构设计3l 4 4 排课系统的实现。3 5 4 4 1 系统平台3 5 4 4 2 系统开发相关技术3 5 4 4 3 系统的基本框架3 6 4 4 4 相关代码描述3 7 4 4 5 排课系统主要功能界面4 1 第五章总结。 。4 6 5 1 全文工作总结4 6 5 2 工作展望4 7 参考文献。 校期间发表的论文、科研成果等 致谢 4 8 。5 0 硕士学位论文 m a s t e r st h e s i s 第一章绪论 1 1 研究背景及意义 开课和排课是高校每学期开学例行的事务，其中排课是教务管理工作中最重要 同时也是最复杂的工作之一。排课的实质是为开课课程安排合适的上课时间和地 点，使教学能有计划和有秩序的展开。排课涉及资源非常多，如上课校区、教学楼、 课程、教师、学生、专业、班级等，排课问题的约束条件非常复杂，在课表编排过 程中排课各约束条件和资源在不断发生变化，因此实现课表编排的自动化是很有难 度的。目前，大部分高校的排课任务仍然通过有经验的教务人员进行手动排课完成， 因此通常会消耗大量的人力和时间。因排课考虑的因素繁多，排课过程中如何满足 各种排课要求和避免这些资源间的冲突是一个难题，由于人脑处理数据的能力非常 有限，手工排课的结果通常不够理想。近年来因高校课程设置在不断丰富，以及高 校扩招带来学生人数的增加，都对排课提出了更高的要求，因此设计和实现自动化 排课系统替代效率低下的手动排课方法成为当前研究的热点。 排课系统不仅要实现排课的自动化功能，还应具备人性化、高效性等特点，根 据对排课现状的分析和了解，高校排课诸多问题解决的关键不仅仅是对算法的优 化，重点是设计一个合理的算法，算法的合理性体现在，如：同一门课程时间间隔 设置的合理性、课程需尽量安排在上课效果最佳的时间等。人性化合理安排课程能 够提高教学质量和节省教育资源，算法的合理性也是实现排课系统结果的正确性和 运行稳定性的前提。 二十世纪9 0 年代开始，国内众多高校、软件公司和个人针对排课问题进行了 大量研究和开发工作，为高校教学排课提供了丰富的理论基础并研发出许多高校排 课系统，然而，目前自动化排课算法的研究还未成熟，排课系统都不具备通用性。 基于此，本课题通过对我校排课现状进行调研，提出一种适合于我校选课制和排课 要求的自动排课算法，并基于该算法设计出一个信息集成化水平高的自动排课系 统，以减轻教务部门的排课工作量，提高我校教学质量。 1 2 排课问题研究现状 排课问题的研究在国外开始较早，早在二十世纪6 0 年代，c c g o t l i e b 就提出 了课表编排问题的数学模型，并引起了国外对该问题的广泛关注和重视。但是由 于实践的困难，人们对该问题是否存在解产生了疑问。 7 0 年代，s e v e n 和c o o p e r 等人在论文【2 】【3 】中证明了该问题是一个n p 完全问 的认识并正式确立了课表编排问题的学术地位。 国外对排课问题的研究从二十世纪5 0 年代发展至今，产生了很多种求解方法 和策略。整体规划方法将该问题转化成求解多个1 o 变量的解【4 】【5 1 ，此方法的计算量 是相当大的，虽然分支限界法可以解决1 0 线性优化问题，但该方法适合于小规模 的课表编排求解。j u n g i n g e r 将排课问题表示为三维运输求解的问题1 6 1 ，t r i p a t h y 等 人主张线性编程算法，将排课看作整数线性求解并表示课表为一个数学模型r 7 1 ，另 外，还有一些学者尝试性地从图论【8 1 1 9 1 2 6 1 1 2 7 1 方面来求解排课问题，但是因图着色也 是n p 难的问题，而且只有小规模课表编排问题才能够归结为二部图匹配，由于二 部图匹配模型与排课差距较大，图着色方法对于高校排课的实际意义不大。进入9 0 年代后，比较有代表性的排课问题研究如加拿大m o n t r e a l 大学的j f e r l a n d 和c h a r l e s f l e u t e n t 【l 们，j f e r l a n d 将排课分解成分组问题和时间表问题两个相关联的子问题并 使用惩罚因子构造启发函数，其研发的s a p h i r 系统包括数据处理、交互优化和自 动优化等若干模块，解决矛盾采用多重数组的方法，这与西方教学管理体制是分不 开的。 因为排课问题的约束条件复杂，使用数学模型表示排课问题常常导致问题规模 的激增。国外众多研究表明，紧紧依靠数学编程解决排课问题是不大可行的，使用 运筹学中的“分层规划 的策略对排课规模展开分解可能成为一种有效的解决方法 脚j o 国内对排课问题的研究始于二十世纪8 0 年代，排课系统按照教育资源共享的 程度，分为单机版和网络版。单机版的排课系统仅在一台机器上运行，无法与其他 资源进行共享，即数据是独享的，所有用到的资源必须在主机上单独拥有，输入资 料和发布结果都由手工操作，单机版的安全性很容易被满足。网络版的排课系统伴 随着互联网技术的崛起而产生的，系统建立在校园网平台基础上，以基于w e b 的教 务管理理念为指导，资源间能够实现交互和共享，信息可实现分散处理和集中优化， 不同院系间实现数据交换功能，因此提高了教务管理效率，与此同时也对网络安全 性提出了更高的要求。 国内自最开始的手工排课到目前较热门的基于遗传算法的研究，比较有代表性 的排课系统有：清华大学研发的t i s e r ( t i m e t a b l e s c h e d u l e r ) u 1 1 ，1 9 8 4 年南京工学院 王能斌等人自主研发的u t s s ( u 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 ，大学课表安 排系统) 【1 2 1 ，2 0 0 9 年大连理工大学路芳瑞等人研发的智能化教学管理和课程调度系 统【1 3 】等。以上排课系统由于自身的独特性( 与本校的教学体制相关联) ，因而不易 2 硕士学位论炙 m a s t e r st h e s i s 被广泛使用。 1 3 我校的排课现状 华中师范大学是中国教育部直属重点综合性师范大学，国家“2 l l 工程 重点 建设的大学，学校共有2 4 个院系，包括6 0 个本科专业。学校对本科生开设四种类 型课程，包括公共必修课程、公共选修课程、专业必修课程、专业选修课程。学校 实行学分制教学管理制度，学分制是以学分计算和选课制度作为基础的教学管理制 度，选课制度淡化了传统的行政班级的概念，各年级学生在本学期结束之前根据学 分制要求，通过校园网在线选择下学期课程，使得学生上课的课程具有弹性化，体 现了以人为本、共性中满足个性需求的特点。 行政班级即传统的普通意义上的班级，通过自主选课，我们引入了教学班的概 念。教学班可能包含一个或多个院系的行政班级的全部学生，也可能包含一个或多 个院系行政班级中的部分学生，一门课程可以有一个或多个教学班。学生自主选课 的结果是：同专业学生上同门课所在的教学班可能不同、同行政班级学生上同门课 程所在的教学班也可能不同的情况。 随着教学体制的深化改革，我校教务管理网络平台虽然初步实现自动化管理， 但很多方面管理方式仍然采用手工管理。由于一些基础数据不够完善，部分管理功 能暂未实现，如全校的排课任务至今仍然交由教务处排课人员和各个院系的教学秘 书通过手动排课方式共同完成。 下面介绍我校排课前准备工作和排课流程如下： 1 院系教学秘书呈报院系开课计划：教学秘书根据院系培养方案向教务处呈报 下学期开课计划。对于公共必修课和公共选修课，开课计划内容包括( 开课 院系，课程名称，学分，周学时，总学时，授课教师，教师授课要求) ；对 于院系专业课，开课计划内容包括( 开课院系，开课专业，课程名称，授课 年级，行政班级名，人数，授课老师单位，授课教师，课程考核方式等) 。 2 教务处审核开课计划：教务人员根据院系开课标准和教育资源情况对院系教 学秘书呈报的开课计划进行审核。 3 教务处安排公选课的上课时间、教室及授课老师：一经确定，在该时间不能 安排其他任何类别课程。 4 教务处安排公共必修课的授课教师：对每门公共必修课的授课对象按院系、 专业进行划分，为每一批授课对象指定几名具备该课程授课能力的老师，供 学生选择偏向的授课教师。 3 硕士学位论文 m a s t e r st h e s i s 5 学生网上选课：学生根据总学分要求和各类别课程学分要求上网选课，选择 必修课的授课教师和自己感兴趣的选修课程及授课教师。 6 教务处对选课结果进行审核：取消选课人数未达到课程最少计划人数的课 程：对学生不合理的选课，开启二次选课并审核。 7 排课人员进行手动排课：对每一门公共课，根据选课总人数以及授课对象所 属院系和专业，进行分批处理( 同专业学生尽量集中在一个教学班里) 产生 若干个教学班。对教学班排课时，原则上规定公共必修课同专业的不同教学 班的上课时问尽量相同。 8 课表下放和实施：教务处将公共课的排课结果以班级课表、教师课表的形式 向院系发放。 9 院系教学秘书排专业课：专业课只能安排在公共课的剩余时间和地点上。考 虑到相对固定学生上课地点的问题，学校将每栋教学楼的教室划分到各院 系，+ 每个院系拥有若干指定的教室，专业课将被安排在指定的这些教室中。 1 0 实施排课。 我校手动排课暴露出了很多问题，如：手动排课可能使学生的多门课程集中在 同一天上或者教师一天上多节课程的不合理情况的发生；排课过程中先排的课程占 用了后排课程的可用时间造成死锁，需要排课人员凭借经验反复修改和调整相关课 程的上课时间和地点，这种工作是繁琐和耗时的；当专业课的授课老师或者授课对 象来自外系时，教学秘书需要与外系教学秘书或者教师进行沟通协调，统一公共的 空闲时间，而当因素改变时，课表还可能进行二次调整等。 1 4 本文主要工作 本文首先分析和讨论了我校的排课流程和排课基本问题，针对我校选课现状以 及手工排课的弊病，设计了基于优先级的自动排课算法，算法结合了贪心算法、分 治算法、回溯算法的思想，力求在解决排课要素间多种冲突问题的基础上取得最好 的排课效果。而后详细描述了系统架构和系统各个模块的功能，并对数据库进行了 详细设计，最后基于该算法设计并实现了适合我校的自动排课系统。 本文对于排课问题的研究主要集中在： l 、如何尽量避免冲突：本研究在对我校实际排课情况进行调研后，通过对现 有的各种排课算法和排课基本问题的进一步研究，提出了一种适合我校实际情况的 自动排课算法，算法通过设置教学班优先级最大限度的避免排课冲突的产生： 2 、如何在避免冲突的前提下取得最好的排课效果：好的排课要求排课结果要 4 硕士学位论文 m a s t e r st h e s i s 具有科学性和合理性，主要是指课程安排的平衡性和离散化问题，本算法通过优先 匹配优先级高的时间模式，获得最佳的上课时间，并使得一周上多次课的课程有一 定的时间间隔，取得最好的上课效果； 3 、如何在取得最好上课效果的前提下节约教学资源：通过划分教室等价类和 按容量从d , n 大排序的方法选择教室容量接近教学班人数的教室，节约了教室资 源： 4 、对于自动排课发生死锁的教学班，如何进行自动解锁和手动调课：对于时 间死锁和教室死锁，本文给出了不同的解决办法，在时间死锁问题上算法首先结合 回溯法的思想处理死锁，在处理失败以后，通过排课人员在排课界面上进行试调课 和排课操作解决，因此，该问题对系统的手动排课界面提出了比较高的要求； 5 、对系统架构、各个功能模块进行了描述，并对数据库进行详细设计，最后 给出了系统运行结果界面。 本研究基本上实现了我校排课的自动化运行和管理，进一步完善了我校教务系 统的功能，极大地减轻了教务部门的排课工作量。 5 硕士学位论文 m a s t e r st h e s i s 第二章排课问题分析及常用算法 2 1 排课的基本问题 2 1 1 排课因素 本课题参考了大量文献，将排课定义如下：“排课的本质是根据排课约束条件， 将课程、学生、教师在合适的时间段分配到合适教室的最优化组合的问题 。排课 在定义上考虑的要素很多，既要避免时间冲突和地点冲突，确保教学的正常运行， 还要讲求合理性。在进行排课数据管理之前先要对排课参数进行初始化设置，设置 的合理性会直接影响到排课的效果。这些参数主要包括：常规参数、排课时间、教 室时间、教师时间、部门时间等。 从排课引入冲突的角度，将排课牵涉到的因素归纳如下： 1 、时间：时间属性包括学年、学期、周次、节次。根据我校的实际情况，工 作日从周一到周五共五天，每天有早中晚三个时段。上午和下午时段分为四个小节， 晚上有两个小节，共十小节课，每节4 5 分钟。两小节课组成一大节，按大节来上 课，1 2 节、3 4 节、5 6 节、7 8 节、9 1 0 节分别为一大节课，因此每周五天共涉及有 2 5 次课分别用t l ，t 2 ，t 2 5 表示。考虑每周的课表一般是相同的，除了有的课 程分单双周上课因此需要单双周课表。 2 、课程：每个课程都有自己的编号、课程名称、学分、总学时、周学时、指 定教室类型、课程性质、考核方式、起始周次、结束周次等。每门课程可以指定教 师，也可以规定禁止安排上课时间。 3 、院系：属性包括院系编号、院系名称、包含的专业名称和专业编号等。 4 、行政班级：即入学分班的班级，属性包括行政班级编号、所属专业编号、 名称、人数。 5 、教学班：选课结果产生课程的若干教学班，属性包括教学班编号、课程编 号、授课教师、授课对象专业、人数等。 6 、学生组群：属性包括所属专业编号、所属专业名称、人数等。 7 、教师：属性包括教师编号、教师姓名、所属院系编号等。每个教师同一时 间只能给一个教学班授课，同时教师可以有授课偏好、禁用的授课时间和期望的授 课时间。 8 、校区：属性包括校区名称和编号，当教师在多个校区授课时需要考虑教师 从一个校区奔赴到另一个校区的时间，这是我们所考虑的排课时间因素之一。 6 硕士学位论文 m a s t e r + st h e s i s 9 、教学区域：一个校区有多栋教学楼，距离靠近的教学楼可以合称一个教学 区域，也可以单独的一栋教学楼叫做一个教学区域。排课是尽量避免学生跨区上课。 1 0 、教室：属性包括教室名称、编号、教室类型( 如普通教室、多媒体教室、 机房) 等。每个教室属于一个教学区域。在同一时间每个教室只能安排某一教学班 的授课。同时为了考虑节约教学资源，根据教学班人数来安排合适容量的教室。 2 1 2 排课约束条件 排课要根据约束条件来进行，设置约束条件的目的是为了避免冲突保证教学正 常运行，冲突几乎发生在任何两个排课因素之间，如两个教学班安排在了同一时间 或同一个教室上课，同一教师在同一时间安排了多门课程等。 怎样对课程、时间、教师、学生及教室资源进行优化组合避免冲突保证充分发 挥各资源优势是设计排课算法的重点。表2 1 给出了课表编排的三大类约束条件。 表2 - 1 课表编排的三大类约束条件 约束类型约束内容 基本硬约束指时间和空间上不可能发生的事情，是课表编排中最基本的约束 条件，包括： 基 ( 1 ) 在同时间同教学班的学生不能安排两门不同的课程。 本 硬 ( 2 ) 同教师在同时间不能安排两门或多门授课任务。 约 ( 3 ) 同教室在同时间不能安排两门相同的课程。 束 ( 4 ) 同时间课程总数不能大于所能提供教室的总数。 ( 5 ) 教室容量要能容纳课堂学生人数。 硬约束是根据学校的实际情况在课表编排过程中必须遵循的规则，包括： ( 1 ) 某些性质的课程需要特定类型的教室，如，英语听力课要安排在多媒体 硬 语音教室，计算机实验课要安排在机房等。 约 ( 2 ) 某些时间不排课，如某年级政治学习时间。 束 ( 3 ) 某些教师在某些时间不能安排授课。 ( 4 ) 某些教室在某些时间不能安排课程。 ( 5 ) 在两个校区上课时虚要留下足够的时间赶赴等。 软约束是指排课过程中满足更佳但不满足又无妨的约束条件，如： ( 1 ) 对同一授课对象、同一教师尽量选择固定的几个教室授课 软 ( 2 ) 一周上多次的课程安排上课要有一定时间间隔 约 束 ( 3 ) 教师对授课时间和地点偏好的考虑 ( 4 ) 学生一天安排课程节数适量，并且课表中上课时间均匀分布 ( 5 ) 不同类别的课程在一天内交叉安排。 7 硕士学位论文 m a s t e r st h e s i s 基本硬约束和硬约束是评价排课算法是否可行的准则，软约束是评价排课算法 优劣的准则。一个好的排课算法，应该在满足硬约束的前提下尽量满足软约束条件， 以求取得最好的排课效果。好的课表还应尽量满足教师和学生的基本要求，使得大 多数的课程能够让教师和学生满意，并且达到不错的教学效果。本文在设计排课算 法时，遵从本校以教学班授课的情况，以教学班为基本单位排课。 2 2 排课系统功能需求 在了解了排课基本问题后，根据我校的课程设置特点和教学管理的要求，通过 仔细研究和分析，总结出我校排课系统的主要功能如下： 1 、系统初始化及基本信息维护 系统初始化包括设定学年学期、校区、教学区域、学期起始周次等，基本信息 维护包括院系基本信息、专业基本信息、课程基本信息、教师基本信息、班级基本 信息、学生基本信息、教学班基本信息及教室基本信息等的自动导入和手动录入及 维护。 2 、对有特殊要求的课程手动预排课 院系教学秘书根据所在院系学生和教师实际情况上报教学计划，教学计划反应 教学任务的基本情况以及一些约束，如课程对教室类型的特殊要求、对上课时间和 地点的特殊要求等。系统先对有特殊要求的课程进行手动预先排课。 3 、自动排课 系统能够在获取数据库的基本信息以及排课各项约束条件以后进行自动排课， 最终生成各种课表，并且对排课过程中抛出的异常给予响应和提示。 4 、手动排课 系统不仅要能够对特殊要求的课程进行手动排课，还要求对自动排课失败的课 程能够进行手动排课，对安排成功的课程要进行手动调课。 5 、上网查询、打印输出功能 提供w e b 查询功能，排课结束后教师能够上网查询和打印教师课程表，学生能 够查询和打印个人课表，教务人员可以查询各种类型课表，还可以进行简单的调课 和数据修改。 6 、用户管理 系统对不同级别的用户设置不同的访问权限，不同用户通过身份认证后才能进 入系统进行权限范围内的操作。系统管理员可以设置和修改不同用户的访问口令和 密码。 8 硕士学位论文 m a s t e r st h e s i s 7 、数据备份与恢复 实现系统数据库的安全性管理，包括将数据库中的重要数据进行备份、从备份 文件中恢复错误删除掉的数据等等。 2 3 各种常见的排课算法 常见的排课算法主要有以下几类： 1 启发式算法 启发式算法( h e u r i s t i ca l g o r i t h m ) 是人们从面对现实规律或具体问题积累 的经验和规则中启发出来的方法。常用的启发式算法有：二十世纪5 0 年代提出的 贪心算法和局部搜索算法、8 0 年代h o l l a n d 提出了遗传算法、8 0 年代后期的模拟 退火算法、禁忌搜索算法、蚁群算法等。 ( 1 ) 局部搜索算法是在搜索过程中始终选择当前点的邻居中与离目标最近者的 方向搜索。对特定的问题一般能快速找到满意的解，但是容易陷入局部最优。 ( 2 ) 遗传算法是美国人h o l l a n d 借鉴生物进化论中的自然选择定律和自然遗传 机制提出的一种具有全局最优性、智能性( 自组织、自适应、自学习) 和并行性的 高效率搜索算法，该算法由于其优点常被用于排课系统中。于国莉在文献 1 5 3 中运 用遗传算法求解排课问题，在种群产生时采用冲突检测，随机生成课表来补充冲突 个体，从而大大提高了搜索效率。姚建波在文献 1 6 中对传统遗传算法进行改进， 使用遗传算法完成系统建模和编码设计，并对选择交换变异操作进行了详细分析和 研究。尽管遗传算法在很多应用中获得了成功，但是由于它缺乏完整的收敛性理论 以及时间复杂性问题等缺点，使得遗传算法的推广有待进一步做出努力，而且其求 解问题的规模普遍偏小，很难开展运用到课表编排系统中。如何确定各个参数，控 制迭代过程和次数问题也是我们要考虑的问题。 ( 3 ) 模拟退火算法是1 9 8 3 年由s k i r k p a t r c k 等人提出的又一种启发式搜索算 法，其原理类似于金属退火原理，算法能够用较短时间在较大解空间内寻求最优解， 目前被有效运用于课表编排这类组合优化问题中。它能够为不同用户提供自由设定 修改目标权值等的功能，具有较好地交互性的特征，但用模拟退火算法解决排课问 题的研究现在只是处于模型试验阶段侧。黄干平等人在文献 1 7 中使用该算法对交 互性课表的实现进行了深入的研究。 ( 4 ) 禁忌搜索算法简称t s 算法，是一种全局迭代寻优算法，是对局部邻域搜索 算法的扩展。为避免迂回搜索和陷入局部最优，算法引入禁忌策略和局部局部邻域 搜索机制，并通过特赦准则释放被禁忌的优良状态从而最终实现全局最优。算法常 9 硕士学位论文 m a s t e r st h e s i s 被用于组合规划问题中，彭超等人在文献 1 8 中提出了基于t s 算法求解排课问题 的解决方案并在一定程度上满足了排课需求。与遗传算法和模拟退火算法相比，t s 算法的特点是可以接受劣解并且得到全局最优解的概率更大等等。 ( 5 ) 蚁群算法是九十年代初d b t a n i e z z o 受蚁群觅食行为的启发提出的一种仿生 优化算法。用该算法解决课表编排问题首先要抽象蚂蚁个体、寻找路径和信息素的 挥发，应用个体信息启发策略来解决问题。蚁群算法的产生为解决排课问题提供了 一种全新的思路，目前该算法的研究相比其他比较成熟的排课算法才刚刚处于初始 阶段，而且排课效率比较低，是排课问题研究的一个全新方向。赵惠怡在文献 1 9 中抽象排课问题为二部图模型，并应用该算法对二部图展开最大匹配，以寻找比较 好的排课方法。 2 基于专家系统算法 专家系统( e x p e r ts y s t e m ) 是一个具有智能化特点的计算机程序，它是人工 智能的一个重要研究领域。通过把专家的经验、知识写到程序中，运用人工智能中 的知识表示和推理技术，达到使用计算机来模拟专家完成专业领域中专门的、困难 的任务的目的。专家系统的研究重点包括知识的挖掘和抽取、知识的表示以及知识 推理技术等。它由知识库、总体数据库、推理机、解释部分和知识获取部分五个部 分组成。专家系统排课算法将专家系统的知识引入到排课系统中，通过将约束条 件放入知识库和把排课数据存入总体数据库，做到了使排课数据和排课原则从程序 中分离出来，利用排课知识策略进行规则推理，得到适应性更好更加符合实际情况 的课表。 使用专家排课系统来解决排课问题具有高效率和准确性，因为它能够汇集教务 排课人员的宝贵经验，使得排课能够快速高效地执行，但是研制专家排课系统的难 度比较大，由于获取排课过程要素间关联规则很困难，实际求解效果不是很理想， 而且研究要循序渐进，系统建好后需要不断地维护和完善。 3 分类优化算法 分类优化算法是模拟手工排课的一种方法，对排课各要素进行分类优化，采用 先难后易得优化决策，苟正伟在文献 2 1 中根据高校排课中的多个要素提