- 相关推荐
自动排课算法的分析论文
摘 要:随着我国教育事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是表示当日没有排课,1~4是表示课程所安排的相应的时间段,如果值大于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} 中给定的值相符合. 在算法描述中用{ C[1 ] , C[2 ] , ., C[ n ]} 表示{ C1 , C2 , ., Cn} ,{ N1 , N2 , ., Nn}以及{ T1 , T2 , ., Tn}。
3.4算法的优缺点分析
优点:这个算法是以课程为中心的,然后进行搜索匹配,取得最先匹配的值;它具有占有空间少,运算速度快这两个特点。
缺点:该算法无法对数据进行择优选取,所以不无法合理分配学校的教学资源,并不能满足一些特殊要求,比如说有些老师喜欢上午上课,有些老师偏向于组织集体上课;有些课程安排到上午会更合适些,有些课程不能安排到上午等。
参考文献:
[1]蔡启明,吴新民;基于中小学校园网的自动排课系统的分析和设计[J];电化教育研究;2003年03期
[2]祝勇仁;邓劲莲;胡献华;张炜;;排课问题的一种遗传算法适应度求解方法[A];第四届中国软件工程大会论文集[C];2007年
【自动排课算法的分析论文】相关文章:
案例分析论文11-07
本科论文目录自动生成11-15
论文的可行性分析02-21
浅论软件需求分析的论文11-10
论文的问卷分析报告范文11-05
案例分析论文15篇11-09
案例分析论文(15篇)11-10
论文参考文献自动编号11-16
论文参考文献自动生成10-26
环境分析与现代仪器分析方法论文09-17