38560字硕士毕业论文通过实例分析了电大自动排课程序的设计与实现。

论文类型：硕士毕业论文

论文字数：38560字

论点：排课,算法,回溯

论文概述：

经过功能测试和性能测试，贵阳广播电视大学自动化排课系统，从数据输入到数据处理，再到数据输出，各组成模块功能运转正常；系统的运行速度、兼容性、稳定性皆达到预期设计要求，能满

论文正文：

第一章导言

 1.1 选题背景及研究目的与意义 中央电大（中央广播电视大学的简称）作为一所直接由教育部管辖的高校，其教学过程中应用了广播和电视技术、文字和音像教材、PPT 以及网络等方式，并借助计算机远程技术实现了开放式教育的新型教学模式。1978年2月开始筹建，1979 年 2 月 6 日正式开学。通过实现本、专科开放教育，给广大社会人员享有平等的受教育机会，尤其对国家机关工作人员、工商企业干部职工、军队和武警的干部战士、欠发达地区基础教育学校的教职工等提供进修进步的阶梯；开展多元化的技能培训、岗位深造以及非学历教育，让所有社会群体能够学到最新的知识与技术；充分利用电大丰富的教育教学资源，整合再造成一个服务于平民的远程教育公共服务体系，帮助实现社会群体及相关组织的远程教育，为他们平时的学习提供支持。进入 21 世纪，为紧跟时发表展的步伐，教育部在全国各大高校开展现代远程开放教育试点。中央电大作为全国最为重要的以远程教育为主体的高校，成为最早的试点之一。其重要特征就是以广播卫星电视、电子信息网络、教学管理网络作为其主导的教育模式。中央广播电视大学于 1979 年 2 月 6 日正式开学，学校的直接领导机关是教育部、广播电影电视部。教育部主要负责教学业务事宜，广播电影电视部主要负责演播技术事宜。与此同时全国各省市区，相继建立省市区广播电视大学近三十所，地市级电大分校和工作站六百余个，在基层单位设立的电大教学班更是多达近一万五千个，一个相当规模的广播电视高等教育网，由此初步形成。电大一直沿用分级办学及管理的组织架构。具体分三级，由上至下分为中央电大、各省级电大以及各地级电大分校和基层各种形式的教学班。同时，各级教育行政主管部门负责管辖和解决相应各级电大的人员配备、财政支持和硬件配套设施等问题。广播电视大学的培养目标是要让学员通过有计划的学习和自主学习基本达到普通高等学校全日制专科的毕业水平。学校实行学分制。学员完成规定的课程，取得相应的学分，由转播中央广播电视课程的省市区广播电视大学发给毕业证书。国家承认持毕业证书者学历相当于高等专科学校毕业。 1.2 国内外现状及分析 上世纪中叶以来，人工智能、电子信息技术、运筹学、计算机网络等科学高速发展，排课问题逐渐开始被人们从更加科学的角度加分析、探索和研究。经过半个多世纪对排课问题的全面研究，人们对排课问题特别是对排课的性质有了更为清晰的理解和认识，更重要的是许多优化和智能算法的提出对解决排课问题产生了积极的推动作用，不少的软件开发者也在此类算法基础上设计了一些计算机自动排课系统，在实践中成功起到计算机辅助排课的作用。国内对排课问题的研究相对滞后，上世纪八十年代才初步形成，最初的主要方法是模拟手工排课以及人工智能来设置专家系统。随着时代的进步和科学技术的迅猛发展，国内对排课问题的研究不断一步一步向广度和深度两个维度扩展，多种研究方法被用于排课问题研究，如模拟退火法、图论、整数规划等。这一章主要介绍了设计和实现一个地市级电大自动化排课系统的背景及意义，介绍了现今国内外的研究现状，介绍了本文研究内容主要分为：排课相关问题、排课算法、系统架构、系统的最终形式和功能等。最后还介绍了论文的章节安排。
 第二章 相关技术研究 2.1 排课问题研究 2.1.1 排课中的基本要素
排课工作之所以复杂、工作量大，是因为要对多个排课要素进行合理的组合匹配，其关键是规避资源冲突，找到一个可行的安排方式。矛盾冲突充满了整个排课的过程，突出表现在任课教师、上课时间、上课班级、开设课程、上课教室等会在组合编排时出现资源的矛盾冲突。其主要因素，主要有教师数量有限、教室数量有限、班级众多、课程门类数量较大等，而教室少、班级多这两个矛盾冲突最为突出[16]。要使课程表编排得科学、合理、有效，需要用全局的眼光，全面考虑班级、时间、教师、学生、教室等诸多因素。学校教学工作和教学活动的开展都围绕着一个中心，也就是落实教学计划。教学计划是排课中一个重要的基本要素。合理配置各种教学资源，组织开展正常的教学活动都需要依据教学计划。在实践中，教学计划的核心是课程，其他各要素又要围绕课程去落实，从系统的客观需要出发，可暂以开课计划替代教学计划。现实中开课计划可以按课程组织，也可以按班级组织，两种形式有所不同。如果是按课程，则包括每个开课计划的课程代码和名称、课程性质和类型、任课教师、每周多少课时、哪些班级开设此门课程等内容；如果是按班级，则包括每个班级开设哪些课程、任课教师、每周多少课时等内容。排课的班级多，不好安排，或有些老师因为种种原因需要照顾。可能使得部分开课计划会先作一些预处理，事先对教室和时间作出相应的安排。这样一类的情况也需要引起注意。时间是排课中的又一个基本要素。节、大节、时间段、天、周、学期、学年等都是在排课问题经常用到的有关时间的概念，其中大节、时间段、天的重要性最为突出。周，往往是学校排课时的常用周期，也就是以周为单位循环上课。只用编制周课表，每周安排同样的课程，直到课时数满。也有一些学校因为资源紧张进行单双周轮流开课，是一种特例，相对较少，暂不考虑。一般每周按周一至周五 5 天排课。每天的时间段按上午、下午、晚上划分为三个。每时间段划分为Ai 节，可用课时总数每天为 N=A1+A2+A3，即上午 A1 节，下午 A2 节，晚上 A3 节。学校文化和教学资源的情况会直接影响 N、Ai 的变化。 2.1.2 排课中的基本规则 简单来看，排定课程表就是一个关于教师、学生、时间和教室等因素的组合规划问题。进行计算机自动排课，合理规避教师、学生、教室三者之间的矛盾冲突是一个最基本的要求，一个教室不能供给上不同的课程的多个班同时使用，相同的教师不能在同一时间任教多门课程。然而，好课表并不能用有没有冲突来衡量。关键是对一些特殊要求进行预处理，优先考虑相关因素。从学校的实际出发，能基本满足各角色的基本要求，能做到教师和学生对大多数课程的安排表示满意，才能成为好课表。教学计划和任务是课表编排的根据，要排出每个班级合理、正确、满意的课表，就要充分考虑时间、空间、教室资源以及个别特殊要求。 2.2 排课算法研究 算法（Algorithm）是指完成一个任务所需要的具体步骤和方法。也就是说给定初始状态或输入数据，能够得出所要求或期望的终止状态或输出数据。算法常常含有重复的步骤和一些比较或逻辑判断。不同的算法可能用不同的时间、空间或效率来完成同样的任务。 2.2.1 回溯算法

回溯算法就是我们通常所说的试探法，这种方法的特点是对问题的解进行系统地搜索，类似于一个有过剪枝 DFS(深度优先搜索)过程。朝着既定目标，向前搜索，遵循一定的优先条件，随着搜索的深入，如果走到某一步，发现无法实现目标或当前的选择不优，就向后返回一步，在上一节点重新进行选择。倘若其中一状态点符合回溯的要求，我们则称之为回溯点。计算机自动排课系统里，针对其中出现的很多约束条件，就是实现选优的条件。这众多的约束条件如果不能被满足，即可判断，当前选择无法达到目标，是不优的。对某一步所有约束条件的检验，就是对该步骤的一个遍历过程，当完成遍历，且没有满足所有约束条件，则进行回溯，重新试探。这个状态点即被叫做回溯点。  2.2.2 贪婪算法 贪婪算法能够用于降低解题的繁琐程度，它不会从综合最优求解为依据，而是利用优先级别来逐步组建最优解，利用将解题过程细分成许多的小细节，以难易度来排序，从而获得按现今分析得出的最优解，慢慢接近预定的目标，迅速取得满意的处理结果。它能对不少问题产生整体最优解，比如最小代价生成树问题、最短路径问题、二分覆盖问题、拓扑排序问题、背包问题、货箱装船问题等。当然，也并不是所有问题都可以通过贪婪算法实现整体最优解，但在某些情形下，整体最优解无法通过贪婪算法得到,仅能得到很好的最优解的近似解。解决问题如果运用贪婪算法有几个主要步骤：（1）求解目标的确定；（2）约束条件分析；（3）优化函数的建立；（4）贪婪策略的设计，是借助此策略进行处理最优问题的重中之重，问题的解决与否与它有着紧密的关联，以优先级别作为基础的贪婪算法主要是借助人工来进行排课的，以班为单位，围绕着各要素和对象选择合适的时间，在该时间上选择对资源进行优化组合进行排课。教师课表、教室课表以及所有班级课表一同排定。当拥有足够的教师以及教室资源时，以优先级别为基础的贪婪算法能够获得相对科学的课表。采取优先级贪婪和化整为零策略可以减小贪婪算法排课的复杂度。排课班可以参照教学计划确定，通过研究开课及排课班级教学资源的状况，针对排课班的需要及占用资源的状况，确定优先级，编排是可以按照优先级先后顺序依次进行。运用贪婪算法设计实现的排课系统，在实际操作中，人工干预较少，排课过程大大简化，但排课原则和资源约束条件的冲突在课表调度问题中经常出现，严重时还会造成组合调度算法中经常出现的死锁问题。 第二章 相关技术研究.........82.1 排课问题研究.........82.1.1 排课中的基本要素.........8第三章 系统需求分析.........163.1 系统需求的总体结构.........163.2 系统需求分析.........16第四章 系统设计.........304.1 系统的总体结构及功能.........304.1.1 系统架构设计......... 314.1.2 系统各模块功能描述及设计方案.........31 结束语 本课题，从研究排课问题到研究算法，从设计到实现，经历了艰苦的过程。通过对排课问题的研究，理清了解决排课问题的思路。把合理规避班级、教师、教室、时间等方面的冲突，作为解决排课问题的突破口，梳理排课的约束条件，为后续的算法设计奠定了基础。通过对各种常用排课算法的研究，结合自身能力和排课系统的特点，在算法的选择上博取众长，运用分治算法、贪婪算法、回溯算法，实现了系统的核心功能自动排课。 参考文献
 [1]伦恰.回溯算法在列车调度中的应用[J].张家口师范专科学校学报,2010,21(4):10-11林巧.利用回溯法求解若干问题的探讨[J].计算机时代,2011:24-26许可.随机约束满足问题的回溯算法分析[J].软件工程,2010,11(11):1467-1471车明,秦存秀,刘凯.基于改进回溯算法的计算机排课系统[J].沈阳工业大学学报,2009,28(6):667-670聂晓东,李振坤,陈平华.基于贪婪算法的排课系统的探讨与实现[J].现代计算机,2007.11:109-112唐洪英,周敏.基于分层分次贪心算法的排课系统设计与实现[J].微计算机信息,2006,2:237-240肖庆航，陆定淑.Delphi 7 数据库开发教程[M].北京：清华大学出版社,2010杨富国.Delphi 程序开发案例解析[M].北京：清华大学出版社，2010萨师煊,王珊主编,数据库系统概论（第三版)[M],北京：高等教育出版社,2010姜力,高群.SQL Server 数据库设计与管理[M].北京：北京大学出版社,2006