图论在排课问题中的研究.pdf

前言

这是我本科阶段做的毕业设计,之后不断有网友来邮件或留言询问算法的问题,所以在这里贴

出与大家一起学习,有问题可以搬砖头(呵呵~~~~)

1绪论

1．1课题背景与研究意义

1．2课题的应用领域

1．3课题的现状

1．4解决NP问题的几种算法及其比较

2目前流行的几种排课算法的介绍

2．1.自动排课算法

2．2基于优先级的排课算法

3基于时间片优先级排课算法描述与分析

3．1排课中的基本原则

3．2排课的基本要求

3．3基于时间片优先级排课算法描述

3．4算法分析

1绪论

1.1课题背景与研究意义

排课问题早在70年代就证明是一个NP完全问题，即算法的计算时间是呈指数增长的，这

一论断确立了排课问题的理论深度。对于NP问题完全问题目前在数学上是没有一个通用

的算法能够很好地解决。然而很多NP完全问题目具有很重要的实际意义，例如。大家熟悉

地路由算法就是很典型的一个NP完全问题，路由要在从多的节点中找出最短路径完成信

息的传递。既然都是NP完全问题，那么很多路由算法就可以运用到解决排课问题上，如

Dijkstra算法、节点子树剪枝构造网络最短路径法等等。

目前大家对NP完全问题研究的主要思想是如何降低其计算复杂度。即利用一个近似算法来

代替，力争使得解决问题的时间从指数增长化简到多项式增长。结合到课表问题就是建立

一个合适的现实简约模型，利用该简约模型能够大大降低算法的复杂度，便于程序实现，这

是解决排课问题一个很多的思路。

在高等院校中，培养学生的主要途径是教学。在教学活动中，有一系列管理工作，其中，教

学计划的实施是一个重要的教学环节。每学期管理人员都要整理教学计划，根据教学计划

下达教学任务书，然后根据教学任务书编排课程表。在这些教学调度工作中，既有大量繁琐

的数据整理工作，更有严谨思维的脑力劳动，还要填写大量的表格。因此工作非常繁重。

加之，随着教学改革的进行及“211”工程的实施，新的教育体制对课表的编排提出了更高的

要求。手工排课时，信息的上通下达是极其麻烦的，而采用计算机排课，教学中的信息可

以一目了然，对于优化学生的学习进程，评估每位教师对教学的贡献，领导合理决策等都具

有重要的意义，必将会大大推进教学的良性循环。

1.2课题的应用领域

本课题的研究对开发高校排课系统有指导作用。

排课问题的核心为多维资源的冲突与抢占，对其研究对类似的问题（特别是与时间表有关的

问题：如考试排考场问题、电影院排座问题、航空航线问题）也是个参考。

1.3课题的现状

年代末，国外就有人开始研究课表编排问题。1962年，Gotlieb曾提出了一个课表问题的数

学模型，并利用匈牙利算法解决了三维线性运输问题。次后，人们对课表问题的算法、解

的存在性等问题做了很多深入探讨。但是大多数文献所用的数学模型都是Gotlieb的数学模

型的简化或补充，而至今还没有一个可行的算法来解决课表问题。

近40年来，人们对课表问题的计算机解法做了许多尝试。其中，课表编排的整数规划模型

将问题归结为求一组0-1变量的解，但是其计算量非常大。解决0-1线性优化问题的分支一

定界技术却只适用也规模较小的课表编排，Mihoc和Balas（1965）将课表公式化为一个优

化问题，Krawczk则提出一种线性编程的方法。Junginger将课表问题简化为三维运输问题，

而Tripathy则把课表问题视作整数线性编程问题并提出了大学课表的数学模型。

此外，有些文献试图从图论的角度来求解排课表的问题，但是图的染色问题也是NP完全问

题，只有在极为简单的情况下才可以将课表编排转化为二部图匹配问题，这样的数学模型

与实际相差太远，所以对于大多数学校的课表编排问题来说没有实用价值。

进入九十年代以后，国外对课表问题的研究仍然十分活跃。比较有代表的有印度的Vastapur

大学管理学院的ArabindaTripathy、加拿大Montreal大学的JeanAubin和JacquesFerland

等。目前，解决课表方法的问题有：模拟手工排课法，图论方法，拉格朗日法，二次分配

型法等多种方法。由于课表约束复杂，用数学方法进行描述时往往导致问题规模剧烈增大，

这已经成为应用数学编程解决课表问题的巨大障碍。国外的研究表明，解决大规模课表编

排问题单纯靠数学方法是行不通的，而利用运筹学中分层规划的思想将