（教育经济与管理专业论文）基于数学模型的计算机排课系统算法研究与分析.pdf

中文摘要 随着我国教育事业的蓬勃发展，计算机已经成为学校教学、管理中不可或缺的 一部分，软件越来越多的应用在学校的各个方面，如学籍管理、成绩管理、物资管 理等等。近年来，许多高职院校都希望能够把排课这个复杂而又繁琐的工作交给计 算机来完成，但一直缺乏一种快速、合理的算法来解决这个问题。 排课需要考虑时间、课程、教学区域、教室、院系、班级、教师等等因素。经 过优化的排课，可以在任意一段时间内，教师不冲突，授课不冲突，授课的班级不 冲突，教室占用不冲突，且综合衡量全校课表在宏观上是合理的。本文进行了排课 需求分析并阐述了系统的整体机构及实现方案，根据人工排课的要求，设计了基于 优先级的自动排课算法。文中详细介绍了排课算法的设计与实现、数据库的设计与 实现。在时问选择的灵活性、优先级的计算、等价类的划分、算法复杂性的降低等 等方面提出了自己的见解。将面向对象技术应用于排课系统，讨论了排课实现过程 及关键算法，分析了冲突产生的原因，给出了问题解决方案及实验分析结论。阐述 了采用微机排课的用户需求，提出了一种依据教学计划，由微机自动排序各学期课 程的设计方案，并对教学计划生成的算法进行了描述。 关键字：计算机自动排课、排课算法、优先级、等价类、时间模式 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fo u re d u c a t i o n a lc a u s e ，c o m p u t e rh a sb e c o m ea l l e x t r e m e l yi n d i s p e n s a b l ep a r to fc o l l e g ee d u c a t i o na n dm a n a g e m e n t ；s o f t w a r eh a sb e e no f m o r ea n dm o r e a p p l i c a t i o n i nd i f f e r e n t a s p e c t o f c o l l e g e ，s u c h a ss t u d e n t m a n a g e m e n t ，g r a d em a n a g e m e n ta n dm a t e r i a l lm a n a g e m e n te t c ，f o rm a n yy e a r s ，m o r ea n d m o r ec o l l e g e sh o l dt h eh o p eo fb e i n ga b l et og i v et ot h ec o m p u t e rt h ec u r r i c u l u ms c h e d u l e n o to n t yc o m p l i c a t e db u ta l s ot e d i o u s ，u n f o r t u n a t e l yl a c k i n go faf a s ta n dr e a s o n a b l e m e t h o dt os o l v et h i sq u e s t i o n t oa r r a n g et h ec u r r i c u l u mn e e d sd i f f e r e n tf a c t o r st oc o n s i d e r ：t i m e ，c o u r s e s ，t e a c h i n g a r e a ，c l a s s r o o m se t c t h ep r o p e rc o u r s e a r r a n g e m e n tt a k e sf u l la d v a n t a g eo ft e a c h i n g s t a f f s ，c l a s sg i v i n g , c l a s s r o o mo c c u p y i n g ，m a k i n gt h e mn oc o n f l i c t s ，a n da l s o i ti s r e a s o n a b l et oe v a l u a t et h ec o l l e g ec l a s st i m e t a b l eg e n e r a l l ya n dc o m p r e h e n s i v e l y i nt h e p a p e r ，if o c u s e do nt h er e q u i r e m e n ta n a l y s i si n c o u r s es c h e d u l i n g ，t h es y s t e m so v e r - a l l s t r u c t u r ea n di t si m p l e m e n t a t i o n t h i sp a p e rp r e s e n t e dt h ea l g o r i t h mb a s e do np r i o r i t y ， i n t r o d u c e dt h ed e s i g na n di m p l e m e n to ft h es y s t e m ，t h ed e s i g na n di m p l e m e n to fb a s e ， a n dt h ed e s i g no fq u e r ya n dr e p o r ti nd e t a i l t h ep a p e rs h o w e ds o m eo r i g i n a l i t yi nf l e x i b l e s e t t i n go ft i m em o d e ，t h ec a l c u l a t i o no fp r i o r i t y ，t h ep o r t i o n i n go fe q u i v a l e n te t c a p p l y t h eo b j e c t o r i e n t e dt e c h n o l o g yt ot h el e s s o n a r r a n g e m e n ts y s t e m i td i s c u s s e dt h ec o u r s e a n dk e ya l g o r i t h mi nl e s s o n a r r a n g e m e n t ，a n a l y s e st h er e a s o nw h yt h ec o n f i n ee m e r g e s a n dp r e s e n t st h es o l u t i o na n de x p e r i m e n t a la n a l y s i sc o n c l u s i o nt ot h ec o n f l i c t u s e r r e q u i r e m e n t so ft h es y s t e mo fa u t o a r r a n g i n gc u r r i c u l aa r ed e s c r i b e d d e s i g np l a n sa b o u t a u t os e l e c t e ds u b j e c t s ，t e a c h e r s ，c l a s s r o o m sa n dt e a c h i n gt i m ea r ep o i n t e do u t k e yw o r d s ：a u t o m a t i cc o u r s es c h e d u l i n g ； a l g o r i t h m ； p r i o r i t y ； e q u i v a l e n t ； t i m em o d e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得叁盎盘堂或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 学位论文作者虢私签字嗍胛旧厂日 学位论文版权使用授权书 本学位论文作者完全了解鑫洼盘堂有关保留、使用学位论文的规定。特 授权盘壅盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检索，并 采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有 关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名导师签名 签字f 1 期：弘矽产f 月r 同 签字同期 第一章绪论 1 1 排课系统的研究动态 第一章绪论 排课是学校教学管理中一项重要而复杂的基本工作，其实质就是为学校所 设置的课程安排一组适当的教学时间与空间，从而使整个教学能够有计划有秩 序地进行。由于具有规模大、约束( 要求) 复杂以及本质不断变化等特点，使 得课表问题成为令人感兴趣的课题之一。 2 0 世纪5 0 年代来、6 0 年代初，国外就有人开始对课程表问题进行了研究。 直到1 9 7 5 年以前的一段时间罩，人们主要从构造算法模型入手，研究其解决方 法，目的是找到一个解决问题的有效算法。1 9 6 2 年，g o t l i e b 提出了一个构造课 程表的数学模型，接着人们对这个模型算法、解的存在性等问题作了许多探索， 并提出过一些新的算法模型，但始终未能找出一个有效算法。1 9 7 5 年，e v e n 等 人在美国s t a mj ，c o m p u t 上发表类的“o nt h ec o m p l e x i t yo ft i m e t a b l ea n d m u l t i c o m m o d i t yf l o wp r o b l e m 证明了课表问题是一个n p 完全类问题。它的论述 确立了课表编排问题的学术地位，把人们对计算机编排课表的复杂性的认识提 高到了理论的高度。这类问题的求解是典型的时间表与多物流的决策问题的求 解。用计算机解决这个人文决策问题，从数学角度建立模型，研究设计一种计 算机算法的尝试都未能获得满意结果。因此，人们寻求有效算法的探索才告一 段落，而将更多的精力转移到如何借助计算机这一现代化工具束实现自动编排 实际课程表这个问题上。 近4 0 年来，人们对课表问题的计算机解决法做了许多尝试。其中，课表编 排整数规划模型将问题归结为一组o - 1 变量的解，但是其计算量非常大。解决 0 - 1 线性优化问题的分支一一定界技术却只适用于舰模较小的课表编排，m i h o c 和b a l a s 将课表公式化为一个优化问题，k r a w c z k 则提出一种线性编程的方法。 j u n g i n g e r 将课表问题简化为三维运输问题，而t r i p a t h y 则把课表问题视作整数 线性编程问题并提出了大学课表的数学模型。 此外，有些文献试图从图论的角度来求解课表问题，但是图的染色体问题 也是n p 完全问题，只有在极为简单的情况下j 可以将课表编排转化为二部图匹 配问题。这样的数学模型与实际相差太远，所以对于大多数学校的课表编排问 题来说没有实用的价值。 进入2 0 世纪9 0 年代以后，国外对课表问题的研究仍十分活跃。比较有代 第一章绪论 表性的有印度的v 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 n a u b i n 和j a c q u e sf e r l a n d 等。目前，解决课表问题的方法有：模拟手 工排课法、图论方法、拉格朗h 松弛法、二次分自a 型法等多种方法。山于课表 约束复杂，用数学方法进行问题描述时往往导致问题规模剧烈增大，这已经成 为应用数学编程解决课表问题的巨大障碍。国外的研究表明，解决大规模课表 编排口j 题单纯靠数学方法是行不通的，而利用运筹学中分层规划的思想将问题 分解，将是一个有希望得到成功的办法。 在国内，对课表问题的研究始于卸世纪8 0 年代初期，具有代表性的有： 南京工学院的u t s s f 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 h n e t a b l es c h e d u l e r ) 系统，大连弹工大学的智能教学组织管理与课程调度 系统等。这些系统大都是模拟手工排课过程，以“班”为单位，运用启发式函 数来进行编排的。这些课表编排系统杵往依赖于各个学校的教学体制，不宜进 行大量的推广。正如华东交通大学的郑晓芳教授在校学报中排课管理系统的 设讣中所述：“通过实践我们发现不同的学校，管理政策不同，其教务管理软 件很难实现真正意义上的通用，各高校应针对自己的情况开发出适合自己的应 用软件。”可见排课系统再怎样完善也很难满足各个学校的不同的教学体制的要 求。 高职教育在培养目标和办学模式、教学方式等方面都有别于传统学科式教 育。遵循理论“必需”、“够用”为度，理论为实践服务的原则，着重培养学生 的实践能力，培养面向生产、建设、管理及服务一线的高等技术应用型人才。 由于培养目标和培养方式的特点，决定了高职教育的教务工作而临许多新的困 难，其中排课、调课、检查教学进度、质量、沟通教学双方信息等常规性1 二作 中问题尤为突出。如何利用有限的师资力量和有限的教室资源，排出 个合理 的谋表，对维护高职院校正常的教学秩序和提高教学效果有重要的作用。高职 院校应从自己的实际情况出发，开发出适合自己的排课系统。 1 2 高职课表编排若干问题的思考 随着高职院校办学规模的不断扩大，办学层次的不断提高，高职院校课程 表编排管理工作也显得越来越重要，学校要做好这项工作，关键要遵循科学的 排课原则，采取有效的管理办法，实现课表编排现代化。 排课原则，采取有效的管理办法，实现课表编排现代化。 第一章绪论 1 2 1 确立高职课程表编排原则 编排课程表即要涉及到“活动”的要素一一任课教师和丌课对象学生，又 要涉及到“固定”的要素一一课程和教室等场地或设备。这“活动”的和“固 定”的要素相互交织在一起，给排课问题带来了复杂化，给工作带来了许多困 难。要处理好这个问题，首先要确立一套科学的排课原则。 1 有利于充分利用教学设备和条件的原则 设计排课系统的算法具有一定的复杂性，设计教师、教室班级、课程和时 间等信息对象，算法目标是为满足需求( 如班级、课程等) 进行合理资源( 如 教室、教师和时间等) 分配，核心问题是避免资源冲突。 在学校的教学工作中，有些课程需要共同使用学校的场地、设备、器材、 实验室、电化教室等。如公共体育课需要用到操场、体操房、体育器材等，理 科需要用到实验室、文科需要用到语音电化教室等。在排课中必须根据实际情 况给予科学的安排、周密的考虑，以提高设备的使用效率。规模较大的高职院 校，教师一般采用“穿插使用”的办法，这些学校许多课程如公共课是跨系、 跨专业进行的，一个班级没有固定的上课教室，一门课程或许是几个班级的学 生坐在一起，而另一门课程却在其它教室罩上，象这样不时地变换上课地点的 课程，排课是要避免“撞车”现象的发生。特别是近年来，随着各校招生规模 的不断扩大，学校教学设备和条件普遍吃紧的情况下，更要合理安排和充分利 用好现有教学条件和设备，避免“撞车”现象或闲置。 2 科学的制定教学计划，保证课程顺利丌设原则 教学计划是学校教育、教学的指导性文件，是编排课程表的唯一依据。它 根据学生的身心发展规律，按照教育原则和培养目标，根据学科的内在必然联 系，合理的、科学的、有序的编订了每学期要丌设的课程。课堂教学是按固定 的课程表迸行的，课程表是学校全面贯彻党的教育方针，培养具有一定觌格的 大学生的具体反映。它应该按照教育学和教育心理学的原理科学的将教学计划 固定下来，并通过教学活动不断的得到实施和完成的。 而且根据高职学校的教学特点，教学计划要求满足以下几点： ( 1 ) 既要有便于执行的相对的稳定性，又要顺应职业社会需求的发展变化甚 至要有超前意识： ( 2 ) 既要明确理论教学的任务，又耍规范技能训练的标准； ( 3 ) 对于“复合型”专业，还要注意跨学科的各门课程之间的联系与衔接， 甚至先后顺序、深浅程度、课刊比例都要反复向有关专家征询。 在编排课程表时，一定要严格按照教学计划制定，保证课程顺利丌设，不 第一章绪论 要随意改变或停丌某一课程。 3 体现“以人为本”的原则 全校教师在教学活动中，应团结、协作和谦让，体现“以人为本”的原则， 尽可能的考虑学生的发展和教师本人的利益，创造一个和谐的工作坏境。 ( 1 ) 年轻教师刚参加工作，只是具备一定的理论基础，在实践技能方面还有 待于向有经验的教师学习请教。因此每天的课时，年轻力壮的教师可以集中安 排，便于集中时间去学习，年老体弱的教师分散编排，以利于劳逸结合，不影 响身体和教学效果。新老教师同时上课时，尽量把老教师安排在前面，新教师 安排在后面，“以老带新”，让新教师先听后讲有学习的机会。 ( 2 ) 要想提高学校的教学水平，必须先提高教师素质。从建院起，院领导就 把“双师型”作为严格要求教师的标准，尽可能提供职业实践的机会，大力支 持教师考证兼职，我院第一个考取职业资格证的教师己有四十五岁，在相关政 策的支持和老教师的带动下，全院的教师都行动起来，报考在职研究生的人数 年年倍增。因此，在编排课程表时要充分考虑任课教师的教学与科研活动。要 适当集中安排任课教师的课时，让他们有一个相对集中的时间去学习、搞科研， 也给教师有充分休息和备课时间。但不要在一天或连续二天内安排很多课时， 以防过度疲劳，影响教学效果和教师健康。 ( 3 ) 对家住校外的教师、身体健康状况不良的教师和家庭需要照顾的教师， 安排课程时应尽可能的给予照顾，尽量不要安排在上午1 2 节课。 ( 4 ) 同一学科中新老教师的课应不在同一节课中安排，如果教师外出参加活 动，便于安排代课。 4 有利于提高学生学习效率的原则 学生是学校教育的主体，教学的目的就是要让受教育者接受知识，理解和 掌握知识，发展学生的认识能力和体力，培养学生的世界观和道德品质。高职 院校不同于中、小学，其课程多，性质区别大。有的侧重逻辑演绎，有的侧重 抽象思维，有的偏重记忆，有的只要阅读和理解，还有的是体能、劳动技能课、 实验课、实践课等。面对众多不同性质的课程，如何根据学生的心理特点和身 心健康发展规律合理编排课程，提高学习效益，是值得我们研究的课题。 从心理学角度分析，大学生大脑已经发育成熟，接受新事物、学习新知识 的能力远比中小学生强，克服“前摄抑制”和“倒摄抑制”的能力也比较强， 而且“负迁移”效应相对减弱。针对学生的这种优势，只要对众多性质不同的 课程实行优化组合，就能有效地提高学习效率。则需要处理好以下几方面： ( 1 ) 可以编排两节连堂课，但至多不要超过三节。安排两节连章课，一方面 第一章绪论 前拳课的教学内容对后堂课的学习会产生“正迁移”的作用，有利于提高学习 效果。另一方面有利于大学教学内容的合理安排，让一些理论知识和观点得到 连贯的较全面的阐述。 ( 2 ) 一门课程连排在三节以上的方法不可取，由于连续排课三节以上的课程 其先后材料性质相同，刺激也相同，学生容易产生疲劳，容易产生“倒摄抑制” 和较大的“负迁移”效应，影响学习效果。 ( 3 ) 学习难度较大或主干课程应当安排在学生和教师精力最旺盛的时间。一 般讲，每天上午是最佳黄金时阳j ，学生和教师精力充沛，大脑清醒，不易产生 “前摄抑制”现象，适宜安排难度较大或主干课程。每天下午和晚上学生容易 疲劳，精力易分散，适宜安排各种活动课程和易理解的课程，如实验、体育、 选修课等课程。 ( 4 ) 不同性质不同层次的课程适当搭配、交错编排。高校需要丌设多类课程， 这些课程性质不同，层次也不尽相同，在排课时要尽量做到“适当搭配、交错 编排”，以减少“负迁移”效应。如文科和理科、公共课和专业课、形象思维为 主和抽象思维为主的课程以及作业多和作业少的课程要适当搭配，交叉混排， 不要偏于同一天或连续几天都排同一性质同一类型的课程。 ( 5 ) 实验课与理论课的编排，最好先上理论课，后紧接着实验课，时问隔的 不要太长。高职学校由于注重技能实践教育，因此排课时不要将体育、劳动技 术等体能课程安排在同一天，体育课尽量安排在下午。 1 2 ，2 加强学校课程表编排管理 加强学校课程表编排管理，确保教学工作良好运转。高校排课主要涉及到 课程、任课教师、丌课对象以及教室等场地或设备四方面的因素。学校在组织 实施的过程中，如果要让这四要素有机的结合起来，进入最佳运行状态，发挥 最大的效能，以保证课程表的合理性、科学性、及时性和正确性，保证课程设 置符合教育规律和培养目标，保证教学工作良好运转，学校除了必须遵循高校 排课原则外，还必须要建立一套较为完善的管理办法。 1 建立一支稳定的高素质的课程编排管理队伍。一般学校教务部门和二级 系部都要配有专人负责课程表的编排工作，并且教务部门和二级系部严把审核、 检查关。专职工作人员必须具备大专以上水平，懂得教育心理学，掌握教育规 律，熟悉教学计划，了解各门课程的性质和层次，具有很强的事业心和高度的 责任感。 2 在排课的组织实施过程中，公共课程和专业课程实行校院两级管理，有 第一章绪论 利于学校对整个教学的宏观管理和调控，有利于各院发挥主人翁的念度，也有 利于任课教师提前做好备课，统筹安排其他各项工作。全校公共课由教务部门 统一编排和管理，专业课程出各院负责落实。一般课程表编排工作于学期结束 前一个月开始，先由教务部门根据实际情况提出具体要求与编排办法，并根据 教学计划确定公共课程教学任务意向书出各系院确定师资后，再根据有关编排 原则排定公共课程，确定全校性政治劳动、教研活动等事件，这样，全校公共 课程表已基本排定。然后，各院系根据学校已经排好的框架，按教学计划要求 逐一排好各门专业课程。最后，经教务处综合审查后，及时把课程表印发给每 位任课教师。 3 要及时处理上课试行阶段出现的种种问题。丌学第一周是上课试行阶段， 学校、系领导应当予以高度重视，要组织力量做好前期检查和协调工作；学校、 院系两缴工作人员必须要认真对待，及时处理试运行过程中出现的种种问题， 任课教师要提前下班级、下教室了解丌课情况，如有冲突等问题，一方面要及 时报教务部门、系室有关负责人，另一方面要给予支持和理解，防止问题扩大 化。第二周丌始上课正常运转后，教务部门要编印全校任课教师一览表、全 校教室使用情况一览表等以便学校检查存档。 4 健全管理制度，加强只常教学秩序检查，杜绝随意调课、停课现象。课 程表已经编排完毕，上课已经进行，这并不意味着管理工作已告结束，恰恰相 反，在课程表的执行过程中时常会出现擅自调课、停课、上课迟到、早退等现 象。因此，必须要加强日常教学秩序检查与管理，建立临时调课、停课申请制 度，健全和完善教学事故处理办法，杜绝随意调课、停课、拒不执行教学计划、 不按教育规律办事的现象，以保持课程表的相对稳定性和严肃性。 5 将计算机排课与教室管理、教学计划管理结合起来。计算机排课与教室 管理、教学计划管理具有密切关系，它们可为计算机排课提供必需的基础数据， 即教室使用情况和下学期丌课情况等。因此可以直接通过教室管理及教学计划 管理系统产生排课所需基础数掘，从而大大减少计算机排课时基础数据输入的 工作量。 】3 计算机编排课表的逻辑模型 1 3 1 人工排课操作的基本模型 人工排课操作的基本模型如图1 1 所示 第章绪论 图卜1 人工排课系统的基本模型 图中：o ：信息处理口：处理生成信息集：输入输出信息集 各步处理和每个信息集描述如下： 1 教学部门从各专业教学计划中抽取本学期各专业的教学课程及其有关信 息，汇总编排各专业的课程设置及学时安排表( 如表1 1 所示) 。 表1 1课程设置表 课程名称课榉性质课时总数( 周数周课时)上课周的分布( 起l r 周) 2 各教研室按课程设置表安排任课教师，填报教师任课安排表一一选课表， 如表1 2 所示： 第一章绪论 表1 - 2选课表 课样名称上课班级课程性质课时总数( 周数周课时)任课教师特殊要求 3 教务部1 3 t ：- i i ；课，输出课程表：包括班级课表、教师任课表、教室课表和 课程总表。 1 3 2 计算机编排课表的逻辑模型 计算机排课软件系统的设计应从计算机处理问题的特点出发，既考虑计算 机所解决问题的需要，又要充分发挥计算机的特点和优势，使计算机处理问题 的方法更加科学化。计算机排课主要应有以下几个方面： 1 建立信息代码体系，建立便于计算机操作的信息代码体系，这不仅是为 了便于操作，提高计算机操作的准确度，也是科学的教务信息管理所必须的。 2 合理分配计算机的求解域，人工排课的全部操作，都可由计算机完成， 但并不是所有的步骤出计算机完成都能提高效率和水平。对于各班各门课程的 任课教师的安排，包含诸多的人的主观意志，而人的脑力劳动含量较少，人工 操作更具优势。用计算机操作却需要输入大量的有关信息，费时费力。此时， 将整个排课分为三步，第一步由计算机编排课程设置表，第二步人工填报教师 任课表，第三步计算机编排课程上课时问表( 简称课程课时表) 。 3 调整信息流及数据结构，对人工操作的表格形式和数据内容进行调整， 以便于计算机的操作，如下表1 3 和1 - 4 所示： 表卜3课程设置表 学期课程名称课科性质课时总数( 周数 周课时)上课周的分布( 起i r 周) 第一章绪论 表1 - 4教师任课表 课程代号班级代号教师代号课程性质周学时数起始周终i f j 周特殊要求 在编排课程课时表过程中，先排班级与教师的时间表，再排教室。而一次 操作人工难以完成。这样操作在教室足够多的情况下可充分完成。在教室资源 比较紧张的情况下，往往仅为能排出教室，也要反复调整教师与班级的课时表。 难以实现最佳的教室编排。计算机解决问题不受信息品种和等级、数量的限制。 将班级、教师、教室课表同步编排，可提高教室利用的优度。 系统逻辑模型说明系统的功能组成及信息流，表示如图1 3 ，各信息集的信 息项构成在系统详细设计中说明。 图中：么二7 ：输入输出信息集：厂 ：存储信息集( 文 件) ：( ) ：人工加工处理；l i ：机器加工处理； 业教学计划- 叫教学计划编辑卜+ i 教学计划r _ ：j 议程砹汁安排 班级谍程j j ! i 程敦师任谍表 互寸卜z 玺垂三7 f 青息编辑抖面救帅俯息玑级仿息教室俯息 教学进度 。_ 。_ - _ - _ _ _ t 荔瓦飞 厩 信息编辑界面 课程信息ll 毅帅信息i1 班级f 膏息 课程课时表编排 代码衍息 教室信息li 代蚂信息 = = = 乙三一 翮 垫奎堡查if 教帅淋表l、茎兰堡壁卜1 至竺竺丝 议程打印，。瑚r 夕种赋脚动2 盘础世者1 教帅龇时 卜2 计算机编排课程表的逻辑模型 第一章绪论 1 4 本系统的引用意义 随着教学改革的进行，新的教育体制对课表的编排提出了更高的要求。手 工排课时，信息的上通下达是极其麻烦的，而采用计算机排课，教学中的信息 可以一目了然，对于优化学生的学习进程，评估每位教师对教学的贡献，领导 合理决策等都具有重要的意义，必将会大大推动教学的良性循环。 本课题根据高职高专院校的教学体制的特点，分析了排课问题的数学模型， 设计了一种基于优先级的自动排课算法，该算法通过划分等价类、计算优先级 等方法大大降低了课程调度的算法复杂性，从而可以以较快的速度获得较为满 意的排课结果。同时，在设计算法的过程中也非常注意其冲突的解决。 0 第二章排课系统分析 第二章排课系统分析 2 1 课表编排的基本问题 1 基本概念 ( 1 ) 学时教学活动所延续的小时数。 ( 2 ) 小节上课时间的最小单位。 ( 3 ) 教室泛指教室、实验室、机房、运动场地、电化教室等能为教学活动 提供一定空间等设备的教学设施。 ( 4 ) 自然班级由同一年级、同一专业、按同一教学计划培养的一定数量的 学生组成的，便于管理和课外活动的学生集体。对学生较多的专业，一般分为 多个自然班级。 ( 5 ) 教学班级在相同时间、相同教室学习，山相同教师讲授同一门课程的 一定数量的学生组成，便于教学和课堂活动的学生集体。在多个教师任同一门 课程，或一门课程开设多个班级时，按课程和任课教师将学生分配到多个教学 班级( 必修课可以在排课前确定教学学生分班情况，选修课教学班级分班情况 在选课完成后才能确定) 。教学班级学生来自不同院系时，称为混和教学班级。 ( 6 ) 教学类型与完成一门课程的全部教学任务相关的各个相对独立的教学 环节，如主讲、实验、习题等。一门课程一般涉及多个教学类型。 2 课表编排任务 课表编排任务是以“课”的基本形式下达的，这些课程的设置是由教学计 划规定的，而课程教学的组织是根掘各校实际情况，具体就落在课表上。每一 门课都给出了任课教师、上课班级、学时数以及其他一些要求与限制。每个班 都是个固定的编制，如果一门课有几个班合上，则称为“合班课”。 3 学期安排 每个学年有两个f 规学期，每学期约2 0 个教学周，以各教学周上5 天课， 若每天按6 小节排课，如果扣除一个下午为集体活动时间，则每周至多能排2 8 学时。通常要求课都排在白天前四个小节来上。 2 2 需求分析 本课题的主要内容就是使用计算机实现课表的编排、基础数据的处理、课 第一章排课系统分析 表的查询和报表的输出等多种功能，作为一个完整的应用系统，主要涉及以下 需求： 1 基础数据的处理 排课过程中涉及到许多基础数据，这些基础数据包括院系、教师、学生、 教室、课程等信息，对于这些基础信息要能够根据实际情况灵活进行增加、删 除、修改等处理。 2 排课处理 课程的编排不是任意的，它是个时间、教师、学生、教室四者的组合规 划问题，为了达到最好的教学效果应遵循一定的要求。这些要求主要有： ( 1 ) 要尽量为所排课程安排上该类课程效果最好的时| 、日j ； ( 2 ) 课程在一周上多次时要有一定的时间间隔； ( 3 ) 公共课等涉及面广、学时多的课程应优先处理； ( 4 ) 对同一教师，同一上课对象应尽量选择相对固定的几个教室； ( 5 ) 对于教师、学生、课程等提出特殊要求的情况，要根据具体情况予以处 理。例如：有送小孩的教师不安排在上午1 2 节课；年龄大的教师不宣安排在上 午1 2 节课：有外出指导实习任务的教师和班级要在一学期的指定时问结束本学 期的课堂教学计划；某位教师临时增加了教学任务，需处理新增课时与原课表 时间的冲突等等： 另外，对于一些特殊课程，如单双周课程、不规则周次课程也需要进行考 虑，合理安排。对于计算机初排的结果还应可以通过人工交互进行少量的修改 等。 3 排课结果的处理 计算机编排完课程后，对这个结果进行各种条件的查询，并可以根据情况 输出各种形式的表格，以便于教务人员进行处理。例如：可查询某班的课程安排、 某位教师的课程安排、以及某个教室的使用情况。 4 充分利用网络优势 充分利用网络优势，实行计算机分布式排课。计算机排课需要计算机在全 校范围内对各种时间是否发生冲突进行检查，因此早期的计算机排课系统大多 实行集中式排课，一般由教务处负责完成。但目前各校均在扩招，从而造成学 生多、班级多，排课时所需要输入的基础数据多，排课任务都由一个部门来完 成是很不现实的。实行计算机排课的唯一出路就是将排课任务分解，化整为零， 实行分柿式计算机排课。现在各高校大多建立了校园网络，这使得实行分布式 计算机排课成为可能。课程、教师、学生班级、教室等基本信息既可临时录入， 第一章排课系统分析 又可从其它教学管理系统或校园网中获取，以减少数据录入工作量。 2 3 系统陛能要求 1 安全可靠性 系统应能准确、安全、可靠的运行，具备较强的抗误操作能力，保证数据 一致性，确保排课的顺利进行。 另外，系统中的许多基础信息是学校教学管理中的重要基础信息，为了确 保这些信息不被改变或破坏，为系统设计三级安全体系。 第一级管理员身份验证 第二级操作员身份验证 第三级普通用户身份验证 针对不同的使用者，分配不同的使用权限，以便最大程度地保证数据库中 基础数据的安全。 2 操作灵活性 系统要具有友好的人机界面，要求简单、明了、提示性强，采用友好的图 形界面引导教务人员完成整个排课工作。整个系统界面风格要求统一、层次清 楚、方便用户使用。 3 可维护性 在动态环境下，具备调整和维护能力。 2 4 系统的开发环境 2 4 1 数据库系统选择 在系统丌发过程中，需要一种负责数据库的定义、建立、操作、管理和维 护的软件转换系统，这就是数据库管理系统( d b m s ) ，其作用是把用户对数据的 操作转换为对系统文件的存储操作的访问。对d b m s 的选择主要考虑的问题有以 下几个方面： 1 数据库的定义与建立 d b m s 应提供定义手段，并保证数据库安全性与完整性规则的定义，最终 完成数据库的建立。 2 数据库的操作 第二章排课系统分析 能接受、分析和执行用户对数据库提出的各种操作请求，完成对数据库的 查询、插入、删除和修改等工作。 3 数据库的控制 包括控制整个数据库的运行、控制用户的开发操作、执行对数据库的安全 性、完整性的检查。 4 数据库的维护 用户要求或系统设置变化时能修改和更新数据库。 5 故障恢复 运行期间发生故障时，应能够提供有效的措施工具，把故障的影响降低到 最小范围内，并保证尽快恢复。 6 数据通信 应能与操作系统协同处理完成数据的流动。 分析现有的数据库管理系统，本系统选择了a c c e s s2 0 0 2 进行系统丌发。 a c c e s s2 0 0 2 是微软公司的o f f i c e 软件组件之一，它是一种关系型数据库管理应 用程序，通过它可以把存储在多个文件和分散在表中的数据，使用特定的数据元 素链接起来，并可以通过创建可读的报表来整理、统计、显示这些数据。它的一 个文件中可包含所有相关的表、索引、窗体和报表定义，甚至写好的程序也包 含在此文件中。但另一方面，它又采纳了x b a s e 和p a r a d o x 两个关系数据库中 最好的特点。在a c c e s s2 0 0 2 中不仅可以使用这两个数据库中的所有字段数据 类型，而且还增加了一些新的字段数据类型。同时为了完善自身功能，a c c e s s 2 0 0 2 又增加了一套设计窗体和报表的方法，以及从v i s u a lb a s i c 语言的应用中 借鉴了许多程序设计方法。在结构上a c c e s s2 0 0 2 又具有独特的，类似于客户 机服务器数据管理系统d b m 的数据库文件结构，用m d b 作为文件扩展名。在 使用时不需要考虑文件结构的各个方面，因为a c c e s s2 0 0 2 本身会自动管理各 种文件。a c c e s s2 0 0 2 除了可以按m d b 文件结构去维护数据之外，还可以使用已 有的其他数据库中的数据，例如可以按x b a s e 、p a r a d o x 和b t r i e v e 原来文件的 格式使用这些数据库，这种方法称为连接。除此之外，a c c e s s2 0 0 2 也可以从非 数据库管理系统的应用文件中输入数据。例如，e x c e l 电子数据表文件，l o t u s 1 2 3 电子数据表文件，用制表符定界格式的a s c i i 文本文件等。a c c e s s2 0 0 2 可以用它能够输入的任何一种格式输出文件。a c c e s s2 0 0 2 同其他数掘库相比最 大的优势在于：可以挂接其他数据库管理程序通过o d b ca p i ( 开放数据连接应用 编程接口) 所建立的文件，如客户机服务器文件i b md b 2 文件。 1 4 第一章排课系统分析 2 42 数据库设计 数据库设计是应用系统研制成功的基石。为了实现系统功能，系统预设两个 数据库：静态数据库和动态数据库。 1 静念数掘库 排课是一项高难度、复杂的工作，需要考虑的因素很多，而且考虑因素需 根据实际情况不断变化。此数据库是一个丌放式的，用户可根据自己的实际情 况，将新的建议及需考虑的因素加入排课数据库中。 此数掘库随着时l 、日j 的推移，逐步健全排课规则，使排课趋于合理。本系统 权重是采用数值表示，数值大表示优先考虑。 2 动态数据库 本系统的动惫数据库中包含教师的工作安排和课程表等。根据教师每学期 的工作安排，按照工作安排排课。虽然此数据库需经常变动，由于现行体育课 已打丌班级界限，多个班级同时进行多种体育锻炼，上课的班级个数远大于合 班课班级个数，所以课程表分成体育课程表、合班课程表和单班课程表三个相 关的部分。由于一个学期的课程表适用范围不同，本系统设计了起始周、截止 周和使用时间三个字段以区别课程表。 2 4 3 系统的硬件环境 机型：p c 系列微机 c p u ：1 6 6 m h z 以上 内存：3 2 m b 以上 硬盘：2 g b 以上 2 5 系统的开发工具 系统的丌发工具为v i s u a lb a s i c6 0 。v i s u a lb a s i c6 0 编程语言是由m i c r o s o f t 公司推山的极为j “泛的可视化开发r 具，利川v i s u a lb a s i c6 0 可以开发山基丁w i n d o w s 应川 ￥序，依靠强人的编译器以及网络与数据库的开发能力，t l v i s u a lb a s i c6 0 可以开 发山功能强人的虑j l i j 科序。 1 v i s u a lb a s i c6 0 面向对象编程的优点： ( 1 ) 代码可重复使用，因此可以节省丌发时间。 第二章排课系统分析 ( 2 ) 结构化好，容易弄明白特定程序的用途。 ( 3 ) 易于测试，可以把程序分割成小的组件并隔离测试定制的组件。 ( 4 ) 需求改变时，面向对象编程易于扩充。 2 v i s u a lb a s i c 6 0 面向对象编程的特点： ( 1 ) 面向对象编程的基本思想是：把问题分解为一组对象。对象包含数据和处 理数据的例程。每一个对象都应有进一步描述它们的数据和处理对象的函数。 把处理一个特定的对象类型所需要的数据和函数结合在一起，称之为封装。可 以把几个对象组合生成一个新的对象，称之为合成。还可以在现有对象基础上 生成一个新的对象。修改现有对象加入新的功能以生成新的对象，称之为继承。 继承是面向对象编程的强大功能之一，通过继承现有的行之有效的对象，能够 一方面节省代码，不用重新输入原始对象中已有的内容：另一方面，提高可靠 性，直到原始对象能正常运行。所以遇到的错误必然来自新的代码。并且，如 果在原始对象中找到了错误，所作的修改自动影响所有继承他的对象。最后， 还可以提高可读性，若能够弄懂一组基本对象集是如何工作，那么，所有从这 些基本对象派生的对象都将易于理解，只需检查新的数据和函数。 ( 2 ) 面向对象编程的另一个特点是其多念性，即取决于所用的不同对象，可 以改变某个特定函数如何操作。 ( 3 ) 继承性和多态性的组合，可以轻易地生成一系列虽类似但又独一无二的 对象。出于继承性，这些对象共享许多相似的特征。但由于多态性，每个对象 可以有独特的表现。 2 。6 系统总体结构 在对当前有关学校需求的充分分析以及对未柬可能需求的分析基础之上， 确立了系统总体结构。本系统包括五个子系统，它们分别为：录入子系统、自 动排课子系统、查询子系统、报表输出子系统和用户管理子系统。系统的总体 结构设计如图2 1 所示： 图2 1 系统总体结构 第一二章排课系统分析 各个子系统的主要功能为： 1 自动排课子系统 根据录入的基础信息进行有效科学地综合统计，分析各项数据，然后按照 所设计的排课算法编排出科学合理的课程表。 2 录入子系统 实现基础数据的增加、修改、删除功能以及对库中所有数据进行浏览的功 能。这些基础数据包括教学区、教室、院系、专业、教研室、班级、教师、课 程等基本信息，另外还包括编排课表所需要的参数信息、教学信息等附加信息。 为了保证数据库的安全，系统中只为系统管理员和操作人员赋予了操作权限， 而普通用户( 教师、学生) 则没有操作该模块的权限。 3 查询子系统 完成用户提出的各种查询。包括按班级、教师、教室、课程、时问、总教 室等条件进行的查询。 4 报表输出子系统 利用排课算法编排出的结果，重新组织数据，输出用户所需的各种形式的、 复杂的报表。包括单班课表、总课表、单教室占用表、总教室占用表、教师上 课信息、教学任务统计表以及丌课目录表等。 5 用户管理子系统 实现对用户及其权限的管理。为了确保数据库的安全，为不同的用户提供 不同的操作权限。权限不同的用户对数据库的操作范围不同，对于一些权限低 的用户，甚至不给予处理数据库的权力。 第三章综合数据结构与数据库系统的设计 第三章综合数据结构与数据库系统的设计 3 1 生成数据库表 表是a c c e s s 数掘库的基础，是信息的基本载体。其他对象，如查询、报表 的信息都是取自表中的信息。表的设置应该体现数据库的组织性、共享性、独 立性及最小冗余度。因此在设计表时，应该特别注意以下设计原则：即表中不 应该包含重复信息，并且信息不应该在表之间复制；每个表应该只包含关于一 个主题的信息。 排课系统中要生成的数据库表包括作为排课事实的院区、系部、教研室、 班级、课程、教师、教室等初始信息，也包括作为排课系统输出的课表数据及 其它辅助数据。 本系统建立了一个名为u s e r 的数据库，所有具体的数据项都以表的形式放 在数据库中。这些表包括：院区数据库表、系部数据库表、专业数据库表、班 级数据库表、教室数据库表、教师数据库表、教学楼数据库表、教学信息数据 库表、教研室数据库表、开课任务书数据库表、课程表数据库、密码数据库表、 时问模式数据库表。具体参见图3 - 1 所示 图3 1u s e r