（计算机应用技术专业论文）基于专家系统的排课软件的研究与设计.pdf

摘要 扫 课是学校教学管理中十分重要、又相当复杂的管理工作之一。其实质 就是为学校所设置的课程安排时间和地点，从而使整个教学能够有计划有秩 序地进行。随着信息技术的飞速发展，学校教务管理对计算机排课的要求非 常迫切，但目前尚未有普遍适用并反映良好的计算机排课系统。有人把排课 问题化成整数规划来解决，但计算量很大，至今没有一个切实可行的算法。 还有人用图论中的染色问题来求解排课问题，但染色问题本身也是一个n p 完全问题。许多排课软件利用启发式函数来解决排课问题，但大多数启发式 方法都是模拟手工排课的过程来实现的，因而受到人为因素的丁扰较多。总 的来说这些课表编排系统各有优缺点，具体实施时往往比较依赖于各个学校 具体的教学体制，通用性不强。、， l 本文通过对近年来国内外的各种有关排课文献以及各种排课方法进行深 入细致地分析综合，汲取各自的特点，以专家系统为构架，对开发通用型实 用排课系统进行了积极有益的尝试。首先，利用专家系统中知识库与推理机 相分离的思想，使排课规则与排课推理机制相互独立，以解决课表编排的通 用性的问题。其次，在推理机的设计中利用了资源分配的思想，把排课问题 看成是对需求者合理地进行资源分配并避免资源冲突的过程。这个过程是分 步完成的，将每一步的输出作为下一步的输入，出现冲突及时返回调整。在 资源分配过程中，应用线性规划中分治法的思想，将排课这样一个多维的资 源分配问题转化成几个一维的资源分配问题加以解决，从而降低了推理过程 的时间复杂度。最后，在解决冲突的过程中，对传统的与或图深度优先的有 界搜索算法进行了改进，提出了与或图的路径标识搜索算法。同时，利用启 发函数的思想，根据人工实际排课的经验，建立若干组启发式信息，即课程 进度选择模式，系统按照这些模式去安排课程进度，以保证课表编排的的合 堕巫婆三里盔兰堡主堂垡堡塞 理性以及提高编排的效率。 作者利用本系统对所在学校的三个学期的不同要求的的课表进行了实际 编排，并对其他几所不同体制的学校的课表进行了试验性编排，经教务部门 验收合格。通过几次的排课实验表明，本文所提出的课表编排理论对开发通 用型实用排课系统具有积极的意义。 关键字： 专家系统：自动排课；知识表示；推理机制 哈尔滨工程大学硕士学经论文 a b s t r a c t t h ea r r a n g i n gs c h e d u l ei so n eo ft h em o s ti m p o r t a n ta n dt e m p i i c a t e d j o bi nas c h 0 0 1 t h ee s s e n t i a li sa r r a n g i n gt h et i m ea n dp l a c ef o re v e r y c l a s si no r d e rt h a tw h o l et e a c h i n gw i l lb ec a r r je do no r d e r l y w i t h t h e d e v e l o p m e n t o ft h e i t ，t h er e q u e s to f a r r a n g i n gs c h e d u l eb y c o m p u t e ri sv e r yu r g e n t ，b u tt h e r ei sn ou n i v e r s a la r r a n g i n gs c h e d u l e s y s t e mt h a th a v eb e e na c c e p t e db yt h em a s s e s s o m ep e e p er e g a r dt h e a r r a n g i n gs c h e d u l ea st h eq u e s t i o no fi n t e g r a lp r o g r a m m i n g ，b u tt h e c a l c u l a t i v es c a l ei sv e r yg r e a t ，t h e r ei sn oas u i t a b ea r i t h m e t i ct o s o l v ei t t h eo t h e r s m a n a g et ou s et h ep a i n t e dt h e o r yo fc h a r tt os 0 1 v o i t ，b u tt h a ti sa l s oan pc o m p l e t eq u e s t i o n m a n ya r r a n g i n gs c h e d u l e s y s t e m su s et h eh e u r i s t i cf u n c t i o nt od ow i t hi t b u ti t w j l ib e d i s t u r b e db ym a n ym a n m a d ef a c t o r s i naw o r d ，t h e s e a r r a n g i n gs c h e d u l e s y s t e m sh a v et h e i ro w nv i r t u e sa n df a u l t s ，i tw i l lb el i m i t e db vt h e e d u c a t i o n a ls y s t e mo fas c h o o l ，t h eu n i v e r s a l c a p a b i l i t yi sn o tv e r y s t r o n g t h i st h e s i si sb a s e do ne x p e r ts y s t e m sf r a m ea n dh a st r i e dt o d e v e l o pa u n i v e r s a la n d a p p l i e da r r a n g i n gs c h e d u es y s t e m s t h e f i r s t ，b yu s i n gt h et h e o r yt h a tt h er e p o s i t o r yi s s e p a r a t e df r o mt h e d i s c u r s i o ne n g i n ei nt h ee x p e r t s y s t e m ，t h er u l e so ft h ea r r a n g i n g s c h e d u l ea r es e p a r a t e df r o mt h ed i s c u r s i o n e n g i n eo ft h ea r r a n g i n g s c h e d u l ei no r d e rt os o l v et h eu n i v e r s a l p r o b l e mo ft h ea r r a n g i n g s c h e d u l es y s t e m t h es e c o n d ，b yu s i n gt h et h e o r yo nt h ea l l o c a t i o no f r e s o u r c ei nt h ed e s i g no ft h ed i s c u r s i o ne n g i n e ，t h e a r r a n g i n ga c h e d u l e 哈尔滨工程大学硕士学位论文 p r o c e s si sr e g a r d e d a st h ea l l o c a t i o no ft h er e s o u r c e sf o rt h ed e m a n d e r i nt h i sp r o c e s s ，b ym a k i n gu s eo ft h et h e o r yo fd e e o m p o s a b i l i t y ，a m u l t i - d i m e n s i o np r o b l e mi sc h a n g e di n t os o m eo n e d i m e n s i o np r o b l e m s i no r d e rt or e d u c et h et i m ec o m p e x i t y a tl a s t jnt h ep r o c e s so f g e t t jn gr i do fc o l l i s i o n ，an e wa l g o r i t h mt h a tm a r k st h es e a r c h jn gp a t h i sg i v e n a tt h es a m et i m e ，m a n yg r o u p so fh e u rjs t i ci n f o r m a t i o na r e s e tu pt os o l v et h es e h e d u l eo fc l a s s m o r eo v e ri tw i l lm a k et h ec l a s s t a b l e l o o k sm o r es u i t a b l e t h ea u t h o rh a v ea r r a n g e dt h ec l a s st a b l e so ft h r e et e r m sb yt h i s s y s t e mi nh i ss c h o o l ，a n dh a v ed o n et h es a m et h in gi na n o t h e rt y p eo f s c h o o l ，t h ec l a s st a b l e si sc h e c k e db yt h ee d u c a t i o n a la d m i n i s t r a t i o n d e p a r t m e n ta n dt h i ss y s t e mi ss u i t a b l e t h et h e o r yu s e di nt h i sa r t i e l e i s s i g n i f i c a n t i n d e v e l o p i n g t h eu n i v e r s a la n d a p p l i e da r r a n g i n g s c h e d u l es y s t e m k e yw o r d s ： e x p e r ts y s t e m ia r r a n g i n gs c h e d u l ea u t o m a t i c a l l y k n o w l e d g er e p r e s e n t a t i o n ： i n f e r e n c ee n g i n e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献等的 引用已在文中指出，并与参考文献相对应。除文中已经注明 引用的内容外，本论文不包含任何其他个人或集体己公开发 表的作品成果。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律 结果由本人承担。 作者( 签字) ： 日期：年月日 哈尔滨工程大学硕士学位论文 1 1 引言 第1 章绪论 排课是学校教学管理中十分重要、又相当复杂的管理工作之。其实质 就是为学校所设置的课程安排时间和地点，从而使整个教学能够有计划有秩 序地进行。目前，国内大部分学校仍然采用手工排课的方法，然而为几千名 学生和几十个专业的教师安排出合理的课程表往往需要花费教务人员一、二 个月的时间，工作量大、排出的课表不宣调整。随着我围教育体制改革的深 入，学生人数不断增加，课程设置不断向深度和广度发展，手工排课的缺点 就越来越突出。 由于计算机具有运算速度快，处理能力强等特点，很自然地进入到这一 应用领域中。用计算机进行排课能够快速地得到满足约束条件的可行结果， 具有排课时间短，人力省和质量高的优点。因此，人们的工作更多转向了实 际课表的计算机编排上。 1 2 计算机排课的目的和意义 在我国现行的教育体制下，学校大体上分为三类：普通中小学、普通高 校、中等专业学校以及职业学校等。这些学校对课程表有着各自不同的要求， 总的来说有如下特点。 1 、中小学 同年级的学生课程设置相同，每班人数大体相同，教室相对固定。一般 情况下，教室是足够多的，排课时不用考虑教室因素，但对课程的进度有着 比较严格的要求。 晗尔滨工程大学硕士学位论文 2 、普通高校 由于高校学生选课的灵活性，使得每门课的听课人数参差不齐。新旧课 程的不断更替，使课程变化较大“。而且，各高校普遍教室紧张，班级和教 室之间不可能做到一一映射，而是一种多对多的映射，即每个班级要在多个 教室上课，同时每个教室也要为多个班使用。或是多对一的映射，即几个班 同时在一间教室上合班课。 3 、中职学校 该类学校处于普通高校和中小学之间，一般来讲课程变化较大，各个班 级人数参差不齐。每个教师的周课时量都很大，对课程进度有一定的要求。 各班上课教室相对固定，但也有合班上课的要求。 可见，不同体制的学校对课程编排有着不同的要求，课程表问题具有很 大的灵活性。但传统的课程表编排是由人工来完成的。教务工作人员在长期 的工作实践中摸索出了一些既行之有效，又切合实际的手工编排方法。在高 校中有代表性的编排流程为校教务处首先根据各系汇总上来的开课情况，预 测教室的总需求量，按此提供专用教室，形成公共课程表，即，张包括公共 课程、教室、时间和任课教师的课程表。然后再根据各系开课情况及教室占 用情况，进行教室预分配，并将分配表发到各系，各系教务人员则在此基础 上安排本系课程，经过与其他系相互协商，最后形成各系专业课程表，汇总 到校教务处，形成全校的课程表“3 。 其工作流程如图1 1 所示。 哈尔滨工程大学硕士学位论文 校教务处 校教务处 校教务处 校教务处 形成公共课程表 教室预分配表 上下发 办卧 王汇总 校教务处 争h 计伊h | | t l萎例萎卜、l 霎例羹 汇总 工汇总工 汇总 工、7 总 形成最终课程表( 全部) 倒1 1 高校课表编排流程 随着学校规模的扩大，排课涉及的因素越来越多，问题越来越复杂，使 得这项工作耗费了大量的人力，总的来说人工排课存在如下因难。 ( 1 ) 工作量大，耗费较多的时间和人力。 ( 2 ) 课程、教师、学生及课时等数据关系繁杂，人工管理效率低。 ( 3 ) 涉及因素多，要做到考虑全面、没任何冲突很困难。 ( 4 ) 细小数据的调整，往往牵涉很广，增加很多工作量。 ( 5 ) 课表填写、数据汇总等简单重复性工作量很大。 因此，课程表编排问题一直被人们认为是最困难的作业调度问题之一。= “。 随着计算机的应用已从科学计算，实时控制方面逐渐扩展到非数值处理的各 个领域，计算机系统在办公自动化的应用日益受到各行各业的极大关注。 计算机的应用为人们提供了现代化的工具和手段，应用计算机技术进行 哈尔滨工程大学硕士学位论文 自动排课，可以大大提高排课效率，合理分配有限的教室和教师资源，尽可 能减少排课流程中的人为因素的干扰，从而使得课程表更加合理。 1 3 研究动态 二十世纪五十年末六十年初，国外就有人开始对课程表问题进行了研究。 在1 9 7 5 年以前的一段时间里，人们主要从构造算法模型入手，研究其解决方 法，目的是能找到一个解决问题的有效算法。1 9 6 2 年，g o t l i e b 提出了一个 构造课程表的数学模型”3 ，接着人们对这个模型算法，解的存在性等问题作 了许多探索，并提出过一些新的算法模型“，但始终未能找出一个有效算法。 1 9 7 5 年，e v e n 等到人证明了课表问题是个n p 完全类问题“。对于大多 数这类问题，迄今为止还没有找到在多项式步骤内解决的有效算法。因此， 人们寻求有效算法的探索才告一段落，而将更多精力转到如何借助计算机这 一现代化工具来解决实际课程表的编排问题。 随着我国教育事业的蓬勃发展，课程表调度问题越来越尖锐地摆在人们 面前。二十世纪八十代初，国内一些大学也开始了对课表问题的研究。随着 计算机在教育行业的普及应用，产生了不少排课系统，有用程序设计语言开 发的，也有用数据库管理系统开发的”。但目前还没有一种能为大家所普遍 接受的产品，究其原因主要有以下两点。 ( 1 ) 现有的排课系统大多采用传统方法进行程序设计，排课所用数据与 程序结合过于紧密。排课系统的事实数据相对于不同学校、不同班级差异 很大，排课的规则要求也有很大的不同。这些数据与程序结合过于紧密， 就会限制系统的通用性。同时对于程序的修改维护工作也带来很大难度， 不便于系统扩充和升级。现有排课系统有的也使用了独立的数据文件或数 据库文件，但设计思路仍是咀程序为核心，数据只是作为程序的附属文件 存在，排课规则也主要由程序体现，系统仍存在不便于扩充的弊端。 哈尔滨工程大学硕士学位论文 ( 2 ) 现存排课系统重点考虑了一般性排课原则，初排后的课表往往需要 针对各种特殊情形进行人工调整。满足各种特殊要求是有效完成课表编排 工作重要指标，过多依赖人工调整就不能充分体现讨+ 算机排课的优越性， 尤其是智能化的特性。 1 4 专家系统设计思想的引入 通过考察排课过程可以发现，现有的一些排课系统之所以通用性差，是 因为约束条件与排课推理程序结合过于紧密。为了提高系统的通用性，必须 将二者相互分离。而且事实上，人们在排课过程中并不需要进行很多运算， 而只是凭直觉和经验，同时考虑到每个教室教师的约束条件，按照一定的分 配策略对各门课程分配上课的时间和地点。基于以上分析，最好的方法就是 将专家系统中推理机与知识库相分离的思想引入到排课系统中，即按照专家 系统的构架来设计排课系统的结构。首先把各种排课的约束条件加以整理、 消化、构成排课知识存入知识库。将初始的排课数据比如教学计划存入综合 数据库。同时建造推理程序，根据排课知识逐步安排调整排课数据，最终得 到一张实用的课程表。 1 5 论文所做的主要工作 本文通过对近年来国内外的各种有关排课文献以及各种排课方法进行 深入细致地分析综合，汲取各自的特点，以专家系统为构架，借助图论以及 线性规划中的相关理论，利用资源分配的思想对开发通用型实用排课系统进 行了积极有益的尝试。 哈尔滨工程大学硕士学位论文 第2 章专家系统简介 通过上一章的分析，本系统决定采用专家系统的基本结构作为系统的基 本框架，那么什么是专家系统呢? 在这一章中要对专家系统的基本结构和功 能进行简要的介绍。 2 1 什么是专家系统 专家系统( e x p e r ts y s t e m s ) 也称为基于知识的系统，是人工智能的 个最为重要的应用领域。专家系统产生于二十世纪六十年代中期，经过数十 年的研究已日臻成熟，其应用得到了飞速发展。专家系统的研制促进了人工 智能理论和技术的发展，开辟了计算机求解非数值问题的有效途径。 迄今为止，关于专家系统还没有一个公认的严格定义，一般认为它具有 如下特征。 ( 1 ) 是一个智能程序系统。 ( 2 ) 具有相关领域内大量的专家知识。 ( 3 ) 它能应用人工智能技术模拟人类专家求解问题的思维过程进行推 理，解决相关领域内的困难问题，并且达到领域专家的水平。 将以上几点概括起来可以说，所谓专家系统就是一种在相关领域中具有 专家水平解题能力的智能程序系统，它能运用领域专家多年积累的经验与专 门知识，模拟人类专家的思维过程，解决问题“”1 。 如何将专家的知识和经验以适当的方式存入计算机，利用类似专家的思 维方式，对原始数据进行逻辑推理、演绎、并做出判断和决策，这就是专家 系统的任务。从结构组成的角度来看，专家系统是一个由存放初始数据、中 间结果、最终结果数据的综合数据库和存放专i q 领域知识的知识库，以及 个能选择和运用知识的推理机制组成的计算机系统。 哈尔滨工程大学硕士学位论文 2 2 专家系统相对于传统程序的优点 虽然专家系统也是一个程序系统，但是专家系统与传统程序不同，其主 要区别如下。 ( 1 ) 传统程序是对数据结构以及作用于数据结构上确定算法的表示， 数据+ 算法= 程序。 而专家系统是通过运用知识进行推理，即 初始数据+ 知识+ 推理= 系统。 ( 2 ) 传统程序把关于问题求解的知识隐含于程序中，而专家系统则把 应用领域中关于问题求解的知识单独组成一个知识库。也就是说，传统程序 将其知识组织为两级，即数据级和程序级，而专家系统则将其知识组织成三 级，即数据级、知识库级和控制级。 ( 3 ) 传统程序一般是通过查找或计算来求解问题的答案，基本上是面 向数值计算和数据处理的，而且在问题求解过程中先做什么及后做什么都是 由程序规定的；而专家系统则是通过推理来求解问题的答案或证明某个假设， 本质上是面向符号处理的，其推理过程随着情况的变化而变化，具有不确定 性及灵活性。 可见，专家系统与传统程序的根本区别在于前者使知识库和运用知识的 推理机制相互独立。而传统程序通过算法对大量的数据进行积累和处理，使 繁琐的事务处理自动化。专家系统中，知识独立于推理程序，知识与推理机 制的分离为问题的求解带动来了极大的便利。当应用场合发生变化时，修改 相应知识库即可，推理机制可保持不变。从而使得系统具有很强的适应性和 灵活性。 哈尔滨工程大学硕士学位论文 2 3 专系统的功能 专家系统具备以下几个功能。 ( 1 ) 存储问题求解所需用的知识、初始数据和推理过程中涉及到的各 种信息，如中间结果、最终结果等。 ( 2 ) 根据当前输入的数据，利用己有知识，按照一定的推理策略，去 解决当前问题。 ( 3 ) 提供知识获取，机器学习以及知识库的修改、扩充和完善等维护 手段。只有这样才能更有效地提高系统的问题求解能力。 ( 4 ) 提供一种用户接口，便于分析和理解用户的各种要求和请求。 2 4 专家系统的一般结构 专家系统的一般结构以m y c l n 为代表，是基于规则的专家系统，由所 谓的产生式系统发展起来。这种结构包括知识库、推理机、综合数据库、人 机接口、解释程序以及知识获取程序。如图2 1 所示。 图21 专家系统的一般结构 其中知识库、推理机和综合数据库是目前大多数专家系统的丰要内容， 8 哈尔滨工程大学硕士学位论文 而知识获取程序、专门的人机接口是所有专家系统都期望具有的模块，但它 们并不是在所有专家系统都得到了实现。各模块的功能和作用描述如下。 1 、知识库 用以存放解决问题所需的专门知识。一个专家系统性能高低取决于知识 库的三性，可用性、确定性和完善性。因此，知识库的建立是建造专家系统 的中心任务。另外对知识如何表达也是一项非常重要的工作，这个问题目前 仍是研究的重点项目之一，正在不断发展之中。 2 、综合数据库 用于存放关于问题求解的初始数据、中间结果以及最终求解结果。综合 数据库的内容是不断变化的。在求解问题的开始时，它存放的是用户提供的 初始事实，在推理过程中它存放每一步推理所得到的结果。推理机根据数据 库的内容从知识库选择合适的知识进行推理，然后又把推出的结果存入数据 库。 3 、推理机 推理机由一组程序组成，负责整个系统的运行。它根据当前输入的数据， 利用知识库中的知识，按一定的推理策略，实现对问题的求解。 4 、知识获取程序 知识获取部分的建立，就是设计一组程序，使它具有下述功能。 ( 1 ) 能将新知识加入知识库。 ( 2 ) 根据实践结果，能发现原知识库中不合适的规则。 ( 3 ) 能删除知识库中原有的知识。 5 、解释程序。 对系统的求解过程以及系统当前的求解状态提供说明，便于用户理解系 统的求解过程及进度。 6 、人机接口。 蛤尔滨工程大学硕士学位论文 将用户的输入信息翻译为系统可接受的内部形式，把系统向用户输出的 信息转换成人类易于理解的外部形式。 2 5 本章小结 专家系统工作方式可简单地归结为运用知识进行推理。所以知识库、推 理机是专家系统的核心部分。本章主要对专家系统的结构和功能进行了简单 的介绍，着重阐述了其中知识库与推理机分离的特点，为后面排课系统的结 构设计进行了理论上的准备。 第3 章排课系统的分析 通过前面的讨论，排课系统的框架己基本形成。本章将对排课过程中可 能遇到的问题进行说明，对系统将要实现的目标和系统的要达到的性能进行 分析阐述，并对系统开发环境进行选择。 3 1 课表编排中的基本问题 在课表编排过程中将会遇到各种教务管理中常用的名词术语，不同体制 的学校可能不相同，现统一加以说明。 1 、术语含义说明 这里先将有关课程的术语做如下界定。 ( 1 ) 学时：教学活动所延续的时数。 ( 2 ) 小节：上课时间的最小单位。 ( 3 ) 教室：泛指教室、实验室和运动场地等能为教学活动提供一定空 间设备的教学设施。 2 、课表编排 课表编排任务是以“教师所任课程”的基本形式下达的，这些课程的设 置是由教学计划规定的。而课程教学的组织是根据各校实际情况，具体就落 在课表上。每一门课都给出了任课教师、上课班级、学时数以及其他一些要 求与限制。每个班都是一个固定的编制，如果一门课由几个班合上，则称为 “合班课”。 3 、约束条件 排课过程中的约束条件主要有以下五个。 ( 1 ) 在同一时间里，一个班级只能上一门课。 ( 2 ) 在同一时间里，一位教师只能在一个地点授课。 1 i 哈尔滨工程大学硕士学位论文 ( 3 ) 在同一时间里，一个班级或一个设施只能被一位教师的课所占用。 ( 4 ) 上课教室相对固定。同一门课程在一固定教室上，尽可能不变动。 ( 5 ) 选择可用教室中容量能满足上课人数的要求，而目要尽可能减少 座位空间的浪费。 此外课表编排要兼顾大量的其他约束条件，如某门课须使用某个专用教 室，否则教学无法进行。某门课不能排在某些时间内，因为教师在这些时间 另有任务等等。 以上这些约束条件是从教师、班级、课程以及教室等各个角度提出的， 它们之间有时会相互关联，难以妥善外理。因此所满足的条件与要求愈多， 课表就愈受欢迎，同时排课的时间可能也越长”。 4 、课表调整 课表编排完毕后，应能根据实际需要进行局部的微调。比如某个教师对 自己的课程安排又提出了新的要求。 3 2 排课系统目标分析 计算机排课系统应实现信息管理、课表编排、课表打印及数据统计等过 程的自动化。排课系统应能满足时间、教室和教师等各种约束条件，能解决 跨专业选课、教师跨年级跨班级任课、专业课分班上和公共课合班上等难题。 能在不影响全校总课表的前提下，加排新生课表。提供查询统计功能，便于 对课程设置情况、教师课时数和班级课时数进行统计比较，并免除课表抄写 工作等。 3 。3 系统性能要求 系统的性能将直接关系到用户对软件的满意程度，一个好的系统应该有 如下的良好性能。 哈尔滨工程大学硕士学位论文 ( 1 ) 安全可靠性 系统应准确、安全和可靠地运行，具备较强的抗误操作能力，保证数据 一致性，确保排课的顺利进行。 ( 2 ) 操作灵活性 系统具有友好的人机界面，要求简单、明了、提示性强、操作简单。系 统需要进行特别设计，以适合教学管理者使用。 ( 3 ) 通用性 在不同的教学环境和教学体制下，系统都能根据需要排出符合要求的课 表。 3 4 系统的开发环境 在系统开发过程中，需要一种负责数据库的定义、建立、操作、管理和 维护的软件系统，这就是数据库管理系统( d b m s ) 。其作用是把用户对数据的 操作转换为对系统文件的存储操作，同时把对数据库的访问，从用户级带到 概念级，再导向物理级，其职能就是有效地实现数据库三级之间的转换。对 d b m s 的选择主要考虑的问题有以下几个方面。 ( 1 ) 数据库的定义与建立 d b m s 应提供定义手段，并在保证数据的安全性与完整性的基础f 二，最终 完成数据库的建立。 ( 2 ) 数据库的操作 能接受、分析和执行用户对数据库提出的各种操作请求，完成对记录的 查询、插入、删除和修改等工作。 ( 3 ) 数据库的控制 包括控制整个数据库的运行，控制用户的并发操作，执行对数据库的安 全性完整性的检查。 哈尔滨工程大学硕士学位论文 ( 4 ) 数据库的维护 用户要求或系统设置变化时能修改和更新数据库。 ( 5 ) 故障恢复 运行期间发生故障时，应能够提供有效的工具，把故障的影响降低到最 小范围内，并保证尽快恢复。 分析现有的数据库管理系统，本系统选择了v i s u a lf o x p r o7 0 进行系 统开发。 3 5 本章小结 本章对学校的课表编排问题进行了分析，对有关排课的术语进行了界定， 对系统将要实现的目标以及系统的性能进行了阐述，并对系统的开发环境进 行了选择。 1 4 哈尔滨工程大学硕士学位论文 第4 章排课知识及其表达 知识库和推理机是本系统的核心部分，知识库中存放的是排课过程中所 要满足的各种约束条件，因此如何对这些约束条件进行有效的组织及恰当的 表达将是本章要解决的问题。 4 1 排课系统中的知识 排课系统中的知识大致可分为：时间知识、教室知识、教师知识和进度 规则知识。 1 、时间知识 该类知识用于说明各个时间段是否可以安排课。包括一般性知识和特殊 性知识。 一般性知识应是针对一般学校普遍适用的，主要有以下两条。 ( 1 ) 星期六、星期日一般不上课。 ( 2 ) 晚上一般不上课。 特殊性知识主要说明各校针对自身情况做出的规定，差异性较大。举例 如下。 下。 星期三下午不安排课。 2 、教师知识 用于说明教师对课程安排的某些要求，主要表现为特殊知识。现举例如 ( 1 ) 王强老师要求他的课不要安排在周三。 ( 2 ) 张力老师要求将她计算机一班的数学课安排在星期三上午l 、2 节。 3 、教室知识 用于说明关于某一教室的排课要求。举例如下。 1 5 哈尔滨工程大学硕士学位论文 3 0 2 教室星期五第四节不能安排课。 4 、进度规则知识 用于说明某些老师对所任课程进度方面的特殊要求。举例如下。 ( 1 ) 王芳老师要求将他三个班的语文课安排在同一天。 ( 2 ) 李芒老师要求将她计算机二班的6 节英语精读课安排在一天上完。 4 2 知识的表示 将知识表示成计算机可以接受和运用的形式，是建立知识库的关键步骤 之一。 4 2 1 排课知识的表达 通过上面的分析，将知识以如下形式进行表达和存储。 ， 1 、对于时间知识、教师知识和教室知识，无外乎两种情况。一是对于某 天某节某个老师( 或教室) 不能安排课；二是可以安排课。为此可以引入数 字0 、1 分别表示这两种状态。为每个教师、教室生成一条“0 、1 ”记录， 存入一数据文件中。 2 、对于有些教师要求将她某班某门课必须安排在指定的某天某节的强烈 要求，可以将其转化成知识存放到另一个数据文件中。 3 、对于有些老师对所任课程的某些进度要求，也可将其转化成知识存放 到一数据文件中。 综上所述，在排课之前可将收集来的各种约束条件组织成知识分别存入 知识库中的各个数据文件中。为便于排课推理模块取用知识，对各种排课知 识依其分类不同用不同的数据文件进行表达与存储。 4 2 2 各类知识文件的结构 为了将问题简化，现假设一周上三天课，每天两节课，各种知识文件结 哈尔滨工程大学硕士学位论文 构如下。 1 、时间知识文件 该文件只有一条记录，用于表示陔校上课时间，其结构如下。 字段名数据类型 说明 t 1 1 整型 t 1 2 整型 t 2 1 整型 t 2 2 整型 t 3 1整型 t 3 2 整型 时间知识文件举例如表4 1 所示。 鲞兰= ! 堕旦垫堡苎壁堂型 t l l t 1 2t 2 1t 2 2 t 3 1t 3 2 0 000 01 说明：t i j 表示星期i 第j 节，0 表示上课1 表示不上课。即该校星 期三第2 节不上课，其他时间均上课。 2 、教师知识文件 该文件记录了所有教师在各个时间段能否安排课的情况，每位教师一条 记录，其结构如下。 字段名数据类型说明 j s b m字符型 教师编码 t s m c字符型 教师名称 t 1 i 整型 1 7 哈尔滨工程大学硕士学位论文 t 1 2整型 t 2 1整型 t 2 2整型 t 3 1整型 t 3 2整型 教师知识文件举例如表4 2 所示。 表4 2 教师知识文件举例 说明：j s b m 为教师编码，j s m c 为教师名称。即张力老师星期二第一 节不能安排课，王强老师星期二第二节不能安排课。 3 、教室知识文件 该文件记录了所有教室在各个时间段能否安排课的情况，每个教室一条 记录，其结构如下。 数据类型 字符型 字符型 整型 整型 整型 整型 说明 教室编码 教室名称 m c 名肿 洲 。o，o 锻删脚n n 他他 宇 哈尔滨工程大学硕士学位论文 t 3 1整型 t 3 2整型 教室知识文件举例如表4 ，3 所示。 表4 3 教室知识文件举例 说明：j s h i b m 为教室编码，j s h i m c 为教室名称。本例即3 0 1 教室星 期二第节不能安排课，3 0 2 教室星期二第二节不能安排课。 4 、指定课知识文件 该文件记录了这样一些教师，他们要将自己的课程安排到指定的某天某 节，其结构如下。 字段名数据类型说明 j s b m字符型 教师编码 j s m c字符型 教师名称 b j b m字符型 班级编码 b j m c字符型 班级名称 k c字符型 课程名称 x q整型星期 j s整型 节次 指定课知识文件举例如表4 4 所示。 哈尔滨工程大学硕士学位论文 表4 4 指定课知识文件举例 本例为张力老师要求将计一班的系统结构课安排到星期三第1 节，王强 老师要求将计二班的图形学课安排到星期二第2 节。 5 、进度知识文件 进度知识文件记录了某些教师对课程进度的特殊要求，结构如下。 字段名数据类型说明 j s b m字符型教师编码 j s m c字符型教师名称 b j l字符型班级数l b j 2字符型班级数2 b j 3字符型班级数3 b j 4字符型班级数4 进度知识文件举例，假设教师任课情况如表4 5 所示。 表4 5 教师任课情况表 张力计1 计2 计3 电l 高数 高数 高数 数值分析 2 课时 2 课时 2 课时 2 课时 2 0 晗尔滨工程大学硕士学位论文 电2 数值分析2 课时 王强计l 高代2 课时 计2 高代2 课时 电1 随机过程2 课时 电2 随机过程2 课时 则相应进度知识文件如表4 6 所示。 表4 , 6 进度知识文件举例 说明：本例为张力老师计1 、2 、3 班的高数要在同一天上，电1 、2 班 的数值分析同一天上。王强老师计1 、2 班的高代要在同一天上，电1 、2 班 的随机过程要同一天上。 4 。3 本章小结 本章给出了在排课系统中所要使用的知识，并就知识的表达进行了探讨， 最终确定将知识存储于数据表中，以记录的形式进行表示，并给出了各类知 识表的结构，从而构造了整个系统的知识库。 哈尔滨工程大学硕士学位论文 第5 章综合数据库 排课系统综合数据库包括作为排课事实数据的班级、课程、教室和教师 等初始信息，也包括作为排课系统输出的课表数据及其它辅助数据，本章将 对其进行设计和规划。 5 1 设计原则 数据库的设计即数据的内容和组织方式，是系统开发实现的关键。在设 计数据库的时候，要明确数据库要完成的任务和功能，针对这些功能建立模 型，即模型化。而后，就需要考虑应当在数据库中存放哪些数据，将数据组 织成表和关系，并为数据表建立索引和设置有效性规则。如果需要再创建必 要的查询，这样就完成了数据库的设计。好的数据库结构对保证系统的顺利 运行有着重要的意义。 在排课系统数据库设计过程中，主要考虑以下问题。 ( 1 ) 符合排课过程的需要。能正确反映教学管理的实际环境，包括排课过 程所需要的所有数据，并且支持排课过程的所有操作。 ( 2 ) 有利于数据库系统的实现。 ( 3 ) 具有良好的结构，易于维护，易于理解，效率较高。 ( 4 ) 尽可能减少数据冗余。 ( 5 ) 与其他系统有较好的兼容性。 5 2 综合数据库规划 排课系统综合数据库包括作为排课事实数据的班级，教室和教师等初始 信息，也包括排课过程的中间结果、辅助数据以及作为排课系统输出的课表 数据。所以在本系统中涉及的数据库有三类。 2 2 哈尔滨工程大学硕士学位论文 ( 1 ) 基本情况数据库 教师数据文件 班级数据文件 教室数据文件 课程数据文件 ( 2 ) 教学计划数据库 合班课教学计划文件 体育课教学计划文件 普通课教学计划文件 ( 3 ) 课表数据库 班级课程表文件 教师课程表文件 教室课程表文件 5 3 综合数据库简介 排课系统综合数据库中各数据文件的结构和功能如下。 1 、班级数据文件 功能为存储全校的班级信息，其结构如下。 字段名数据类型说明 b j b m字符型 班级编码 b j m c字符型班级名称 r s 数值型人数 z k s l整型 总课时量 数据来源：由教务人员在每学期排课前录入。 2 、教师数据文件 2 3 哈尔滨工程大学硕士学位论文 功能为存储全校的教师信息，结构如下。 字段名数据类型说明 j s b m字符型教师编码 j s m c字符型教师名称 数据来源：由教务人员在每学期排课前录入。 3 、教室数据文件 功能为存储全校的教室信息，其结构如下。 字段名数据类型说明 j s h i b m整型教室编码 j s h i m c字符型教室名称 k r r s 数值型可容人数 k z k s 数值型可占用课时 w z k s数值型 未占用课时 数据来源：由教务人员在每学期排课前录入。 4 、课程数据文件 功能为存储全校所开课程的信息，其结构如下。 字段名称数据类型说明 k c b m 字符型课程编码 k c m c 字符型课程名称 数据来源：由教务人员在每学期排课前录入。 5 、合班课教学计划文件 功能为存储全校的合班课教学计划，其结构如下。 字段名称数据类型说明 j s b m字符型教师编码 j s m c字符型教师名称 堕叠鎏三矍盔堂堡主堂垡堡壅 ： b j b m l字符型班级编码1 b j m c l字符型班级名称1 b j b m 2字符型班级编码2 b j m c 2字符型班级名称2 r j b m 3字符型班级编码3 b j m c 3字符型班级名称3 b j b m 4字符型班级编码4 b j m c 4字符型班级名称4 k c 字符型课程 k s 数值型课时 z d j s h i字符型指定的教室 数据来源：由教务人员在每学期排课前录入。 6 、体育专选课教学计划文件 功能为存储全校的体育专选课计划表，其结构如下。 字段名称数据类型说明 j s b m字符型教师编码 j s m c字符型教师名称 b j b m l字符型班级编码l b j m c l字符型班级名称l b j b m 2字符型班级编码2 b j m c 2字符型班级名称2 b j b m 3字符型班级编码3 b j m c 3字符型班级名称3 b j b m 4字符型班级编码4 b n c 4字符型 班级名称4 哈尔滨工程大学硕士学位论文 k c字符型课程 k s数值型课时 数据来源：由教务人员在每学期排课前录入。 7 、普通课教学计划文件 功能为存储全校的普通课教学计划，其结构如下。 字段名称数据类型说明 j s b m字符型教师编码 j s m c字符型教师名称 b j b n字符型班级编码 b j m c字符型班级名称 k c字符型课程 k s数值型课时 数据来源：由教务人员在每学期排课前录入。 8 、班级课程表文件 功能为存储全校的各个班级课程表，包括每节上课的教师、教室和课程 信息，其结构如下。 字段名称 b j b m b j m c x 1 l j 1 l r 1 1 x 1 2 j 1 2 r 1 2 数据类型 字符型 字符型 字符型 字符型 字符型 字符型 字符型 字符型 说明 班级编码 班级名称 星期一第 星期一第 星期一第 星期一第 星期一第 星期一第 节课程名 节教师名 节教室名 节课程名 节教师名 节教室名 堕叠鎏三婆丕兰堡圭兰丝笙茎 x 5 4 字符型星期五第4 节课程名 1 5 4字符型星期五第4 节教师名 r 5 4字符型 星期五第4 节教室名 数据来源：表结构由系统初始化时自动生成，记录由排课系统经过推理 自动生成。 9 、教师课程表文件 功能为存储全校的每位老师课程表，包括每节上课的班级、教室和课程 信息，其结构如下。 字段名称 j s b m j s m c x l l b 1 l r 1 l x 1 2 b 1 2 r 1 2 数据类型说明 字符型教师编码 字符型教师名称 字符型星期一第1 节课程名 字符型星期一第1 节班级名 字符型星期一第1 节教室名 字符型星期一第2 节课程名 字符型星期一第2 节班级名 字符型星期一第2 节教室名 x 5 4 字符型星期五第4 节课程名 b 5 4 字符型星期五第4 节班级名 r 5 4 字符型星期五第4 节教室名 数据来源：表结构由系统初始化时自动牛成，记录由排课系统经过推理 自动生成。 1 0 、教室课程表文件 哈尔滨工程大学硕士学位论文 功能为存储全校的每个教室课程表，包括每节上课的班级、教师和课程 信息，其结构如下。 字段名称数据类型说明 i s h i b m字符型教室编码 j s h i m c字符型教室名称 x 1 1 字符型星期一第1 节课程名 b 1 1字符型 星期一第1 节班级名 j 1 1字符型 星期一第1 节教师名 x 1 2 字符型星期一第2 节课程名 1 3 1 2 字符型星期一第2 节班级名 j 1 2字符型星期一第z 节教师名 x 5 4 字符型星期五第4 节课程名 b 5 4 字符型星期五第4 节班级名 j 5 4字符型 星期五第4 节教师名 数据来源：表结构由系统初始化时自动生成，记录由排课系统经过推理 自动生成。 5 4 本章小结 本章就排课系统综合数据库的设计进行了讨论，并就其所需要的各种初 始数据、中间结果以及最终结果数据的存储和表示进行了阐述。 哈尔滨工程大学硕士学位论文 第6 章排课系统中的推理机制 推理机是排课系统中最为重要的部分，它