近年来,系统环境现代大学的学科设置越来越科学,大学的学习方式也在不断的更新,许多国内的大学开始向国际化方向发展,采用学分制的管理系统。而随着高校新生的扩招力度加大,各高校都面临着教室资源紧张的问题,原来每个班有一个固定教室的模式已不存在,甚至原来一个系专用的教学楼都要考虑参加全校的教室资源统一调整,对高校教务处来说确实是一个艰巨的任务。

而知识经济时代已向我们走来,信息化已经成为社会发展的时代特征。计算机技术、通信技术和现代信息技术的迅速发展,以及管理科学、行为科学和系统科学等相关学科的不断发展,为实现MIS系统提供了坚实的理论与技术基础。建设高校MIS,不仅是时代发展的要求,而且是发展教育事业、提高高校教学管理水平和办学效益的需要。高校MIS是一个庞大的系统,包括方方面面,其中一个重要的子系统就是排课系统。

排课调课是高校教务管理的一项日常工作,由于我国高校的基础建设相对落后,加之近年来大规模的扩招,因而师资和教室资源紧张的问题非常普遍。这项工作靠手工完成一般需要耗费大量的时间和精力,且多易出错。同时手工操作也容易不充分利用资源满足经常变化的需求。如利用计算机进行自动排课,不但能使教务人员从繁杂的排课任务中解脱出来,大大提高教务管理工作效率,而且能改善教学管理质量,合理高效地利用有限的资源。对于推动教学的发展起到非常重要的作用。另外,解决排课问题对于解决其他多约束、大规模的时间表问题也具有重要的指导章义。

1.2 1.2高校排课问题的研究背景

随着Internet技术的日益发展,Web应用的逐渐普及,我院校园网建设的逐步扩展,对我院的教务管理提出了新的要求,要求实现教务的网络化管理；同时教育部1999—2000年提出了实现大学教育学分制的要求,这要求我院更改教学的核心制度,把学年制改为学分制,教务管理是体现教学制度的核心部分,因此必须将我院的教务管理系统由学年制改为学分制、由单机或局域网结构改成Internet结构,通过Web浏览器访问学校的教务管理系统,进行教务管理。

目前我国少数高校在校园网的基础上初步实现了管理的集成化。以计算机和网络通信技术为基础的电子邮件系统、电视会议系统、FTP、BBS、WWW等服务已逐渐深入校园生活。但有些高校的排课工作却仍以手工为主,成为整个高校MIS中极不和谐的一部分。究其原因,有其理论根源。

高校排课问题属于一类涉及多种因素的组合规划问题,它的研究工作己经进行了四十多年,但由于它具有规模大、约束(要求)复杂以及不断变化等特点,该问题一直没有解决好。排课问题要求保证学生、教师、教室不产生矛盾,(两个班级不能同时在同一个教室上课,一个教师不能同时给多个班级上课等)并且要满足教室、教师资源的实际约束条件。早在1975年,Even等人就已证明即使在简让的情沉下,排课问颖仍然是NP完全问题。

1.3 1.3高校排课问题的研究现状

50年代末国外就有人研究课表编排问题。1962年,Gotlieb曾提出一个课表问题的数学模型,此后人们又对课表问题的算法、解的存在性等问题作了很多探索,但大多数文献中用到的数学模型都是Gotlieb的数学模型的简化或补充。

有人把排课问题化成整数规划来解决,但计算量很大,至今没有一个切实可行的算法;还有人试图用图论中的染色问题来求解排课问题,可惜图的染色问题本身也是NP完全问题。由于问题的复杂,许多文章利用启发式函数来解决排课问题,大多数启发式方法都是模拟手工排课的过程来实现的。由于实际的排课问题存在各种各样的限制条件与特殊要求,对这些因素处理的好坏就显得尤为重要。

进入90年代,国外对排课问题的研究仍然非常活跃。如印度Vastapur大学管理学院的Arabinda Tripathy、加拿大Montreal大学的Jean Anbin和JacquesA.Ferland以及Charles Fleutent等。渐曲inda知pathy的工作是针对以“人”为单位进行课表编排的。他运用拉格朗日松弛法和分支定界技术求解,这种方法的缺点是为减少变量的个数,人为造成科目间的冲突。A一Tripathy还研究了研究生课表编排问题,他采用多重课组的方法来处理冲突。(即根据学生选课的矛盾情况,将人数多的课程在一星期内开多次)。Jacques A.Ferland等人则把排课问题分成两个子问题:时间表问题和分组问题。在时间表问题中,根据学生注册情况、教师和教室的可利用情况形成一个主时间表。对于选课人数较多的大课,一星期要分成几个时间段来上,分组问题就是将学生分给各时间段。两个问题相关联,通过惩罚因子来构造启发函数。他们研制的SAPHIR课程调度决策支持系统分为数据处理、自动优化、交互优化等几个模块。该系统解决矛盾的主要方法也是采用多重课组。这与他们西方的教学管理体制是密不可分的。

另外澳大利亚的一批学者还将模拟退火法应用到排课问题的研究中。模拟退火法(Simulated Annealing)是Kirkpatrick等人于1983年首先提出的,它是人们从自然界固体退火过程中得到启发并从中抽象出来的一种随机优化算法。模拟退火法用于求解优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题间的相似性。在对固体物质进行退火处理时,常先将它加温使其粒子可自由运动,以后随着温度的逐渐下降,粒子逐渐形成低能态晶格。若在凝结点附近的温度下降速率足够慢,则固体物质定会形成最低能量的基态,优化问题也存在类似过程。模拟退火法被用来解决许多实际应用中优化问题,取得了不错的效果,但用其来解决排课问题,现在还处在模型试验阶段,还有许多问题要解决。

国内对排课问题的研究开始于80年代初期,所用方法从模拟手工排课到运用人工智能构建专家系统或决策支持系统都有。成型系统早期的有南京工学院的UTSS(A University Timetable Scheduling System),清华大学的TISER (Timetable Schedu1ER),大连理工大学的智能教学组织管理与课程调度系统等。90年代后大连理工大学教学组织管理与课程调度系统的开发人员不断地修改更新该软件,使其功能不断扩大。1992年推出《教学组织管理及课程调度系统》2.01版本和安排考试补考的《考试调度系统》,并把它们合在一起形成了《教学调度系统》,1998年推出了在windows下运行的3.00版本。清华大学计算机与信息管理中心开发的综合教务管理系统是90年代后期一个较全面的高校教学管理系统,其中包括排课系统,但其造价较高。

总的说来国内由于各高校资源的不同、习惯(约束)的差异,排课软件适用性还不够。所以研究高效、灵活的排课系统不但仍有意义而且是迫切的需求。

2 2排课算法研究

2.1 2.1排课中的问题

在高等学校的教务管理工作中,课程表的编排是一项十分复杂、棘手的工作。在排课过程中,除了满足大量的制约条件以外,还必须解决许多冲突与矛盾,例如：两位教师不能同一时间在同一班级上课、一位教师不能在同一时间在两个班级上课等等。学分制下的排课系统的主要任务是把各系或各授课部门的课程申请进行汇总,然后根据教学计划或教学环节制订全校各班级的课表。为了使课表的编排更准确、合理、快速,各高校先后开发出一些适用的排课软件系统。我们发现这些软件有以下不足：

⑴ 一学期的课程、教师、教室信息相对固定,但却不能被重用。

⑵自动排课速度较慢。

⑶冲突现象仍然十分严重,需要大量的手工操作。

这就需要我们开发排课系统软件,以便为教务处的教学管理工作提供更大方便。

2.2 2.1编排课表的注意事项

(1) 设置排课的优先级别。

因受教学场地、教学设施、教师资源匮乏等条件的制约,加之学生、教师、时间、空间等要素关系复杂,为了简化关系,避免诸要素的冲突,根据多年的经验,在编排课程时定义了课程的优先级别,保证了课程编排顺利进行.结合我院二校区办学的实际情况,

其优先级别的设置如下:

①首先安排体育课、外语课、物理实验课、制图课等其它人力、场地、设施、多个教学班共享的公共基础课。

②先排跨系或跨专业上的合班课,后排一个班级的课。

③先排重头课的教师的课,后排单头课的教师的课。

④先排周学时多的课和主要课程的课,后排周学时相对较少和非主要课程的课。

⑤先排外聘教师的课,再排本院教师的课。

⑥先排有特殊情况教师的课,再排其他教师的课.课表初步排好后,与教学执行计划进行认真反复地对照,查看是否有课程漏排;每门课程的间距是否合理、每天课程的轻重是否合理等;结合我院二校区办学,教师资源共享,所以特别是查看教师的时间是否合理尤其重要.例如计算机排课时可能会出现这样的情况:教师第一大节在南院上课,而第二大节要在北院上课,因南北两院相距10多公里,此种方案无法实现,若发现这样的问题应及时调整.因此排课人员的排课经验和技巧尤为重要。

(2) 熟悉和掌握全校教学资源及教学计划。

课程表涉及教师、学生、教学设施及教学课程等要素.课程表的编排实质上就是合理组织教学过程中的时间、空间、人力其组合的合理性,是反映课表编排水平的标志。

为此,课表编制者必须做到:

① 熟悉教学计划内容了解并熟悉全院各系、各专业教学执行计划的全部内容及其特点,掌握每个专业所开设的课程内容、课程性质及总学时数和周学时数了解和掌握各专业教学进程中是否存在前半学期与后半学期松紧不一的情况;掌握全院各专业的实践环节是否交错进行以及理论教学与实践教学的衔接情况。

② 掌握教学设施情况对全院所有教室的个数、各教室的配备情况以及分布情况了如指掌.排课的时侯,应设法使同一门课程排在同一个教室,同一个班级的几门课程排在同一个教室或同一个教学楼内.熟悉其它的教学设备如:多媒体、计算机机房、制图室、画室、实验室、操场、音乐教室、排练厅等各种教学活动场所的可利用情况。只有全面掌握了教学场地及用房的实际情况后,排课时才可能根据课程性质及教学要求进行综合协调,使各种类型的教室达到最大的使用率。

(3) 排课应遵循的原则教学工作是高校经常性的中心工作,而学生在教学工作中居主体地位,是课程表规定和引导教学活动的重要依据,因此课表编制人员树立以学生为本的教育思想和观念是科学合理编制课表的前提。

课表编排来看“学生为本”观念体现在以下几方面:

① 突出学生的主体地位高校的根本任务是培养人才,多从学生的利益出发去思考问题,树立一切为了学生的观点.排课应首先考虑遵从学生认知规律,注意学生学习注意力和大脑调节功能的生理及心理特点;其次要注意专业基础课与公共课搭配排、理论课与实验课搭配排、抽象思维课与形象思维课搭配排、难度大的课与难度小的课搭配排、一课活动与二课活动的搭配排,使学生每天的学习负担平衡,给学生课外学习、作业、自学、娱乐或个人特长的发挥以及创新实践活动留有余地等。

② 充分发挥教师的主导作用教师在教学活动中占主导作用,他的思想状况、身体状况、教学态度、业务水平对教学效果有重要影响.为保证教学效果,调动教师的教学积极性、主动性,挖掘优秀的教学资源,课表编制人员要对全院各系部各类教师数、专业水平、身体状况、可承担教学任务等实际情况做到心中有数.把合班课、重头课和有特殊要求照顾的教师姓名列在一起,在不影响课表合理性的基础上,对这些教师的合理要求作适当考虑,以调动教师积极性,让其在最佳精神状态下完成教学任务。

(4) 优化时间、空间的组合,提高办学效率课表编排对办学效率有重要影响,在充分考虑学生的认知规律和教师的主导作用的前提下,优化时间、空间的组合,提高时间、空间的利用率或周转速度充分挖掘办学资源,是提高办学效益的重要途径.为此可采用时间换空间等方法,提高其效益。

1 1绪 论

1.1 1.1高校排课的意义

1.2 1.2高校排课问题的研究背景

1.3 1.3高校排课问题的研究现状

2 2排课算法研究

2.1 2.1排课中的问题

2.2 2.1编排课表的注意事项

1 1绪论