软件工程硕士论文高校自动排课系统排课算法研究与应用.doc

软件工程硕士论文：高校自动排课系统排课算法研究与应用(一)摘要 排课，是给学校各专业的教学计划中设置的课程安排合适的时间和地点，也就是给每个班的课程安排时间和地点。排课工作在教学管理中很重要也很繁琐，计算机自动排课系统，可以降低排课人员的工作量，减少排课中的人为因素。但排课问题属于NP问题，即无法直接得到答案，只能通过猜测获取可能结果。通常NP问题虽无答案，却有算法，算法不能直接告诉答案，但可以用来判断可能的结果是否J下确可行。因此，要做好排课工作，提高排课效率，研究排课算法是必不可少的。 本文在查阅大量相关文献的基础上，对高校的排课问题进行了分析，通过对人工智能中的启发式搜索理论的研究，对优先权策略和分配策略加以分析和应用，设计出排课算法启发式排课算法(HTA)。同时，又对HTA算法中薄弱点(主要是对课程等对优先权过于敏感)进行进一步改造，即在HTA算法的基础上，应用一些拟人的算法或策略，包括靠边策略、择劣策略、前景探测策略、学习策略，减少算法中各因素对优先权的敏感，克服HTA算法的缺陷，完善HTA算法内容。改造后的算法命名为eHTA算法。通过实验，证明eHTA算法在减少人工干预排课次数、好时间好教室的利用、尽量满足约束条件、班级和教师的同负荷均衡等方面，能够产生很好的效果，大大提高了排课效率。 论文还介绍了基于eHTA算法的江苏海事职业技术学院自动排课系统构架，并将系统应用的效果与人工排课进行对比，以科学的方式，证明eHTA算法在提高排课效率各方面的作用。关键词：启发式算法，eHTA，排课The Research and Application of University CoursesTimetabling AlgorithmAbstract Courses timetabling,is to arrange the appropriate time and the place to thecurriculum in school each specialized plan of instruction or is for each classScurriculum arrangement Each semester,coursestimetabling work is in theteaching supervisory work key point and the difficultyAuto-course timetablingcan help reduce working pressure and mallmade interruptionCourses timetabling,belonging to the NP question，is unable to give the direct answer,but a possibleresult through guessAlthough the question does not have the answer，has thealgorithm actually，the algorithm usually cannot tell the answer,but Can tell whetherthe some possibility is true of falseTherefore，it is essential to research oftimetablingIt may help to enhance the timetabling efficiency，promote teachingmanagement level enhancementThis article in the consult massive correlation 1iterature foundation has carried onthe analysis to courscs timetabling，through to the artificial intelligence inspirationalsearch theory research，applied to the priority strategy and the assignment strategy,has designed new algorithm Heuristic Timetabling Algorithm(HTA)At the sametime，also to HTA algorithm in regarding curriculum the priority too sensitiveshortcoming has made the improvement，proposed the eHTA algorithm，appliessome personificationS algorithm or the strategy，“keeping to the sidestrategy,“selecting the poorstrategy,“theprospectsurveystrategy,“studyingstrategy，reduces in the algorithm the curricula to the priority sensitivityThrough theexperiment，proved the eHTA algorithm in the reduced manual intervention numberof times，the good time good classroom use，satisfies the constraint condition，theclass and grade and teachers date load as far as possible balanced and SO on theaspects，can produce the very good results，enhanced the courses timetablingefficiency greatly The paper also introduced based on the eHTA algorithm Jiangsu MaritimeInstituteS courses automatic course timetabling system framework It has alsorecorded this system application effect carried on the past artificial timetabling thecontrast，by the science way，proves the eHTA algorithm in the enhancementtimetabl ing efficiency various aspects function Key Words：Heuristic Timetabling Algorithm，eHTA，courses timetabling1绪论11论文的研究目的 在我国高等教育中有两个主体：一是学生主体，二是教师主体。学生主体是指学校教育一切为着学生，教育目的是为了将学生培养成既具备较高的专业能力知识和技能，又有较好的道德修养，对社会有用的人才；另一个主体是教师，因为在校培养学生的工作主要来源于教师，培养学生的大部分工作都包含在教师对学生的日常教学工作中。高等院校的教学管理工作J下是将两个主体有效结合起来，保证教学工作能够顺利进行。 在高校各项教学管理工作中，排课一直是最基本的、最重要的工作，其实质就是给教学计划中设置的课程安排合适的时问和地点，保证整个教学工作能够顺利地进行；同时，排课工作也是一项很复杂的工作，排课是一个NP问题，就是始终找不到一个最优的方法能够解决的问题，因为这个问题涉及了多种因素进行组合规划，有教师、学生的因素，也有教室的因素。尤其在目前各高校规模不断扩大，教学资源面临紧张，教师总数不足的自订提下，排课工作问题更为凸出。 在学术界，大家对排课问题的研究由来己久，从上世纪60年代到21世纪的现在，各高校都相继开发了自己的排课系统，但设计系统的算法不统一，有用模拟人工算法、有用遗传算法，有用蚂蚁算法等，每种算法各有特点，但殊途同归，目的是设计出一个合理的排课系统，取代高校原本的人工排课的现状，但目前还没有一个算法能够使设计出的计算机排课系统完全摆脱人工的干预，大部分学校只是利用设计出的计算机排课系统产生出一个初始课表，然后，再由人工调试。这种排课的过程，有时比完全人工排课更加耗时耗精力，因此，有些高校干脆仍然继续进行完全人工排课。 本文详细研究了人工智能中的启发式搜索原理，提出了能够应用于排课问题的启发式排课搜索算法，并运用运筹学中的分层规划，对启发式搜索算法进行进一步的改进，提出了靠边策略、择优策略、前景探测策略和学习策略，并将此算法应用在江苏海事职业技术学院的排课系统中，减少了人工干预排课的次数，提高了系统的应用效果。1.2 排课算法研究历史和发展 对排课算法的研究已经接近50年之久。从二十世纪六十年代，国外就有人开始对课程表问题进行了研究。直到1975年以前的一段时间里，人们主要从构造算法模型入手，研究其解决方法，目的是找到一个解决排课问题的有效算法。1962年，Gotl ieb提出了一个构造课程表的数学模型，接着人们对这个模型算法、解的存在性等问题作了许多探索，并提出过一些新的算法模型，但始终未能找出一个有效算法。1975年，Even等人在美国STAM J，COMPUTER上发表了“On thecomplexity oftimetable and multicommodity flow problem”证明了课表问题是一个NP完全类问题。(NP就是Nondeterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。这类问题的答案通常无法按部就班，直接计算出来，只能通过问接的“猜算来得到结果。这类问题，虽无答案，却有算法，这个算法不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案，还是错误的，并在多项式时间内能够判断。)Even等人的论述确立了课表编排问题的学术地位，把人们对编排课表以及研究排课算法的问题提高到了理论的高度。进入20世纪90年代以后，国外对课表问题的研究仍然十分活跃。比较有代表的有印度的Uastapu大学管理学院和加拿大Montreal大学。杂志中讨论较多的排课算法有模拟人工算法、蚂蚁算法、遗传算法等。 国内对排课算法问题也一直有研究，设计出的排课系统，比如南京工学院的UTSS(A University Timetable Scheduling System)系统，清华大学的TISER(Timetable Scheduler)系统，大连理工大学的智能教学组织管理与课程调度系统等，这些系统地运行大都是模拟人工排课过程。 模拟人工算法(Simulative Artificial Algorithm，SAA)是根据排课者人工排课的思维和习惯，依次加入“班级、教师、课程”等信息和不同的限制条件，如：班级是否合班、某教师有空的时白J段、课程合适安排的时间段等等，制定算法，设计排课系统。 蚂蚁算法(ant colony optimization，ACO)，国外提及甚多，这是一种用来在图中寻找最优路径的算法，也称图论算法。这个算法由Macro Dorigo于1992年在他的博士论文中引用，其灵感来源于蚂蚁寻找食物过程中发现路径行为。要让蚂蚁找到食物，就需要让它们遍历空间上所有点；如果要找到最短路径，那么需要计算所有可能的路径，并且比较大小。这个算法本身就很复杂。 遗传算法，由美国Michigan大学教授JHolland与1985年首先提出。这种算法模拟生物发展进化的过程：遗传、变异和选择。生物学中提出每种种群由不同基因编码的各种染色体组成。这个算法可以应用在现实中，种群即问题；每个染色体对应问题的一个解；从初始种群开始，对适应值进行选择，然后变异成一种新的种群；这样一代代演化下去，直到满足期待值为止。这种算法虽然能够解决一定的问题，但染色体本身也是一个NP问题。目前，对排课算法问题的讨论依然很多，但还没有一个算法能够作为计算机自动排课系统的依据，使这个系统能够真J下摆脱人工干预，或许对排课算法的研究可以从如何减少人工干预这一点入手，始终向完全自动排课方向迈进，排课系统的设计才能越来越如人意。1.3 论文的主要研究内容和结构1.3.1 论文的主要内容 本文通过查找各种文献资料，对南京部分高等院校排课问题进行调研，以江苏海事职业技术学院为例，分析了当前高校的现状，对排课问题进行深入研究和分析；在算法方面，运用人工智能学中介绍的启发式搜索原理(Heuristic Theory)和运筹学中的分层规划(Hierarchical Planning)思想，研究出启发式排课算法(Heuristic Timetabling Algorithm，HTA)并应用在实际排课系统设计中，以减少计算机自动排课中的人工干预，提高排课效率。 启发式原理就是依据中间信息，有步骤、有顺序地搜索目标。分层规划思想是对决策目标下的各种不确定性因素进行分类、分层，形成多准则，对各准则下的混合最优解划分权重系数，进行再次规划，形成一个最优化的决策方案。 本文是在启发式原理应用在排课问题上，形成启发式排课算法(HTA)的同时，对启发式排课算法再次进行改进，运用分层规划思想，提出靠边策略、前景策略和学习策略，改进后的启发式排课算法(eHTA)应用在实际排课设计中，通过对比实验，提高了排课效果。1.3.2 论文的结构 本论文的结构包括5章内容： 1)绪论 阐述本论文研究排课算法的目的。排课就是将教学计划中所有设置的课程能够合理地安排，保证学校的教学工作能够顺利进行。排课工作是一项组合规划工作，是高等院校教学管理中的一项非常重要的工作。面对目前教学资源紧张的局面，排课工作无法完全由计算机自动完成，仍然需要负责排课的教务员投入大量的时间和精力。在这样的情况下，本论文研究排课算法，虽无法达到计算机自动排课目标，但可以在很大程度上减少排课工作的人工干预，达到提高排课效率，促进教学管理改革进步的目的。 2)高校排课系统的需求分析 详细分析高校排课系统在排课原则和功能、性能、运行环境及安全性方面需要达到的要求。 3)启发式搜索理论 对人工智能领域的启发式搜索理论进行分析，提出它可应用在排课问题的方面。 4)基于启发式搜索理论的排课算法 根据启发式搜索理论的启迪，建立启发式排课算法(HTA算法)；而后，又依据运筹学中的分层规划思想，提出靠边策略、前景探测策略和学习策略，改进HTA算法，形成eHTA算法。这一章对这HTA和eHTA算法进行了详细描述和分析，也是论文的重点。 5)基于J2EE和MVC的排课系统构架设计 介绍江苏海事职业技术学院自动排课系统的框架，将面向对象技术应用于高校排课系统， 突出软件设计流程，并对应用eHTA算法的排课系统的效率进行了评估。2 高校自动排课系统的需求分析 应用自动排课系统是所有高校排课工作的趋势，它可以降低排课人员的工作量，减少人为干预排课次数，提高排课工作的效率。合理地实施教学计划中的课程安排，保证教学工作顺利进行，高校自动排课系统的设计也必须建立在院校排课工作的基本原则之上，同时在功能、性能、运行环境、安全性等方面，满足各高校的要求。2.1 高校排课工作的基本原则 随着高等院校办学规模的不断扩大，办学层次的不断提高，高等院校排课管理工作也显得越来越重要，学校要做好这项工作，关键要遵循科学的排课原则，采取有效的管理办法，实现课表编排现代化。 1)有利于充分利用教学设备和条件的原则 设计排课系统的算法具有一定的复杂性，设计教师、教室班级、课程和时间等信息对象，算法目标是为满足需求(如班级、课程等)进行合理资源(如教室、教师和时间等)分配，核心问题是避免资源冲突。在学校的教学工作中，有些课程需要共同使用学校的场地、设备、器材、实验室等。如公共体育课需要用到操场、游泳池、体育器材等，专业课程需要用到实验室、阶梯教室。在排课中必须根据实际情况给予科学的安排、周密的考虑，以提高设备的使用效率。规模较大的高校，教师一般采用“穿插使用”的办法，这些学校许多课程如公共课是跨系、跨专业进行的，一个班级没有固定的上课教室，一门课程或许是几个班级的学生坐在一起，而另-课程却在其它教室早上，像这样不时地变换上课地点的课程，排课是要避免“撞车”现象的发生。特别是近年来，随着各校招生规模的不断扩大，学校教学设备和条件普遍吃紧的情况下，更要合理安排和充分利用好现有教学条件和设备，避免“撞车”现象或闲置。 2)科学的制定教学计划，保证课程顺利开设原则 教学计划是学校教育、教学的指导性文件，是编排课程表的唯一依据。它根据学生的身心发展规律，按照教育原则和培养目标，根据学科的内在必然联系，合理的、科学的、有序的编订了每学期要开设的课程。课掌教学是按固定的课程表进行的，课程表是学校全面贯彻党的教育方针，培养具有一定规格的大学生的具体反映。它应该按照教育学和教育心理学的原理科学的将教学计划固定下来，并通过教学活动不断的得到实施和完成的。而且根据高职学校的教学特点，教学计划要求满足以下几点： 既要有便于执行的相对的稳定性，又要顺应职业社会需求的发展变化甚至要有超前意识； 既要明确理论教学的任务，又要规范技能训练的标准： 对于“复合型专业，还要注意跨学科的各门课程之间的联系与衔接，甚至先后顺序、深浅程度、课时比例都要反复向有关专家征询。在编排课程表时，一定要严格按照教学计划制定，保证课程顺利丌设，不要随意改变或停开某一课程。 3)体现“以人为本”的原则 全校教师在教学活动中，应团结、协作和谦让，体现“以人为本”的原则，尽可能的考虑学生的发展和教师本人的利益，创造一个和谐的工作环境。年轻教师刚参加工作，只是具备一定的理论基础，在实践技能方面还有待于向有经验教师学习请教。因此每天的课时，年轻力壮的教师可以集中安排，便于集中时间去学习，年老体弱的教师分散编排，以利于劳逸结合，不影响身体和教学效果。新老教师同时上课时，尽量把老教师安排在前面，新教师安排在后面，“以老带新”，让新教师先听后讲有学习的机会。要想提高学校的教学水平，必须先提高教师素质。近2年，各高校，特别是高职院校将“双师型”作为严格要求教师的标准，鼓励教师从事项目科研工作，因此，在编排课程表时要充分考虑任课教师的教学与科研活动。要适当集中安排任课教师的课时，让他们有一个相对集中的时间去学习、搞科研，也给教师有充分休息和备课时间。但不要在一天或连续二天内安排很多课时，或者课程连续安排，以防过度疲劳，影响教学效果和教师健康。对身体健康状况不良的教师和家庭需要照顾的教师，安排课程时在合理的前提下应尽可能的给予照顾。同一学科中新老教师的课应不在同一节课中安排，如果教师外出参加活动，便于安排代课。 4)有利于提高学生学习效率的原则 学生是学校教育的主体，教学的目的就是要让受教育者接受知识，理解和掌握知识，发展学生的认识能力和体力，培养学生的世界观和道德品质。高等院校不同于中、小学，除了要侧重专业学术的研究以外，也需并举学生实践技能的培养和提高。面对不同性质的课程，如何根据学生的心理特点和身心健康发展规律合理编排课程，提高学习效益，是值得研究的课题。为了提高学习效率，考虑需要处理好以下几个方面：一般编排两节连掌课，但至多不要超过三节。安排两节连堂课，一方面有利于大学教学内容的合理安排，让一些理论知识和观点得到连贯的较全面的阐述；另一方面，连续三节课以上的课程，时间较长，学生容易产生疲劳，容易产生“倒摄抑制”和较大的“负迁移”效应，影响学习效果。学习难度较大或主干课程应当安排在学生和教师精力最旺盛的时间。一般讲，每天上午是最佳黄金时间，学生和教师精力充沛，大脑清醒，不易产生“前摄抑制”现象，适宜安排难度较大或主干课程。每天下午和晚上学生容易疲劳，精力易分散，适宜安排各种活动课程和易理解的课程，如实验、体育、选修课等课程。不同性质不同层次的课程适当搭配、交错编排。高校需要开设多类课程，这些课程性质不同，层次也不尽相同，在排课时要尽量做到“适当搭配、交错编排”，记忆课程与逻辑演绎的课程可以交叉混排。实验课与理论课的编排，最好先上理论课，后紧接着实验课，时间隔的不要太长。高职学校注重技能实践教育，但电不能因此排课将体育、实践技术等体能、实践课程安排在同一天，以免学生过于疲劳。软件工程硕士论文：高校自动排课系统排课算法研究与应用(二)22自动排课系统的需求分析2.2.1数据需求 1)静态数据需求 高校排课系统中涉及到的因素有4个：教师、班级、课程、教室。排课就是对这4个因素进行组合规划，所以，这4个因素的信息要完整和相对稳定。这些因素的信息至少包含： 教师(教师编号，教师姓名，所在系部编号，所教课程编号) 学生(班级编号，所在系部编号、所在专业编号、班级人数) 课程(课程编号，课程名称，所属系部编号，所属专业编号，课程性质，课时) 教室(教室编号，教室类型，教室座位数，是否安排) 以上四个因素在组合规划时，不能发生冲突，即同一名教师在同一时间只能安排同-课、同一个班级只能在同一时间一问教室安排一门课、同一问教室在同一时间不能被两门课或两个班级占掘。满足了以上的要求，系统在排课逻