资源描述：
《自动排课算法的分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、自动排课算法的分析摘要：随着我国教育事1业的不断发展，课程编排问题在很大的程度上影响着学校教学质量的提高。近些年来，政府对教育事业的投入也是逐年加大，可见对教育事业的重视。为了保证教学的质量，学校应该制定出严密合理和规范的课程安排，课程的编制过程是十分复杂和繁重的。下面我们就分析一下排课研究的意义，如今排课问题的现状，以及现有的几种排课算法，详细地分析一下排课算法，关键词：自动排课；排课算法；自动排课算法1.排课算法研究的意义不管是小初高还是大学，靠老师教课来学习还是占主要的部分，这是培养学生的主要途径。在学期开始的时候，学校都会给每人发一张课程表，学生还有老师都
2、是按照课程表来进行计划。一张课程表打印出来十分简单，但是想把课程安排的紧凑合格，管理人员是需要下很大苦工的。新学期开始前学校的管理人员都要整理教学计划，根据教学计划下教学任务书，然后结合教学计划和任务开始编排课程。这个编排过程是繁重而关键的，因为在这些教学调度过程中，不仅有大量繁琐的数据整理工作，还有严谨思维的脑力劳动，需要填写并打印大量的表格。21世纪以来，信息技术突飞猛进，计算机排课慢慢取代了手工排课，这一技术的发明大大减轻了管理人员的工作量，而且采用计算机排课有利于学校对老师教学贡献的评估，有利于优化学生的学习过程，也有利于学校领导决策更合理化，最为重要的是
3、有利于学校教学质量的提高。2.排课的现状分析在国外很早就有人研究课程编排问题，在1962年，Gotlieb提出了一个课表问题的数学模型，他利用匈牙利算法解决了三维线性运输问题。然后，人们对课表问题的算法、解的存在性等方面做了许多深入探讨。近40年来，在计算机新技术的基础上，人们又进行了不断地尝试，并取得一些成效。如1965年，Mihoc和Balas将课表公式化为了一个优化问题；KraetableSchedulingSystem）系统，清华大学的TISER（TimetableSchedulER）系统，大连理工大学的智能教学组织管理与课程调度等。不管是国外研究还是国内
4、的研究，从实际使用情况来看，国内外研制开发的软件系统都不是很实用，比如，我国研制的系统，这些系统大多是模拟手工排课过程的。这种系统课表编排经实践证明是不适合进行大量推广的，因为它过于依赖各个学校的教学体制，限制性较大。另外，排课系统本来就是很复杂的，排课很难做到面面俱到，而且，每个学校都有其特殊性，如果是想要改动某个地方，有可能使全部的课程发生大调整，这就是说全校的课程都会发生变动，在实际应用中我们会发现这是很难实现的。经过长时间的研究，目前解决课表方法的问题有：模拟手工排课法，图论方法，拉格朗日法，二次分配型法等多种方法。在排课算法上，目前，人们已经研制出了几种
5、，比较流行的是自动排课算法和基于时间片优先级的排课算法。下面我们主要介绍详细一下自动排课算法。3.自动排课算法3.1问题的简化描述设要安排的课程为{C1,C2,.,Cn},课程的总数设为为n,各门课程每周安排的次数(每次为连续的2学时)则设为{N1,N2,.,Nn};每星期教学五天，也就是从星期一到星期五;每天最多只能安排4次教学课程,就是1～2节、3～4节、5～6节和7～8节，在以下我们将4次教学课程分别称第1、2、3、4时间段.这样，在这种假设下,每周的教学总时间的段数就是5×4=20，如以下这种表达方式:n≤20,(1)N=6n，i=1，Ni≤20.(2)我
6、们要思考的就是如何设计出恰当的数据结构和算法,从而确定{C1,C2,.,Cn}中每个课程的教学应该占据的时间段,还得保证美个时间段只能由一门课程占据.3.2主要数据结构对于每一门课程,分配2个字节的"时间段分配字":{T1,T2,.,Tn}.每个时间段分配字(假设为Ti)的格式为:Ti的数据类型C语言格式定义为:unsignedint.以Ti的最高位来表示该课程是否有效，如果是0的话表示有效，1的话则表示无效。其他的被称为课程分配位，每个分配位占连续的3个位，这里的位就是bit，用来表示星期一到星期五所安排课程的时间段的值，0是表示当日没有排课，1～4是表示课程所
7、安排的相应的时间段，如果值大于4的话就表示无效。这样的话，小于32768(十六进制8000)就是有效的时间段分配字的值，大于等于32768的时间段分配字则是对应无效的课程。3.3排课算法在上述假设下,我们可以看出，自动排课算法的目标就是确定{C1,C2,.,Cn}所对应的{T1,T2,.,Tn}.假设成立的话,我们发现一共可有20!/(20-N)!种排法.假设一共有4门课,每门课一个星期上2次,则N=8,就是说这8次课安排的方法就可能会有20!/(20-8)!=5079110400,即50多亿种.在这种多可能性的情况下，排课必须有一个确定的排课标准，这样才能节省时
8、间，提高效
