在高等院校中,由于其规模大、学科多、课程多、师生比高、校舍资源紧、课程联系密切等特点,使教学调度工作,即教学计划的实施与管理,成为一项非常复杂而又细致的工作,尤以课程表的编制工作更为突出。近年来,由于高校之间的合并,高校办学规模的扩大,以及学科专业的不断细化等因素,使得教学资源的争夺一再紧张,因此,如何编排一张科学、有效的课程表,就成为一项非常有意义的研究。 排课表问题又称时间表问题。排课表问题就是在满足各种要求和限制的前提下,解决对时间和空间资源争夺而引起的冲突。这是一个多因素的优化决策问题,是组合规划中的典型问题。70年代中期,S.Even等人在SIAMJ.COMPUTE杂志上发表题为《关于时间表和杂物流问题的时间复杂性》一文,首次论证了排课表问题是NP-完全问题,将排课表问题理论化。之后很多人尝试采用多种方法对此问题进行求解。但由于排课表问题所涉及的信息较多,并且求解排课表问题最佳解的时间复杂性是课程表规模的指数级,所以对于有一定规模的排课表问题,一般采用的都是求较佳解的算法。 在排课表问题中涉及到班级、教师、上课时间、课程、教室等这五个制约因素。排课表问题的求解过程就是对任何一门课程,寻找一个合适的教师和时间一教室对。在安排时不能发生冲突,同时应尽量满足经验常识。在J.A.Bondy的《Graph theory with applications》一书中对仅有教师和班级两个制约因素的情况进行了讨论,并用边染色理论解决了这一问题。本文将对有教师、班级以及教室三个制约因素时的排课表问题进行讨论,建立了一个特殊的三分图的模型(某两个部分之间没有连线),并将二分图中的匹配推广到特殊三分图中的独立典型路组,对建立的排课表问题模型进行了求解。 本文共分三章,各章的主要内容如下: 第一章为引言,介绍了排课表问题的研究背景、发展概况以及研究现状。 第二章为模型建立与求解。由于排课表问题涉及到多个制约因素,在第二章首先说明了排课表问题可以归结为教师、班级以及教室这三者之间的关系问题。然后建立了一个特殊三分图的模型,并将二分图中的边匹配推广到特殊三分图中的独立典型路组,对建立的模型进行了求解。