（计算机应用技术专业论文）基于net架构的高职院校调排课系统的设计与实现.pdf

摘要 摘要 高等职业教育在我国是一种新兴的职业教育模式。以前高职院校基本沿袭 中职的教学模式，相对而言，教务管理相对简单。但随着高职教育的改革，学 分制已逐步引入高职院校，成为学生的主要培养模式。由于高职院校的人才培 养目标有别于普通高校。在课程安排中，为了提高学生的实践能力，需要安排 大量的集中时间进行的实践性课程。这就给课程时间编排都带来了较大的难度。 如何妥善解决这些问题，尽快开发出一套针对高职具体实际，排课效率较高的 排课系统，对于简化高职院校的教务工作，提高工作效率有极大的促进作用。 本课题是四川机电职业技术学院“校园信息系统开发与设计”的子课题。 四j | i 机电职业技术学院是一所企业办学的高等职业技术学院，隶属于攀钢( 集 团) 公司。该学院希望改变原先传统的中职教学模式，以适应高职院校的学分 制改革试点工作及攀钢( 集团) 公司的职工培训工作。在排课系统开发中，要 充分考虑到学院的具体实际( 如，针对攀钢( 集团) 的职工技能培训任务较重， 并且时间随机性较强，需要预留教学资源等。) 。同时又要保证学院普通高职 学生，以及中专学生的正常教学和管理。 本论文正是针对上述问题，以高职院校排课系统的设计与实现为主要的研 究对象，在深入分析高职院校的教学管理模式及排课需求的基础上，对高职院 校排课系统的排课算法设计及应用软件的架构与实现进行了探索性研究。主要 内容为： 1 根据高职院校调排课系统的需求，进行了排课相关资源的规划及排课算 法的分析与设计。 2 根据需求分析和排课算法的设计，采用面向对象的思想，对系统的数据 库结构进行了设计，并讨论了对象模型向关系型数据库转换的相关规则及处理 方法。 3 介绍了n e t 的开发技术，以及分布式应用程序在n e t 架构下的设计与 实现。重点研究了本排课系统在n e t 架构上的设计与实现。 4 研究了n e t 架构下系统的访问安全策略及服务端w e bs e r v i c e s 的安全 摘要 访问策略及实现，同时对在n e t 架构下的分布式应用程序部署进行了探索。 关键字：排课算法，n e t 架构，w e b s e r v i c e s ，安全与部署 i i a b s t r a c t a b s t r a c t t h eh i g h e ro c c u p a t i o ne d u c a t i o ni sak i n do fn e w l ya r i s e no c c u p a t i o ne d u c a t i o n m o d ei no u rc o u n t r y i nt h ep a s t ，h i g h e rv o c a t i o n a le d u c a t i o nf o l l o w e dt h em o d e lo f s e c o n d a r yv o c a t i o n a le d u c a t i o n ，t h em a n a g e m e n t o ft e c h i n ga f f a i r si s r e l a t i v i n g s i m p l e w i t ht h er e f o r mo fh i g h e fv o c a t i o n a le d u c a t i o n ，t h ec r e d i ts y s t e mi sg e n e r a l l y i n t r o d u c e di n t oh i g h e rv o c a t i o n a lc o l l e g e s ，a n db e c o m e sam a i nc u l t i v a t i o nm o d e l a s t h e r ea r ed i f f e r e n c e sb e t w e e nt h ec u l t i v a t i o na i mo fh i 【g h e rv o c a t i o n a lc o l l e g e sa n dt h a t o fc o n l m o nc o l l e g e s d u r i n gt h ep r o c e s so fa r r a n g e m e n to fc u r r i c u l u m ，i no r d e rt o i m p r o v es t u d e n t s sp r a c t i c i n ga b i l i t y ，i tn e e d sal o to f c o l l e c t i v et i m ef o rs t u d e n t st oh a v e p r a c t i c ec l a s s e s ，w h i c ht a k e sg r e a td i f f i c u l t yt ot h ea s s i g r u n e n to ft i m e t a b l e i no r d e rt o s o l v et h e s ep r o b l e m s ，i ti s n e c e s s a r yf o ru st od e v e l o pas e to fm o r ee f f i c i e n t 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 es y s t e mf o rt h er e a l i t y o fh i g h e rv o c a t i o n a l e d u c a t i o n ，w h i c hw i l ls i m p l i f yt h et e c h i n ga f f a i r si nh i g h e rv o c a t i o n a lc o l l e g e sa n dh a v e a ne f f e c t i v ef o u n d a t i o no ni m p r o v i n gt h ew o r k i n ge f f i c i e n c y t h ee s s a yi sab r a n c hs u b j e c to f t h ed e v e l o p m e n ta n dd e s i g no fc o m p u s i n f o r m a t i o ns y s t e m o fs i c h u a ne l e c t r o n & m e c h a n i c a li n s i t u t eo fv o c a t i o na n d t e a c h n o l o g y s i c h u a ne l e c t r o n & m e c h a n i c a li n s i t u t eo fv o c a t i o na n dt e a c h n o l o g yi sa h i g h e rv o c a t i o n a lc o l l e g eb e l o n g i n gt op a nz h i h u ai r o na n ds t e e lc o m p a n y ( g r o u p ) t h e c o l l e g et r i e st oc h a n g et h et r a d i t i o n a lt e a c h i n gm o d e lo fs e c o n d a r yv o c a t i o n a le d u c a t i o n t ob emt ot h er e f o r mo fc r e d i ts y s t e ma n dt h ee m p l o y e e st r a i m n go fp a nz h i h u ai r o n a n ds t e e lc o m p a n y ( g r o u p ) i nt h ep r o c e s so fd e v e l o p m e n to fa r r a n g e m e n to fc u r r i c u l u m s c h e d u l es y s t e m ，i ti sn e c e s s a r yf o ru st oc o n s i d e rt h et r u es i t u a t i o no ft e c h i n g ，f o r e x a m p l e ，h e a v yt a s ko f t h ee m p l y e e st e c h n i q u et r a i n i n ge r e a tt h es a m et i m ew es h o u l d e n s u r et h en o r m a lt e a c h i n ga n d m a n a g e m e n t t oc o l n m o nv o c a t i o n a lc o l l e g es t u d e n t sa n d s e c o n d a r ye d u c a t i o n ss t u d e n t s a c c o r d i n gt ot h ea b o v ep r o b l e m ，t h ee s s a y t a k e st h ed e s i g na n da c c o m p l i s h m e n to f 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 es y s t e mi nh i g h e rv o c a t i o n a lc o l l e g e sa si t sm a i n r e s e a r c h i n go b j e c t b ya n a l y s i n gt h et e a c h i n gm a n a g e m e n tm o d e la n dt h en e e d so f 1 1 1 a b s t r a c t a r r a n g e m e n to fc u r r i c u l u mi nh i g h e rv o c a t i o n a lc o l l e g e s ，i th a sa l le x p l o r a t o r yr e s e a r c h o nt h ed e s i g no fa l g o r i t h mo fa 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 es y s t e ma n dt h e a c c o m p l i s h m e n to f a p p l i c a t i o ns o f t - w a r e t h em a i nc o t e n ti s 邪f o l l o w i n g ： 1 a c c o r d i n gt o t h en e e d so fa 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 es y s t e mi n h i g h e rv o c a t i o n a lc o l l e g e s ，i t i n c l u d e dr e $ o u r c c so nt h el a y o u to fs t r u c t u r i n ga c u r r i c u l u ma n dt h ea n a l y s i sa n dd e s i g no f a l g o r i t h mo f a r r a n g e m e n to f c u r r i c u l u m 2 a c c o r d i n gt ot h ed e s i g no fa l g o r i t h mo fa r r a n g e m e n to fc u r r i c u l u m ，a d o p t i n g t h et h o u g h to fo b j e c t - o r i e n t e d ，i td e s i g n e dt h es y s t e m ss t r u c t u r eo fr e l a t i o n a l d a t i v e a n dd i s c u s s e dt h er e l a t i v er u l e sa n dm e t h o d so ft h et r a n s i t i o no fo b j e c tm o d e lt o r e l a t i o n a l d a t a b a s e 3 i ti n t r o d u c e dt h ed e v e l o p m e n tt e c h n i q u eo f n e ta n dt h ed e s i g na n d a c c o m p l i s h m e n to f d i s t r b u t i v ea p p l i c a t i o ni n n e tf r a m e w o r k i tm a i n l yr e s e a r c h e dt h e d e s i g na n da c c o m p l i s h m e n to fa l g o r i t h mo fa r r a n g e m e n to fc u r r i c u l u mi n n e t f r a m e w o r k 4 i tr e s e a r c h e dt h es a f e t ya c c e s ss t r a t e g yo fs y s t e ma n dw e bs e r v i c e ss a f e t y a c c e s si n n e tf r a m e w o r k a tt h es i n 2 1 et i m e ；i th a da ne x p l o r a t i o no nd i s t r i b u t i v e a p p l i c a t i o np r o g r a m m e sd e p l o y m e n ti n n e tf r a m e w o r k k e y w o r d ：a l g o r i t h mo f a r r a n g e m e n to f c u r r i c u l u m ，n e tf r a m e w o r k ， w e b s e r v i c e s ，s a f e t ya n dd e p l o y m e n t i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 圭函应 日期：加，年，月t 1 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：凌卣密导师签名：垄燧 日期：加f 年，o 月，f 日 第一章引言 1 1 课题背景 第一章引言 随着我国高等教育体制改革的逐渐深入，高职教育作为一种新兴的办学类 型，得到社会的广泛认可。就读高职院校的学生数量大幅增加，相对于日趋紧 张的教学资源，如何充分、合理的安排使用有限的教学资源、实现资源利用的 最大化，是摆在各类高职院校面前的重要课题。由此，针对自身的特点，研究 和开发适用于自身的教学信息管理系统成为了当前高职院校信息化建设的一个 重点。四川机电职业技术学院于2 0 0 5 年中期开始研究与开发自己的学院信息管 理系统( i m p s ) 。高职院校调排课系统是我院i m i s 项目的子课题。 1 2 课表问题的研究历史与现状 知识经济时代正向我们走来，信息化己成为社会发展的时代特征。计算机 技术、通信技术和现代信息技术的迅速发展，以及管理科学、行为科学和系统 科学等相关学科的不断发展，为实现m i s 系统提供了坚实的理论与技术基础。 建设高校m i s 系统，不仅是时代发展的要求，而且是发展教育事业、提高高校 教学管理水平和办学效益的需要。高校m i s 是一个庞大的系统，包括方方面面， 其中一个很重要的子系统就是排课系统。 排课、调课是高校教务管理的一项日常工作，由于我国高校的基础设施相 对落后，加之近年来大规模的扩招，因而师资和教室资源紧张的问题非常普遍。 这项工作靠手工完成一般需要花大量的时间和精力，且多易出错。同时手工操 作也不易充分利用资源满足经常变化的需求。如利用计算机进行自动排课，不 但能使教务人员从繁杂的排课任务中解脱出来，大大提高教务管理工作效率， 而且能改善教学管理质量，合理高效地利用有限的资源。对于推动教学的发展 起到非常重要的作用。另外，解决排课问题对于解决其他多约束、大规模的时 间表问题也具有重要的指导意义。 在6 0 年代末，国外就有人研究课表编排问题。1 9 6 2 年，g o t l i e b 曾提出一 电子科技大学硕士论文 个课表问题的数学模型，此后人们又对课表问题的算法、解的存在性等问题作 了很多探索，但大多数文献中用到的数学模型都是g o t l i e b 的数学模型的简化 或补充【l 】【2 】【3 】。 有人把排课问题化成整数规划来解决，但计算量很大，至今没有一个切实 可行的算法；还有人试图用图论中的染色问题来求解排课问题，可惜图的染色问 题本身也是n p 完全问题。由于问题的复杂，许多文章利用启发式函数来解决 排课问题，大多数启发式方法都是模拟手工排课的过程来实现的【1 2 1 1 1 5 1 1 1 6 】。由于 实际的排课问题存在各种各样的限制条件与特殊要求，对这些因素处理的好坏 就显得尤为重要。进入9 0 年代，国外对排课问题的研究仍然非常活跃。如印度 u a s t a p u r 大学管理学院的a r a b i n d at r i p a t h y 、加拿大m o n t r e a l 大学的j e a na u b i n 和j a c q u e s a f e r l a n d 以及c h a r l e sf l e u t e n t 等。a r a h i n d at r i p a t h y 的工作是 针对以“人”为单位进行课表编排的。他运用拉格朗日松弛法和分支定界法求 解，这种方法的缺点是为减少变量的个数，人为造成科目间的冲突。a t r i p a t h y 还研究了研究生课表编排问题，他采用多重课组的方法来处理冲突。( 即根 据学生选课的矛盾情况，将选修人数多的课程在一星期内多次行课) 。j a c q u e s a f e r l a n d 等人则把排课问题分成两个子问题：时间表问题和分组问题。在时间 表问题中，根据学生注册情况、教师和教室的可利用情况形成一个主时间表。 对于选课人数较多的大课，一星期要分成几个时间段来上，分组问题就是将学 生分给各时间段【1 0 】【l l 】。两个问题相关联，通过惩罚因子来构造启发函数。他们 研制的s a p h i r 课程调度决策支持系统分为数据处理、自动优化、交互优化等 几个模块。该系统解决矛盾的主要方法也是采用多重课组。这与他们西方的教 学管理体制是密不可分的。 另外澳大利亚的一批学者还将模拟退火法应用到排课问题的研究中。模拟 退火法( s i m u l a t e da n n e a l i n g ) 是k i r k p a t r i c k 等人于1 9 8 3 年首先提出的，它是人 们从自然界固体退火过程中得到启发并从中抽象出来的一种随机优化算法。模 拟退火法用于求解优化问题的出发点是基于物理中固体物质的退火过程与一般 优化问题间的相似性。在对固体物质进行退火处理时，常先将它加温，使其粒 子可自由运动，以后随着温度的逐渐下降，粒子逐渐形成低能态晶格。若在凝 结点附近的温度下降速率足够慢，则固体物质定会形成最低能量的基态，优化 问题也存在类似过程。模拟退火法被用来解决许多实际应用中的优化问题，取 2 第一章引言 得了不错的效果，但用其来解决排课问题，现在还处在模型试验阶段，还有许 多问题要解决【9 1 ， 国内对排课问题的研究开始于8 0 年代初期，所用方法从模拟手工排课到运 用人工智能构建专家系统或决策支持系统都有。成型系统早期的有南京工学院 的u t s sc 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 ) ，大连理工大学的智能教学组织管理与课程调度系统等。9 0 年代后大连理工大学教学组织管理与课程调度系统的开发人员不断地修改更新 该软件，使其功能不断扩大。1 9 9 2 年推出教学组织管理及课程调度系统2 1 版本和安排考试补考的考试调度系统，并把它们合在一起形成了教学 调度系统，1 9 9 8 年推出了在w i n d o w s 下运行的3 0 版本。清华大学计算机与 信息管理中心开发的综合教务管理系统是9 0 年代后期一个较全面的高校教学 管理系统，其中包括排课系统，但其造价较高。 目前，解决课表问题的方法有：模拟手工排课法，图论方法，拉格朗日松 弛法，二次分配法等多种方法【4 】【5 】【6 】【7 1 。国外的研究表明，解决大规模课表编 排问题单纯靠数学方法是行不通的，而利用运筹学中分层规划的思想将问题分 解，是一个有希望得到成功的办法。国内排课系统大都是模拟手工排课过程， 以“班”为单位，运用启发式函数来进行编排的，但是这些课表编排系统往往 依赖于各个学校的教学体制，不宜于进行大量推广【1 3 】【1 4 】【15 1 。 总的说来，国内由于各高校资源的不同、习惯( 约束) 的差异、排课软件适 用性还不够。就四川机电职业技术学院来说，前后购买过几个排课软件，但都 因无法与现有的系统集成，不能很好的应用。所以研究高效、灵活的排课系统 不但仍有意义而且是迫切的需求。 1 3 课题在理论和实际应用方面的意义和价值 四川机电职业技术学院是一所攀钢( 集团) 公司出资办学的学院。学院除 了承担普通高职学生的教学任务以外，还承担着( 集团) 公司大量的职工培训 任务。而这类职工培训工作，学习时间，课程设置都是根据实际需要来确定的， 具有较大的随机性，灵活性。同时，高职院校的课程设置与普通高校相比，也 具有其特殊性。高职院校课程设置更强调实际操作和动手能力，在学习期间需 电子科技大学硕士论文 要安排大量的实习、实训时间。这使教学安排的复杂度增加。由此，如何设计 一个较好的排课算法，以满足高职院校的排课需求，从而推进高职院校的教学 信息化建设，具有重大的意义和实用价值。 1 4 作者的主要工作 基于n e t 的高职院校调排课系统是2 0 0 6 年度攀钢( 集团) 公司的创新项 目，同时也是四川机电职业技术学院2 0 0 6 年度科研项目“学院信息系统”的子 课题。本人全面负责本课题的分析、设计工作。主要工作如下： 1 对于高职院校的调排课系统进行需求分析。 2 高职院校调排课系统的算法设计。 3 基于n e t 的系统架构与实现。 4 x m lw e bs e r v i c e s 的访问安全。 5 系统的部署。 1 5 论文的组织结构 本论文首先对高职院校调排课系统进行了需求分析和算法设计。然后在n e t 架构模式进行设计与实现。以下是论文的主要内容。 第一章：引言 介绍了本课题的研究背景及该课题在理论和实际方面的意义和价值，同时 介绍了作者的主要工作。 第二章：高职院校调排课系统的算法设计 根据高职院校调排课系统的需求，进行了排课相关资源的规划及排课算法 设计。 第三章：高职院校调排课系统数据库的设计 根据前面的需求分析和算法的需要，进行了系统的数据库的概念结构和逻 辑结构的设计。 第四章：系统在n e t 架构下的设计与实现 4 第一章引言 本章介绍了n e t 的分布式开发技术，以及分布式应用程序的设计与实现。 重点讲解了该系统在n e t 架构上的设计与实现。 第五章：系统的安全与部署 本章介绍了n e t 架构下系统的访问安全策略及服务端w e bs e r v i c e s 的安 全访问策略及实现。 第六章：总结与展望 本章对该系统从需求分析到算法设计及实现进行总结，同时也对高职院校 教学管理的新动态进行了展望。 电子科技大学硕士论文 第二章高职院校调排课系统的算法设计 本章通过对排课问题的分析，结合高职院校排课系统的实际，设计出基于 贪心策略的排课算法，并对算法的性能做了比对和测试。 2 ，排课问题的描述 从数学上讲，排课问题是一个在时间、教师、学生和教室四维空间上，以 教学计划和各种特殊要求为约束条件的组合规划问题。其实质就是解决各因素 之间的冲突。 设课表问题： r t e = t ，p ，c ，k ) 式中： t 为时间集合 t i ，t 2 ，t 3 ， ta ) p 为教师集合 p l ，p 2 ，p 3 ， pb c 为教室集合 c l ，c 2 ，c 3 ，c v ) k 为课程集合 k l ，k 2 ，k 3 ， k 5 ) 课表问题的求解目标就是找到一个解集合r t i ，p j ，c k ，i q 使其满足以下 的硬约束和软约束条件。其中 t i ti l ，2 o p j pj ( 1 ，2 1 3 ) c k ck l ，2 y ) k i kl 1 ，2 6 1 硬约束条件：要求系统保证必须满足的约束条件。 ( 1 ) 除公共课外，同一时间，一个教室只能被一个班级占用。 ( 2 ) 同一时间，一个教师只能在一个教室上课。 ( 3 ) 除选修课外，同一时间，一个班级只能安排一门课程。 ( 4 ) 教室的类型必须与课程要求一致。比如：电子实验课程必须在电子实 验室进行等。 6 第二章高职院校调排课系统的算法设计 ( 5 ) 教室的最大容纳人数必须大于等于在该教室上课的学生人数。 2 软约束条件：系统不要求必须满足，但满足这些条件能得到较优解。 ( 1 ) 同一门课程的上课时间尽量间隔均匀。如某课程周学时为4 学时，以2 学时为一个教学单位，需安排两次。两次的安排时间尽量间隔一天或者一 天以上。 ( 2 ) 课程上课时间尽量安排在星期一至星期五的l 一6 节。 ( 3 ) 教室尽量集中、充分的利用。以便留出空闲教室供学生上自习。 ( 4 ) 对于周学时为奇数的课程，仍按2 学时为一个教学单位进行行课。但 对其中学时数为1 的教学时间点进行单周日排课或者双周排课安排。 ( 5 ) 对班级、教室、教师的单双周上课时问点尽量匹配，以节约教学资源。 如某班级、教师或者教室星期一l 、2 节单周行课。下一门分单双周上课 的课程尽量安排在星期一1 、2 节双周行课。 ( 6 ) 对于上课时间有特殊要求的教师和课程尽量满足其时间要求。如教师 因其它工作需要，提出某一天不能上课等。 2 2 排课算法的设计 本算法利用优化理论及后期评估思想进行算法设计。即首先以课程为线索， 找出所有满足硬约束条件的上课时间点并利用优化函数计算出各个时间点上的 优化值，然后假设安排该课程在此时间点的条件下，对后期需要排课的其它课 程以最优值进行后期估价汇总，选取后期估价汇总值最大的时间点安排课程。 2 2 1 排课预处理 2 2 1 1 课程集合k 的划分及优先级策略 定义2 1 ：课元兀将课程的周学时( z t ) 按照每一次独立行课的学时数 ( c t ) 进行拆分的上课时间单元。即： 吲=dzt(2-1) 将所有待排课课程都拆分成课元，然后按照表2 - 1 的条件计算权值。 7 电子科技大学硕士论文 表2 - 1 条件优化权值表 条件权值 该课元所属的课程是合班课，公选课。 5 0 该课元行课的可用时间点最少。3 0 该课元的学时数为l ，即属于单或双周行课。 2 0 这样，权值大的课元比权值小的课元优先排课，可以大大降低冲突量及算 法的复杂性。 2 2 1 2 教室集合c 的划分 将所有上课的教室按照用途划分成多种类型，见表2 2 表2 - 2 教室用途类型划分表 类型 编号类型编号 普通教室 r l投影教室r 2 物理实验室 r 3 多媒体教室 r 4 化学实验教室 r 5 制图教室r 6 计算机实验教学 r 7 体育场地 r 8 每一类用途的教室又按照容纳学生人数划分为大型、中型、小型教室。见 表2 - 3 教室容纳人数类型划分表 教室容纳学生人数类型 1 3 0 人 小型教室 3 1 5 0 人中型教室 5 0 人以上 大型教室 通过上述方式对教室进行划分，可以直接针对课程所需的教室类型和容纳 人数进行查找可用教室，大大的减少了教室的查找时间。 第二章高职院校调排课系统的算法设计 2 2 1 3 构造时间模式库。 时间模式是根据教务人员的经验，为各种周学时数不同的课程指定的一种 时间组合方式。例如，一门课程的周学时数为4 ，那么它的时问组合方式可以 有：“”，“4 l ”；表示该课程一周上两次，分别为周一的1 2 节和周四的l 2 节上课。同时，为了达到较好的上课效果，也要对这些时间模式进行分级。 如下表2 - 4 所示时间模式分级举例。 表2 - 4 时间模式分级匹配表 周学时优先级 周一周二周三周四周五周六周日 4 l1 14 l 422 24 3 其中，将周一至周日用数字1 7 表示，上课节次：1 2 节、3 4 节、5 6 节、 7 8 节、晚1 2 节分别用数字1 5 表示。例如数字“4 2 ”表示周四的3 4 节，这 个时间单元。这样，对于每种周学时数，可以将所有合理的时间组合形式存入 模式库中。以便进行时间处理时可以用时间模式库中的各种模式进行匹配。 2 2 1 4 构造时间字符串 为了表示班级、教师、教室的可排课时问，分别用3 个字符串表示时间点， 字符串中的位置信息表示天次、节次( 见图2 1 ) 将一天分为5 个间点，每周7 天，共3 5 个时间点。图中一个方格表示一个时间点，每个方格包含两个字符。 1 62 1 图2 1 时间字符串 每个时间点的两位字符含义如下( 见表2 5 ) ： 9 电子科技大学硕士论文 表2 5 时间点字符含义表 第一位字符表示状态 o该时间点未排课，处于空闲状态。 l该时间点单周已排课。 2 该时间点双周已排课。 3该时间单周和双周都已排课。 为了能够记录某一个时间点连续上课的周数，第二位字符以卜z 的2 6 个 大写字母来表示该时间点课程的上课结束周。其中，a 表示第l 周，z 表示第 2 6 周。如：某时间点的两个字符为“0 0 ”表示该时间点空闲。“2 l ”表示该时 间点双周已排课，课程将在第1 0 周结束。值得注意的是，如是一个时间点单周 和双周分排了一门课。第二个字符记录的是最后结束那一门课程的结束周。 2 2 2 基于贪心策略的排课算法 2 2 2 1 贪心策略 指从问题的初始状态出发，通过若干次的贪心选择而得出最优值( 或较优解) 的一种解题方法。其实，从“贪心策略”一词我们便可以看出，贪- i f , 策略总是 做出在当前看来是最优的选择，也就是说贪，i i , 策略并不是从整体上加以考虑， 它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定 了该题运用贪心策略可以得到最优解或较优解。贪心策略具有以下两个主要的 特点： 1 贪心选择性质： 所谓贪心选择性质是指应用同一规则f ，将原问题变为一个相似的、但规 模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已 做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问 题在程序的运行过程中无回溯过程。 2 局部最优解： 由于运用贪心策略解题所求得的解可能是局部最优解，不能保证求得的解 是整体最优解。贪心策略只能求满足某些约束条件的可行解的范围，但排课问 l o 第二章高职院校调排课系统的算法设计 题本身并不一定需要整体最优解。在很大程度上，我们只需要求得一个次优解 或者满足解即可。 2 2 2 2 估价函数的设计 1 可用时间点的优化函数的设计 厂( k 。，7 z ，) = 薯表示k 。条件下，课元石安排在时间点上的优化 i = l 度。其中，墨。表示已排部分课程的课表；万表示当前待排的课元；是当前 课元的某一可用时间点；( 1 i s ) 表示所有软约束( 即优化条件) 的权值。 z o ，1 ) 表示在硌。条件下，若将分配给课元石后，课元石的安排是否满足 第i 个优化条件，若满足玉= l ，则，否则葺= o 。 2 后期估价函数的设计 胃( 工) = m a x ( ( 如。，乃，护) ) 表示在第f 个课元已安排产生部分课表 j = n - i + l k s 的情况下，课元乃( i j n ) 按最佳安排策略即m a x ( f ( k s v n , ，一，r e ) 安排 时间点后的总体优化值为( x ) 。日( 功的值越大，表明课元乃安排的时间越合 理。所以我们选择课元巧所有的可用时间点中，满足m a x ( h ( x ) ) 的时间点为当 前课元巧安排的时间点。日( 砷是当前排课课元巧所选时间点对后期所有待排课 课元的影响作出的一个整体评价。这也是我们整个贪心策略在选择课元上课时 间点的一个评价函数。 2 2 3 算法整体流程描述 算法的整体流程见苫墨( 图2 2 ) 。 电子科技大学硕士论文 图2 - 2 算法整体流程图 2 2 4 算法的时空复杂度分析 2 2 4 1 算法时间复杂度的计算 如果所有划分时间点数为o ( m ) ，而判断一个时间点是否可行需要时o ( m ) 。 1 2 第二章高职院校调排课系统的算法设计 因此获得c 的所有可用时间点需要时间o ( m 2 ) 。如果所有的课元n 都按照优化 值最大的时问点进行安排所需时间为o ( n m 2 ) 。由此，后期估价函数对于一个时 间点进行估价所需时间为o ( n m 2 ) ，所以对于一个课元的时间安排所需时间为 o ( n m 3 1 。我们可以得出，对于课元数为n 的整个排课算法所需时间为o ( n 2 m 3 ) 。 2 2 4 2 算法空间复杂度的计算。 在整个算法中，存储n 个待排课课元所需空间为o c n l ，存储m 个时间点所 需空间为d ( 掰) 。其它数据的存储空间需求不会超过o ( m + 栉) 。所以整个算法的 空间复杂度为o ( m + n ) 。 2 3 算法的测试及应用 2 3 1 测试用例 本排课算法采用了四川i 机电学院的某一学期的排课安排实际数据作为测试 数据，测试数据描述如下( 见表2 - 6 ) ： 表2 - 6 测试用例数据 序号名称数值 l 班级数目 5 2 2教师数目1 3 2 3课元数目6 3 3 4教室数目4 5 5课程总周学时数1 2 4 8 ( 不含选修课) 6班平均周学时数2 4 7班可用时间点总数2 6 8单双周课程数1 8 9分段行课课程数1 3 1 0合班课课程数 1 4 1 l专业选修课课程数3 0 1 2全校公选课课程数 6 1 3可用时间点课元数目1 1 电子科技大学硕士论文 注：选修课是根据四川机电职业技术学院的实际情况，统一安排在下午7 - 8 节和晚上9 1 0 节行课。 为了准确的评价算法的性能，下面例出了在本测试中采用的优化条件及相 应的权值( 见表2 7 ) 。 表2 7 排课优化条件权值表 序号优化条件优化权值权值百分比 l上课时间要尽可能间隔均匀 75 2 2同一门课程的教室尽可能相同11 3该课程在特定时间上课 75 2 4上课时间尽量安排在星期1 52 92 1 5每曰上课时间尽量安排在1 6 节2 9 2 1 6单、双周课程班级匹配75 2 7单、双周课程教师匹配 75 2 8单、双周课程教室匹配75 2 9同组课程同时开课 4 l3 1 通过上述测试数据的运行，排课算法性能( 见图2 3 ) 。 8 0 0 0 0 掣7 0 0 0 0 篁6 0 0 0 0 警5 0 0 0 0 氧4 0 0 0 0 垂黜0 0 0 ： 1 0 0 0 0 0 - 一一 1 1i 3 1 51 71 9 z o z 2 z 5 可用时间点课元数且 图2 3 排课算法性能图 图2 3 中的横坐标为总可用时间点总课元数目，该比值反映了课程安排的 灵活度。该比值为l 时，表明每一个课元有且仅有一个位置可以安排。比值大 于1 ，表明可用的时间点多于需要安排的课元数，排课可选择的时间点较多。 图中纵坐标表示的是课表的整体优化值，其越大，表明课表满足的优化条件越 1 4 第二章高职院校调排课系统的算法设计 多，排课效果越好。 从图2 - 3 中可以看出，本排课算法与四川机电学院的原先购买的排课系统 相比而言，在排课条件较苛刻的情况下，表现出了良好的性能。当条件宽松时 ( 即可选用的时间点较多的情况下) ，两者效果基本一致。 2 3 2 算法应用 本排课算法应用于四川机电学院的排课系统中，通过两学期的实际应用， 排课效果较好，完全满足了学院的课程安排需求。 2 4 小结 类似于排课表这样的时间表问题( t t p ：t i m e t a b l ep r o b l e m ) ，是典型的组 合优化和不确定性调度问题并且己被证明是n p 一完全性问题，不存在确定型多 项式复杂性解法。因此，人们把研究的重点放在启发式算法上。课表问题的难 度在于：首先，它是个多元受限的问题，如果一定要满足所有的约束条件( 这些 条件往往是相互矛盾的) ，则极有可能找不到完整解。其次，它是一个好坏标准 很难统一的问题；同一个排课结果，有人说好，有人说不好。因此其质量标准 很难固定和量化。课表问题的上述特点说明，一个好的排课系统，通常要使用 启发式算法，而且要与用户有很强的交互性，可由用户确定每个条件的权值， 并可根据对排课结果的不同看法，对条件的权值作调整和重排，以满足不同用 户对课表质量的要求。为此，作者选择了基于贪心策略的前景探测算法，具有 交互性好，排课灵活的特点。 1 5 电子科技大学硕士论文 第三章高职院校调排课系统数据库的设计 本章通过排课系统的用例分析，得到排课系统的类图，并详细的论述了对 象模型向关系数据库模型的相关规则及方法。同时结合排课的实际情况，运用 上述方法，得了排课系统的数据库表及关系。 3 1 数据库设计概述 数据库设计方法有两种，即属性主导型和实体主导型。属性主导型从归纳 数据库应用的属性出发，在归并属性集合( 实体) 时维持属性间的函数依赖关系。 实体主导型则先从寻找对数据库应用有意义的实体入手，然后通过定义属性来 定义实体。一般现实世界的实体数在属性数1 1 1 0 以下时，宜使用实体主导型设 计方法。面向对象的数据库设计是从对象模型出发的，属于实体主导型设计。 3 2 应用对象模型与r d b m s 模型的映射 数据库设计( 模式) 是否支持应用系统的对象模型，这是判断是否是面向对 象数据库系统的基本出发点。由于应用系统设计在前，数据库设计随后，所以 应用系统对象模型向数据库模式的映射是面向对象数据库设计的关键。 3 2 1 三层数据库模式面向对象模型的扩展 一般数据库设计多参照a n s i s p a r c 关于数据库模式的3 层标准结构方 案。最接近物理数据库的内部模式由d b m s 提供的s q l 来描述。概念模式可 以由若干个内部模式聚集而成，它是由数据库用户规范的一些表的集合。例如， 在排课系统中，学生信息数据库模式、教师信息数据库模式等，它们都是逻辑 数据库，常常通过库表i d 来界定库边界。一般的概念模式是数据库物理模式 作用域的边界，它能实现数据库的物理意义、特定d b m s 的特殊操作对外部 应用程序的信息隐蔽。外部模式是从特定用户应用角度看待的数据库模式。从 不同的应用出发，对同一概念模式可以给出多种不同的外部模式，但是它们可 1 6 第三章高职院校调排课系统数据库的设计 能访问的是同一个库表的不同子集。当外部应用系统以对象模型进行抽象时， 从各个应用出发抽象出的对象模型可以映射到外部模型上，对此我们不妨称之 为外部对象模型。但是，外部模型只是概念模型的子集，所以面向对象的数据 库设计核心在于系统对象模型向数据库概念模型的映射。 3 2 2 对象模型向数据库表的映射规则 由于r d b m s 是以二维表为基本管理单元的，所以对象模型最终是由二维 表及表间关系来描述的。换言之，对象模型向数据库概念模型的映射就是向数 据库表的变换过程。有关的变换规则简单归纳如下： 1 一个对象类可以映射为一个以上的表，当类间有一对多的关系时，一个表 也可以对应多个类。 2 关系( 一对一、一对多、多对多以及三项关系) 的映射可能有多种情况，但一 般映射为一个表，也可以在对象类表问定义相应的外键。对于