论高校自动排课系统排课算法的研究和应用.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 class’Scurriculum arrangement． Each semester,coursestimetabling work is in theteaching supervisory work key point and the difficulty．Auto-course timetablingcan help reduce working pressure and mall·made interruption．Courses timetabling,belonging to the NP question，is unable to give the direct answer,but a possibleresult through guess．Although 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 false．Therefore，it is essential to research oftimetabling．It may help to enhance the timetabling efficiency，promote teachingmanagement level enhancement．   This 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 personification’S algorithm or the strategy，“keeping to the side’’strategy,“selecting the poor'’strategy,“the prospectsurvey'’strategy,“studying'’strategy，reduces in the algorithm the curricula to the priority sensitivity．Through 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 teacher's date load as far as possible balanced and SO on the aspects，can produce the very good results，enhanced the courses timetabling efficiency greatly．    The paper also introduced based on the eHTA algorithm Jiangsu MaritimeInstitute’S 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 timetabling 1绪论1．1论文的研究目的    在我国高等教育中有两个主体：一是学生主体，二是教师主体。

学生主体是指学校教育一切为着学生，教育目的是为了将学生培养成既具备较高的专业能力知识和技能，又有较好的道德修养，对社会有用的人才；另一个主体是教师，因为在校培养学生的工作主要来源于教师，培养学生的大局部工作都包含在教师对学生的日常教学工作中高等院校的教学管理工作J下是将两个主体有效结合起来，保证教学工作能够顺利进展    在高校各项教学管理工作中，排课一直是最根本的、最重要的工作，其实质就是给教学方案中设置的课程安排适宜的时问和地点，保证整个教学工作能够顺利地进展；同时，排课工作也是一项很复杂的工作，排课是一个NP问题，就是始终找不到一个最优的方法能够解决的问题，因为这个问题涉及了多种因素进展组合规划，有教师、学生的因素，也有教室的因素尤其在目前各高校规模不断扩大，教学资源面临紧张，教师总数缺乏的自订提下，排课工作问题更为凸出    在学术界，大家对排课问题的研究由来己久，从上世纪60年代到21世纪的现在，各高校都相继开发了自己的排课系统，但设计系统的算法不统一，有用模拟人工算法、有用遗传算法，有用蚂蚁算法等，每种算法各有特点，但殊途同归，目的是设计出一个合理的排课系统，取代高校原本的人工排课的现状，但目前还没有一个算法能够使设计出的计算机排课系统完全摆脱人工的干预，大局部学校只是利用设计出的计算机排课系统产生出一个初始课表，然后，再由人工调试。

这种排课的过程，有时比完全人工排课更加耗时耗精力，因此，有些高校干脆仍然继续进展完全人工排课    本文详细研究了人工智能中的启发式搜索原理，提出了能够应用于排课问题的启发式排课搜索算法，并运用运筹学中的分层规划，对启发式搜索算法进展进一步的改良，提出了靠边策略、择优策略、前景探测策略和学习策略，并将此算法应用在江苏海事职业技术学院的排课系统中，减少了人工干预排课的次数，提高了系统的应用效果1.2 排课算法研究历史和开展    对排课算法的研究已经接近50年之久从二十世纪六十年代，国外就有人开场对课程表问题进展了研究直到1975年以前的一段时间里，人们主要从构造算法模型入手，研究其解决方法，目的是找到一个解决排课问题的有效算法1962年，Gotl ieb提出了一个构造课程表的数学模型，接着人们对这个模型算法、解的存在性等问题作了许多探索，并提出过一些新的算法模型，但始终未能找出一个有效算法1975年，Even等人在美国STAM J，COMPUTER上发表了“On thecomplexity oftimetable and multi·commodity flow problem〞证明了课表问题是一个NP完全类问题。

NP就是Non．deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题这类问题的答案通常无法按部就班，直接计算出来，只能通过问接的“猜算’’来得到结果这类问题，虽无答案，却有算法，这个算法不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案，还是错误的，并在多项式时间内能够判断)Even等人的论述确立了课表编排问题的学术地位，把人们对编排课表以及研究排课算法的问题提高到了理论的高度进入20世纪90年代以后，国外对课表问题的研究仍然十分活泼比拟有代表的有印度的Uastapu大学管理学院和加拿大Montreal大学杂志中讨论较多的排课算法有模拟人工算法、蚂蚁算法、遗传算法等     国内对排课算法问题也一直有研究，设计出的排课系统，比方南京工学院的UTSS(A University Timetable Scheduling System)系统，清华大学的TISER(Timetable Scheduler)系统，大连理工大学的智能教学组织管理与课程调度系统等，这些系统地运行大都是模拟人工排课过程    模拟人工算法(Simulative Artificial Algorithm，SAA)是根据排课者人工排课的思维和习惯，依次参加“班级、教师、课程〞等信息和不同的限制条件，如：班级是否合班、某教师有空的时『白J段、课程适宜安排的时间段等等，制定算法，设计排课系统。

    蚂蚁算法(ant colony optimization，ACO)，国外提及甚多，这是一种用来在图中寻找最优路径的算法，也称图论算法。