自动排课算法的分析

自动排课算法的分析摘要：随着我国教育事1业的不断发展，课程编排问题在很大的程度上影响着学校教学质量的提高。近些年来，政府对教育事业的投入也是逐年加大，可见对教育事业的重视。为了保证教学的质量，学校应该制定出严密合理和规范的课程安排，课程的编制过程是十分复杂和繁重的。下面我们就分析一下排课研究的意义，如今排课问题的现状，以及现有的几种排课算法，详细地分析一下排课算法，关键词：自动排课；排课算法；自动排课算法1.排课算法研究的意义不管是小初高还是大学，靠老师教课来学习还是占主要的部分，这是培养学生的主要途径。在学期开始的时候，学校都会给每人发一张课程表，学生还有老师都是按照课程表来进行计划。一张课程表打印出来十分简单，但是想把课程安排的紧凑合格，管理人员是需要下很大苦工的。新学期开始前学校的管理人员都要整理教学计划，根据教学计划下教学任务书，然后结合教学计划和任务开始编排课程。这个编排过程是繁重而关键的，因为在这些教学调度过程中，不仅有大量繁琐的数据整理工作，还有严谨思维的脑力劳动，需要填写并打印大量的表格。21世纪以来，信息技术突飞猛进，计算机排课慢慢取代了手工排课，这一技术的发明大大减轻了管理人员的工作量，而且采用计算机排课有利于学校对老师教学贡献的评估，有利于优化学生的学习过程，也有利于学校领导决策更合理化，最为重要的是有利于学校教学质量的提高。2.排课的现状分析在国外很早就有人研究课程编排问题，在 1962年，Gotlieb提出了一个课表问题的数学模型，他利用匈牙利算法解决了三维线性运输问题。然后，人们对课表问题的算法、解的存在性等方面做了许多深入探讨。近40年来，在计算机新技术的基础上，人们又进行了不断地尝试，并取得一些成效。如1965年，Mihoc和Balas将课表公式化为了一个优化问题；Krawczk提出了一种线性编程的方法；Junginger将课表问题简化为一个三维运输问题。最近几年，我们在课程编排方面已经取得了一些成绩，但是对于多数学校而言，这种课表编排还不具备实用价值，只能在极为简单的情况下才能实现。然而，人们并没有放弃研究课表问题，在九十年代，国外在课表问题研究方面的主要代表人物有加拿大Montreal大学的Jean Aubin和Jacques Ferland、印度的Vastapur大学管理学院的ArabindaTripathy等。我国对课表问题的研究是开始于80年代初期，具有代表性的是南京工学院的UTSS（A University Timetable Scheduling System）系统，清华大学的TISER（Timetable SchedulER）系统，大连理工大学的智能教学组织管理与课程调度等。不管是国外研究还是国内的研究，从实际使用情况来看，国内外研制开发的软件系统都不是很实用，比如，我国研制的系统，这些系统大多是模拟手工排课过程的。这种系统课表编排经实践证明是不适合进行大量推广的，因为它过于依赖各个学校的教学体制，限制性较大。另外，排课系统本来就是很复杂的，排课很难做到面面俱到，而且，每个学校都有其特殊性，如果是想要改动某个地方，有可能使全部的课程发生大调整，这就是说全校的课程都会发生变动，在实际应用中我们会发现这是很难实现的。经过长时间的研究，目前解决课表方法的问题有：模拟手工排课法，图论方法，拉格朗日法，二次分配型法等多种方法。在排课算法上，目前，人们已经研制出了几种，比较流行的是自动排课算法和基于时间片优先级的排课算法。下面我们主要介绍详细一下自动排课算法。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)我们要思考的就是如何设计出恰当的数据结构和算法, 从而确定 C1 , C2 , ., Cn 中每个课程的教学应该占据的时间段,还得保证美个时间段只能由一门课程占据.3.2主要数据结构对于每一门课程,分配2 个字节的"时间段分配字" : T1 , T2 , ., Tn . 每个时间段分配字(假设为Ti )的格式为:Ti 的数据类型C 语言格式定义为:unsigned int . 以Ti的最高位来表示该课程是否有效，如果是0的话表示有效，1的话则表示无效。其他的被称为课程分配位，每个分配位占连续的3 个位，这里的位就是bit，用来表示星期一到星期五所安排课程的时间段的值，0是表示当日没有排课，14是表示课程所安排的相应的时间段，如果值大于4的话就表示无效。这样的话，小于32 768 (十六进制8000)就是有效的时间段分配字的值，大于等于32 768 的时间段分配字则是对应无效的课程。3.3排课算法在上述假设下,我们可以看出，自动排课算法的目标就是确定 C1 , C2 , ., Cn 所对应的 T1 , T2 , ., Tn .假设成立的话,我们发现一共可有20 !/ (20 - N) !种排法 . 假设一共有4 门课,每门课一个星期上2 次,则N = 8 ,就是说这8 次课安排的方法就可能会有20 !/ (20 - 8) ! = 5 079 110 400 ,即50 多亿种.在这种多可能性的情况下，排课必须有一个确定的排课标准，这样才能节省时间，提高效率。一般情况下我们会采用轮转分配法来进行:首先从星期一开始就按 C1 , C2 , ., Cn 中的相应顺序来安排课程，每门课程安排1 次,之后再按这样的顺序继续排后面的课程,直到所有课程的开课次数都与 N1 , N2 , ., Nn 中给定的值相符合. 在算法描述中用 C1 , C2 , ., C n 表示 C1 , C2 , ., Cn ， N1 , N2 , ., Nn以及 T1 , T2 , ., Tn。3.4算法的优缺点分析 优点：这个算法是以课程为中心的，然后进行搜索匹配，取得最先匹配的值；它具有占有空间少，运算速度快这两个特点。缺点：该算法无法对数据进行择优选取，所以不无法合理分配学校的教学资源，并不能满足一些特殊要求，比如说有些老师喜欢上午上课，有些老师偏向于组织集体上课；有些课程安排到上午会更合适些，有些课程不能安排到上午等。参考文献：1蔡启明,吴新民;基于中小学校园网的自动排课系统的分析和设计J;电化教育研究;2003年03期2祝勇仁;邓劲莲;胡献华;张炜;排课问题的一种遗传算法适应度求解方法A;第四届中国软件工程大会论文集C;2007年