一 课题背景

信息社会的高科技，经济化的高效益，使计算机的应用已普及到经济和社会工作的各个领域。而素质教育在学校不断的深化，学校对学生的实践能力也越来越重视，所以学校的实验室和实验课课时也越来越多。而且许多学校开始实行学生的自主选课模式，而不是传统的教学模式。以往排课选课中，只能通过人工的方式编排。但是，随着各类学科范围的不断扩大，各个院系的学科科目逐渐增多，以至于庞大的课时、众多的教师、复杂的教室信息令管理人员无法合理、迅速、高效地制定出相应的排课计划。采用手工方式排课，有时需要花费一个月甚至更长时间才能完成一个学期的排课任务。这就促使我们必须采用一些以计算机为辅助的手段来帮助

一 研究意义

如今，高校每年招生数量的急剧增加以及教室资源紧张等一些原因，靠人工方法来进行排课很难很好的实现。有了课程调度系统，将为学校在排课方面带来极大的方便。教务处的工作人员只需要输入简单的数字，汉字就可以轻松的实现排课。同时， 利用计算机进行自动排课,不但能使教务人员从繁杂的排课任务中解脱出来,提高教务管理工作效率,而且能改善教学管理质量,合理、高效地利用有限的教学资源,使学校的各种教学活动、教学管理及其它相关的工作能够有序、规范地进行,维持正常的教学秩序,同时对推动教务管理的信息化起到非常重要的作用。

二 研究现状

国外针对排课问题展开的研究较早。1963年Gotlieb在他的文章《The Construction of Class-Teacher Time-Tables》中提出了课表编排的数学模型，并使用匈牙利算法解决了三位线性运输问题。此后，人们对课表问题的算法，解的存在性问题做了很多深入探讨，但是大多数文献所用到的数学模型都是Gotlieb的数学模型的简化或补充。1976年Even在其论文《The Complexity of Timetable And Multi Commodity Flow Problem 》中，第一次证明了课表问题是NP完全的。Even的论证进一步地将人们对课表问题复杂性的认识提高到理论高度。近50年来，人们对课表问题的计算机解法做了很多尝试。其中，有人将课表编排的整数规划模型问题归结为求一组0-1变量的解，但是其计算量非常的大，而且解决0-1线性优化问题的分支定界技术只适用于规模较小的课表编排；Mihoc和Balas（1965）将课表公式化为一个优化问题；另外还有人提出将它当做一种线性编程的方法或将课表问题简化为三维运输问题；而Tripathy则把课表问题视作整数线性编程问题并提出了大学课表的数学模型；此外，有些文献试图从图论的角度来求解课表问题，但是图的染色问题也是NP问题，只有在极为简单的情况下才可以将课表编排转化为二步图匹配问题。这样的数学模型与实际相差甚远，所以对于大多数学校的课表编排问题来说没有实用的价值。进入九十年代以后，国外对课表问题的研究仍然十分活跃，比较有代表性的有印度的Vastapur大学管理学院的Arabinda，Tripathy，加拿大Montreal大学的Jean Aubin和Jacques Ferland等。对于课表的编排，已经适用的算法有：关联规则FP-growth算法，基于时间位图叠加匹配的算法，基于资源匹配的算法，分组优化决策算法，分支定界法，有限回溯法，拉格朗日松弛法，二次分配型法等多种方法。由于课表约束复杂，用数学方法进行问题描述时往往导致问题规模剧烈增大，这已经成为运用数学编程解决课表问题的巨大障碍。外国的研究表明，解决大规模课表编排问题单纯靠数学方法是行不通的，而利用运筹学中分层规划的思想将问题分解，将是一个有望成功的办法。

国内对排课问题的研究较晚，开始于80年代初期。1984年，清华大学在《清华大学学报》上发表了林漳希和林尧瑞在该课题上的实验性研究成果《人工智能技术在课表编排中的应用》。 其他一些具有代表性的有：南京工学院的UTSS（A University Timetable Scheduling System）系统，清华大学的TISER系统，大连理工大学的只能教学组织管理与课程调度系统，西南交通大学在分析高校课程编排所遵循的基本原则和模糊性原则的基础上，定义了课元之间关于教师的相关关系和关于自然班的相关关系，提出了以课元相关运算和课元的候选时空片计算为核心的计算机排课算法，延边大学根据高校课程表的制作特点，设计了计算机自动排课的数据结构与算法；沈阳电力高等专科学校研制了基于Client/Server的开放式只能排课系统等。使用遗传算法来求解排课问题也有较多其他相关的报道，还有一些其他高校根据自己的情况编写了一些程序去实行计算机自动排课，例如浙江大学的”教务管理系统”等等。这些系统大都是模拟手工排课过程，以”班”为单位，运用启发式函数来进行排课，都或多或少存在问题。所以，虽然为了使课表的编排更准确、合理、快速,高校教务部门已先后开发出一些适用的排课系统，但我们发现这些软件有以下不足:每个学期的课程、教师、教室信息相对固定,但却不能被重用；不能保存每个学期的历史数据,不便教师对以前课表进行查询；未提供用户的分级使用制度；自动排课速度较慢；形成的课表大小不固定,增加打印难度，因此现在的排课系统正在向解决这些问题的方向发展。

参考文献

[1] 陈洁.学校教务部门排课问题的数学模型及算法. 教育信息化，1999.3