排课系统的开发和实现

摘要

要完成一所大学或者一个学院的课程安排是一件非常复杂的问题，如果用人手工进行安排的话，需要极大的精力和时间。而在排课的时候，需要考虑的范围，涉及到教师、课程、教室还有班级情况等等。而在现今的大学排课过程中，整个学校需要考虑的教师，课程信息是成百上千，排课问题由此变为一个异常复杂的组合问题。所以在现实世界的应用中，排课问题的所有排列组合对于人类来说几乎可以被认为是一个天文数字。而一个可以被接受的排课方案是一个满足排课所有制约性要求的方案。在此基础上，如果有人希望能通过一些启发性的设定而得到一个更为优化（更为合理，美观，更为符合人的习惯）的排课方案的话，则这个问题就会变得超乎寻常的困难。所以迄今为止，为了能够用计算机自动完成排课任务已经进行了非常多的尝试。

排课的本质问题是将大量的课程安排进有限的上课时间和教室中，与此同时还会涉及到 任课老师和学生班级等各种因素互相制约的影响。通常来说，排课中涉及的变量越多，则排课问题就会越复杂。而本课题的排课研究涉及的排课环境是上海交通大学的网络学院。

网络学院的排课是排课问题中的一个全新的领域。因为，在网络学院中，教室有了多媒

体，视听等各种新的属性，而这在传统的排课问题中是没有的。而且，网络学院的上课时间也更具多样性。不同的专业，有的每天上午最多只能排4节课，而有的专业却可以安排5节课。时间标准的多样性，教室属性的多样性，使得网络学院的排课问题需要考虑更多的因素，从而给排课提出了更高的要求。

本文所做的研究工作先是比较了一下当今比较流行的集中排课算法，如线性算法、遗传

算法、逻辑(CLP)编程等等算法各自的优缺点和适用性。并且，在此基础上，本文针对网络学院排课更为特殊的要求，提出了一个新的算法。最终，基于本文所提出的这个算法，开发出了一个全新的排课模型，使其不但能适应普通的排课环境，还能够很好地满足网络学院更为特殊的排课要求。

关键词： 远程教育， 排课， 人工智能， 遗传算法，逻辑编程

上海交通大学学士论文 网络学院排课系统的实现

THE CONSTRUCTION OF TIMETABLES FOR SCHOOL COURSES

Abstract

The construction of timetables for universities or schools is an extremely complex problem, whose manual solution requires much effort. The set of all possible solutions, that is the space of the problem, is very large, at least in the real world examples. An acceptable solution is one who satisfies all the problem constraints. The problem goes even more difficult if someone wants to generate an optimum timetable according to some heuristic criteria. Various attempts have been made so far on the automatic solving of the timetabling problem by a computer.

The course-timetabling problem essentially involves the assignment of weekly lectures to time periods and lecture rooms. And generally speaking, the more variable the timetabling has, the more complex it is. Because there are quite a lot of versions of the timetabling problem, differing from one school to the next, we focus on constructing course timetables at our own long-learning school.

The timetabling for our network school is a brand new in the TTP area. In this

problem, the classrooms have attributes such as Multimedia, Video that we never encountered before. Some obstacles like that make the timetabling for the network school a more complex problem and bring a lot of new challenges.

In this paper, some popular TTP algorithms such as Linear, genetic algorithms have been introduced. And according to the especially high demand of the network school, the paper brings a new algorithm and accomplished a new timetabling system. It not only meets the demand of ordinary timetabling problem, but also satisfies the network school’s especially complicated standard.

Keywords: Distance-Learning, time tabling, Artificial Intelligence, genetic algorithms，evolutionary algorithms，Constraint Logic Programming(CLP)

２

上海交通大学学士论文 网络学院排课系统的实现

目录

第一章 绪论 .................................. ５

§1.1 网络教育特点和发展现状 ................................................................................ ５ §1.2 本课题的研究背景........................................................................................... ６

§1.3 本课题的研究目标........................................................................................... ７ §1.4 本课题研究应解决的主要问题 ......................................................................... ７

第二章 排课问题的理论介绍 ..................... ８

§2.1 排课问题的诞生 .............................................................................................. ８ §2.2目前排课问题的几个普遍的算法....................................................................... ９

§2.2.1 Simulated Annealing................................................................................. ９

§2.2.2 Constraint Logic Programming ............................................................... １１ §2.2.3 Graphic Coloring Heuristics ................................................................... １１ §2.2.4 Genetic Algorithms ............................................................................... １２ §2.2.5 Linear Programming.............................................................................. １３ §2.3 小结............................................................................................................. １３

第三章排课问题的要求 ........................ １３

§3.1 对本排课系统的要求 .................................................................................... １３ §3.1目标.............................................................................................................. １４ §3.2排课的基本情况 ............................................................................................ １４

§3.2.1教学任务的划分 .................................................................................. １４ §3.2.2不同教学任务教学时间的安排 ............................................................. １４

§3.2.3排课中按照课程重要性的划分 ............................................................. １４ §3.2.4关于排课时间的概念 ........................................................................... １５ §3.2.5关于中同一门课程的持续时间的安排 ................................................... １５ §3.3排课过程中遇到的各种条件和 ................................................................ １５

§3.3.1排课系统必须满足的条件(hard constraints) ............................................ １６ §3.3.2排课系统会尽量争取满足的条件(soft constraints) .................................. １７ §3.4小结.............................................................................................................. １７

第四章 本课题所做排课系统的实现 .............. １８

§4.1 本排课系统的排课过程................................................................................. １８ §4.2 本排课系统的实现原理................................................................................. １９

§4.2.1 开发工具和前期准备........................................................................... １９ §4.2.2排课系统的基本思路和算法 ................................................................. １９ §4.3 本排课算法的小结........................................................................................ ２６

第五章 本排课系统的使用介绍 ................. ２７

§5.1 信息的输入 .................................................................................................. ２７

§5.1.1教室信息的输入 .................................................................................. ２７ §5.1.2班级信息的输入 .................................................................................. ２８

３

上海交通大学学士论文 网络学院排课系统的实现

§5.1.3课程信息的输入 .................................................................................. ２８ §5.1.4教师信息的输入 .................................................................................. ２９ §5.2课表的生成 ................................................................................................... ３０

第六章 总结和展望 .......................... ３１

§6.1本课题完成的总结......................................................................................... ３１ §6.2对于排课系统的期望 ..................................................................................... ３１

§6.2.1排课系统的架构 .................................................................................. ３２

§6.2.2 use case技术........................................................................................ ３２ §6.2.3 COM/DCOM标准对象模型.................................................................. ３２

致 谢 .................................... ３４ 参考文献与附录： ........................... ３５

４

上海交通大学学士论文 网络学院排课系统的实现

第一章 绪论

随着社会科技的不断发展，特别近20年来在信息技术上所取得的性进步，我们的生活方式也不可避免的不断地受信息技术影响而改变，其中就包括我们长久以来的学习方式。有着长久历史的课堂教学模式，由于有着地域（跨地域的不可行性），时间（时间上的不灵活性）以及资源（合格的教师资源和课堂资源的短缺性）已经渐渐难以胜任现代社会日益增长的全民学习和终身学习的要求了。

而与此同时，信息技术，特别是近年来迅速发展的互联网(INTERNET)为我们带来了一个全新的教育理念——远程教育。

§1.1 网络教育特点和发展现状

网络教育可以是远程教育的一种模式。

远程教育是指位于不同地点的教师和学生通过通信的方式来完成教学任务。远程教育的先驱应该是邮件式的函授教育。通过邮件的函授教育，存在着教育双方的延时非常严重的情况（邮件在两地来回的时间），可谓不是非常的理想。

随着社会技术的不断进步，在上个世纪的二，三十年代出现了基于收音机的广播教育。然后在上世纪的五，六十年代随着电视的普及，又诞生了电视学校。不过，无论是广播还是电视，教学中非常重要的交互性（教师和学生之间的及时互动）以及可回溯性（学生在任何时间想要复习一下以前所学的内容）都由于技术的原因没能很好实现。

值得庆幸的是，随着互联网的飞速发展，远程教育的最新形势，通过互联网Internet或是局域网Intranet的网络教育迅速兴起，并且提供了目前为止作为理想的远程教育方式。 目前的对于网络教育的研究差不多集中在以下两个领域：基于Web的远程教育和实时的远程教育。在基于Web的方式下，教学内容以课间的形式放在Web服务器上，学习者可以在任意时间任意地点地学习，我们称之为以学生为中心的学习模式。而实时的远程教学则主要利用视频会议系统传输视频和音频，购建一种分布式的教室，在这种环境下，教师和学生只是在物理位置上不同，我们称之为面向教师的学习模式。

５

上海交通大学学士论文 网络学院排课系统的实现

在以上两个研究领域中，基于Web的教学模式由于对系统配置无特殊要求，在Internet上应用较为容易。而实时的远程教学模式，由于对传输视频和音频系统有较高要求，同时还要考虑到主教室和分教室之间互相配合的各种情况，运作较复杂，但是由于交互性更好一点，所以在教学的效果上更甚一筹。

所以，在目前的情况下，两种教学模式互相依存，共同发展。比如上海交通大学的网络学院教学模式，现在就以实时的远程教学模式为主，基于Web的教学模式为辅。

§1.2 本课题的研究背景

为了适应这种网络的教育模式，上海交通大学网络教育学院开发了一个非常集成度非常高的电子教务平台。

这个平台所包括的教务管理内容有 1、 排课 2、 注册

3、 学生基本信息统计 4、 成绩管理 5、 毕业资格审查 6、 证书制作、发放 7、 归档

其中，排课的部分又细分为

⑴、 按专业制定教学培养计划（全部课程，包括毕业设计或论文）； ⑵、 按专业制定每学期教学执行计划； ⑶、 按开设的课程聘请（落实）上课教师；

⑷、 根据教学执行计划、学生人数、学生选课地点、教师要求及教室等情况排课；

但是，在电子教务系统中，排课的工作目前仍就是由负责排课的教师手工编排。当学院开设的课程越来越多以后，教师的安排，教室的安排和课程的安排，各种制约条件之间的矛盾会越来越难处理。用手工编排，费时费力费心，还难免会有顾此失彼的情况发生，所以将排课部分由计算机来完成这一工作变的日益重要。

而纵观目前市面上说流行的各种排课系统软件，不是小学版的，就是中学版的，主要原因是中小学的上课安排规律性很强，每次上课人数由一个班级组成，不需要换教室，没有上下学期课程不同之分，每天上课都为早上4节，下午2-3节的固定时间。没有晚上要上课的要求，白天也不会有课时空着等等情况出现。而大学的排课问题就要复杂很多，而且各个大学的教学情况不同，导致对排课的要求也有很大的不一样。所以，目前适合大学排课的软件市面上比较罕见。

而网络教育学院的排课比起普通的大学排课方式，更要麻烦许多。比如，网络学院的教

６

上海交通大学学士论文 网络学院排课系统的实现

室就有多媒体教室，视听教室等等目前普通的大学排课中还没有遇到的问题。而且，在网络学院的授课中，有时还会出现教师在主教室上课，而通过连线的方式，另外有一部分同学在分教室上课的情况。至于是否能进行连线上课，除了要考虑教室的容量和学生的数目，还要考虑所授课程是否适合在不同的教室中连线授课，还要考虑教室的性质是否能符合连线上课在技术上的要求。并且在目前网络学院的教学中，除了普通的本科生教学任务外，还有为了满足社会需求而开设的工程硕士课程，其课程又要求安排在双休日和星期一至星期五的晚上，而且其每个课时的长短，每天上课的课时数又和普通网络学院的本科生有很大不同。所以由此产生的现实是，市面上无数种软件中没有为网络学院的排课所开发的软件。

因此，作为计算机领域的一个经典课题，本文的研究课题，“排课系统”，作为网络教育学院电子教务平台的一个补充，在这样的背景环境下被提了出来。

§1.3 本课题的研究目标

排课系统的本质目标是合理安排一个学期中所有的时段，模块，教室还有教师，使之不互相冲突。由于教室，时间，教师等资源的有限供应性（limited available），由此就意味着排课系统必须有一些必须满足的制约(hard constraints)，从而才能满足特定的条件。

在满足以上排课的硬性要求要求，如教室的不冲突，教师的不冲突，课程的不冲突的目标以后，还应该尽一切可能满足一些不一定必须满足但最好满足得要求(soft constraints) 比如，将主课尽量的安排在上午等等。

最后，在完成上面这些常规排课的要求上，本课题尚需结合上海交通大学网络教育学院的实际情况，比如因为要通过网络上课，对教室有各种性质的要求，最后能够开发出能够满足本校网络教育排课这一特殊要求的排课程序出来。

§1.4 本课题研究应解决的主要问题

（1） 排课问题数学模型的建立。

（2） 排课问题中各种性制约(hard constraints)条件如何满足。 （3） 排课问题中优化条件的如何完成。

（4） 由于排课是一个大规模排列组合的问题，所有得可能性非常大，所以如何对搜索的

规模进行一定的缩小，也是一个非常重要的问题。

７

上海交通大学学士论文 网络学院排课系统的实现

第二章 排课问题的理论介绍

§2.1 排课问题的诞生

最近的30年来，排课(time tabling)受到了越来越大的关注。各种关于排课的文献，理论，方法也层出不穷，并且这种趋势仍有继续下去的迹象。各种关于排课的方法不断更新，很大一部分原因是因为近年来学校教学的方式在不断的改变（比如上海交通大学现在就有了网络教育学院），而排课的方法也必须跟着学校教学方式的改变而不断改变。

每一个学年或是学期，大学的教务管理当局都必须设计出一张全新的课程表，而随着大学教育规模的扩大和教学模式的复杂化，要排出一张理想的课程表成为了一件非常令人头疼的任务。其中让人倍感困惑的就是在排课中有一系列共享资源（比如教室，教师）的课件（modules）引起互相之间的矛盾或说是制约(Constraints)。

以上海交通大学网络学院为例，每一个课件（modules）通常有两个学时或是三个学时构成。在排课的时候，若干互相制约的条件必须被考虑到。比如，不能有两门课（course）在同一时间，在同一教室上课。或者教室的容量比上这门课的同学数量来的小。或者，考虑的更远一点，除了这些必须满足的性条件外，还会有一些希望满足的优化条件，比如一些比较重要的课程，最好能安排在上午完成。为了便于管理，同一专业的英语课程最好能安排在同一时间完成。等等。还有就是，在某些的固定时段，某些课程的教师会有进修的任务或是开会的任务等等，不一而足。总之，也就是，在这些时候，这些教师不能上课，或者说，某些班级的某些课程就不能安排在一周中的这些特定时段。

由于，排课问题是一个比较经典的计算机难题，特别是大学的课程。而我们学校网络学院，由于授课方式的更为灵活，教学手段和途径和传统的授课方式又有所不同，因此，要做这样一个排课的系统就更为困难。所以，迄今为止，绝大多数的课程表都由人手工完成，除了比较费时费力以外，还比较有可能出现一些前后互相矛盾的地方。为此，就算排课问题是一个比较困难的问题，针对我们学校网络学院特殊情况的排课系统还是有开发的必要。

通常来说，一张课程表的完成可以分为的两个步骤

（1） 教学资源的分配，如上课时间，教室，课程等等信息的配置。具体来讲，就是那个

班级要上哪些课程，每个班级的人数，每门课具体的教师的安排，以及这些教师什么时候有空等。结合到网络学院的特殊情况，还必须考虑到上课的教室有没有一些特殊要求，是否允许几个教室之间连线上课等等。

（2） 一个可以接受的课程表的设计实现和完成，所谓可以接受的课程表就是必须满足先

前定义各种性的条件，而且要比较好的满足各种非强制性的期望条件（优化条件）的课程表。

８

上海交通大学学士论文 网络学院排课系统的实现

目前为止来说，由计算机能做的只能是第二个部分的工作，而第一部分的工作通常要排 课的老师输入或决定。而且就长远来说，第一部分的工作计算机估计永远无法完全的由人来完成。

§2.2目前排课问题的几个普遍的算法

作为计算机领域的一个比较经典的问题，排课算法的研究在国内仍然不是非常普遍。有关排课算法的相关资料，国内的材料十分的鲜见。虽然，市面上排课的软件不少，但大多数却是为中，小学开发的，难度也相对较低。

不过，在国际上，有关排课算法的文章相对就较多，而且虽然迄今为止，没有所谓最完美，或者说是最佳的排课算法，但由于所做的研究相当多，所以已经有了较为成熟和理想的排课算法。

以下，就是目前为止，较为常见的几种排课的算法或也可以称之为技术。 §2.2.1 Simulated Annealing

这个算法名字Simulated Annealing [14][20]的中文直译应该是“模拟淬火”算法，不过

我没有看到过相关的中文资料，所以决定还是保留其英文的原名比较好。

Simulated Annealing (SA)算法被广泛应用于处理各种不同组合优化问题，特别是在学

校的排课计划中。其基本的算法描述如下图所示。

９

上海交通大学学士论文 网络学院排课系统的实现

Figure 2.1: The Simulated Annealing Algorithm

SA算法相对其他的一些全局优化技术有优点也有缺点。优点之一是非常容易实现,几乎可以应用到任意一个组合优化问题中去，能为大多数问题提供解决方案，并能与专家系统等启发式方法相结合解决一系列复杂的问题。所以SA是一个比较可靠的技术,不过它的确仍有缺点。为了得到一个好的结果，升级的过程以及各种可调节变量的选取变的非常重要。而且，SA技术比较消耗时间，运行的时候速度比较慢。

最显而易见的将排课问题（Timetabling Problem）映射到Simulated Annealing

Algorithm的构造如下

1. state是一个包含如下集合的课表:

o P: 教师的集合 o C: 班级的集合 o S: 学生的集合 o R: 教室的集合 o I: 时间段的集合.

2. cost 或是 E(P, C, S, R, I)定义如下：

１０

上海交通大学学士论文 网络学院排课系统的实现

o E(P): 是分配超过定额 的课同一位教师所引发冲突的代价，在计划外增

加一门或若干门课在教师的计划中所引起的冲突

o E(C):是将若干门课程安排在同一时间上课引发得不可避免冲突的成本 o E(S):是将不属于某些学生专业的课程安排的这些学生课表中去所引发的矛

盾的成本

o E(R):是将教室分配给不合适（指容量上）班级而引起冲突的成本 o E(I):是课时分配过多或过少所引起冲突的成本

3. swap (move) 是以下一个或多个班级在集合 C中 班级 和 班级 再考虑到时间

段和 ,以及教室 次班级的swapping。 Figure 2.2： Mapping

和

所做的置换。一般来讲，每一个步骤就是指这样的一

§2.2.2 Constraint Logic Programming

Constraint Logic Programming (CLP) [2][17] 是由Logic Programming (LP)结合系统中的操作而成。从而产生的一种新的语言结合了LP 的优点(declarative semantics, non-determinism, relational form) 与解决算法（constraint-solving algorithms）的高效率。

由此，这一语言的优势保障用户无需关心搜索的技术，的声明是明白无误的而且容易修改和扩展。

在逻辑编程的范例中，有关满足的问题可以被写成一个Horn子句的形式，也就是各种性的条件被包含进子句中。而当程序运行的时候，各种相应产生被传递到解决机制中去。而这一机制应用“域”(Domain Independence)满足技术，比如线性程序或者布尔判断等来找到一个可行的解决方案。所以，这种方法仍旧是基于搜索的，不过可以有效的减少搜索范围。

逻辑编程非常适合排课问题。因为它允许所有的公式将明示化。虽然，这个方法的表现会由于排课中的一些小改动而受到极大影响。不过经改动多的排课公式仍能很好的满足各种逻辑条件。

而且由于排课问题本质上是一个大规模的组合问题，所以有一个极为庞大的搜索范围。因此，通过用CLP语言解决这个问题，可以将搜索的范围压缩到一个较小的基础上并能很好的控制住搜索的时间。

§2.2.3 Graphic Coloring Heuristics

Graphic Coloring Heuristics [5]这个算法的基本思想是这样的，假设有S1-S10这是十名学生，他们所选的课程分变为e1-e6中的若干门，如表2.1所示。

１１

上海交通大学学士论文 网络学院排课系统的实现

Student Lecture S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 e1,e2,e3,e6 e1,e2,e3,e5 e1,e2,e3,e5 e1,e2,e5 e4 e4,e5 e2,e4 e2,e4,e6 e3,e4,e6 e3,e4,e6 Table 2.1：Example of Student-Lecture Data

则我们可将他们之间的这种关系映射到下图所示的关系中去。由于，学生S1会选择e1,e2,e3和e6这四门课，所以将e1e2,e1e3,e1e6,e2e3,e2e6,e3e6连起。凡是，同一线段的两端的两门课程就不能在同一时间开设。

Figure 2.3：Graph coloring for a simple timetabling problem

不过，这个算法的用途比较广泛，但有一个比较大的缺点，就是特殊应用的(application-specific constraints)不能很好的整合到这一方法中去。 §2.2.4 Genetic Algorithms

遗传算法Genetic Algorithms或称为进化算法Evolutionary Algorithms [8][10]引起了越来越多的关注。

１２

上海交通大学学士论文 网络学院排课系统的实现

有关遗传算法在排课领域中的应用最早出现于1990左右，由Colorni [53]提出，并随之迅猛发展。在1997年8月举行的国际自动排课会议(PATAT97)上，将近1/4的报告中或多或少的有进化算法的技术。而此前1995举行的会议上，更有近1/3的报告是基于遗传算法。这些数字表示进化算法已经成为一个用来处理一系列较大范围的排课问题的成熟和成功的方法。

遗传算法的理论受启发于达尔文的进化论理论。在遗传算法中，一系列的解决方案(solutions)对于一个特定问题(chromosomes)的表现(performance)被评估(evaluated)和被排序（ordered）,然后选出其中表现较好的解决方案作为双亲（parents），然后在将这些parents进行适当的变异操作(mutation) 或是将两个parents进行交叉组合的操作（crossover operation），由此由这些parents方案产生一个或多个子方案(children).然后这些新产生的方案再次被评估，周而复始，直到有满足条件的方案产生。 §2.2.5 Linear Programming

Linear Programming [21]是对排课问题进行线性求解，通常并不能得到最佳的解。本文的课题的研究，虽然主体上仍旧是基于线性求解的基础之上，但是在求解的时候，有优先级方面的设置和一些改动，所以可以在线性求解的基础上得到一个较佳的可接受的排课方案。

§2.3 小结

排课问题发展到现在的程度，仍旧没有所谓做理想，最完美的排课方案。各种常见的排

课方案，都各有优点和缺点。用一种排课方案，不可能做到非常好地解决所有的排课问题。但是，一个特定的排课环境，有可能可以找到一个较理想的排课方案。

而且，关于排课问题的研究，仍旧在不断深入的研究中。我们现在已经可以用计算机自

动排出一张可以接受得课表了，相信随着我们的努力，我们将来排出的课表一定会越来越人性化。

第三章排课问题的要求

§3.1 对本排课系统的要求

本课题诞生的原因是因为上海交通大学的网络教育学院需要一套适合网络学院多样化

１３

上海交通大学学士论文 网络学院排课系统的实现

教学任务的排课系统，而排课问题又是计算机领域中一个叫经典的问题，正是因为有这样一个契机，所以本文的研究课题就放在了排课问题得研究上，更确切的说，是网络学院的排课问题的研究上。

§3.1目标

本排课系统的目标是能够根据网络学院的教学执行计划、学生人数、学生选课地点、教师要求及教室等情况由计算机智能地排出符合要求的课程表。

在排课过程中，本排课方案必须满足所有的性条件(hard constraints),也就是不

会有冲突的情况出现，同时还会尽最大的努力完成尽可能多的优化性条件（soft constraints）。

§3.2排课的基本情况

§3.2.1教学任务的划分

按照网络学院的授课对象的不同，需要安排的课表有为网络学院全日制本科学生所开的课程，有为专升本的学生所开的课程，还有为工程硕士所开的课程。

而按照这些所开课程的不同，在教学时间的安排上可以分为全日制和业余制两种。其中，

网络学院的本科学生上课时间属于全日制，而专升本的同学，以及工程硕士的同学的上课时间属于业余制。

§3.2.2不同教学任务教学时间的安排

全日制的教学任务安排在周一至周五的白天

业余制的教学任务则安排在周一至周五的晚上，以及周六和周日的全天（白天，晚上） 全日制的上课时间为 上午 4节（最多） 周一至周五

下午 4节（最多） 周一至周五

业余制的上课时间为 上午 5节（最多） 周六和周日

下午 6节（最多） 周六和周日 晚上 4节（最多） 全周

§3.2.3排课中按照课程重要性的划分

按照课程的重要性划分，可将全日制的课程划分为主干课和非主干课之分，并且除此情况外，在重要性上无任何其他的划分标准。

１４

上海交通大学学士论文 网络学院排课系统的实现

同样，业余制的课程也存在主干课和非主干课的区别，并且除此情况外，在重要性上无任何其他的划分标准。 §3.2.4关于排课时间的概念

因为每学期开学的时间（指日历时间,年月日）无法确定。同时，在学期过程中的节假

日换课或停课等情况，也非排课系统事先所能掌控，所以在本排课系统中涉及的时间只有周数，第几周之类的概念，以及某一周中第几天的概念（周一到周七），没有年月日的概念，所以本排课系统是一个基于周概念（weekly）的排课系统。

与此类似的情况是，在排课中预先设定上课的小时和分钟的概念，也不是非常的合理。因为，我们无法保证每天上午，下午还有晚上开始上课的时间，或是每节课的长短，甚至课间的休息时间在将来一定不会变化。所以，如果将小时和分钟排进排课系统的算法中，难免在将来会造成某种程度上的困惑。

另外的一个原因是，全日制和业余制的上课时间，无论是课时长短，还是课间休息的时间都完全不一样。如果，在排课的核心算法思想中，将小时和分钟的单位写入，将无法同时处理全日制和业余制这两种不同的情况。

所以，在本排课系统中每天的课程安排，只有课时的概念，单位是“节”，而没有小时和分钟的概念。在课表安排出来以后，小时和分钟这类的时间概念可有排课老师对应上课的节数灵活的添置上去。

§3.2.5关于中同一门课程的持续时间的安排

根据网络学院排课教师的多年排课经验和要求，每门课的持续上课时间以2节课或者是3节课构成比较合理，极端情况才允许下可能有4节课，但不可能存在只上1节课或者连续上课超过4节课的情况出现。

§3.3排课过程中遇到的各种条件和

排课中必须满足的条件也就是排课中的性条件(hard constraints),如果不能完全

满足这些条件的话，这会引起各种各样的冲突（conflicts），比如同一时间，会出现一个教师要在两个不同的地点（教室）上课的情况，或者同一时间，同一个教室被安排给多个不同的班级上不同的课程。很明显，以上的这些冲突在我们目前认知的三维空间是无法完成的，这样排出来的课表也就是没有意义或价值的

同时，排课的时候还会有一些不是一定需要满足，但是应该尽一切可能完成的条件(soft constraints)，。比如说，要把主干课程安排在上午上课。虽然，违反这一条件不会引起物理意义上的冲突，可以按照这样的课表上课。但是，这样排出的课表不会受到同学和老师的

１５

上海交通大学学士论文 网络学院排课系统的实现

欢迎，是一张非常不科学的课表，所以也是没有什么价值或意义的。

在本课题的研究中，所遇到的必须满足的条件(hard constraints)以及尽量满足的条件(soft constraints)如下。

§3.3.1排课系统必须满足的条件(hard constraints)

以下的条件是一些排课系统默认的，不需要排课教师人工协助设置的，理所当然应该必须满足的条件。

(1) 每个班级每个学期所指定要完成的课目都必须要被安排，也就是不能出现漏排一门课这

类的情况。

(2) 每个班级每个学期所要完成的课目只是被要求完成的课目，也就是不能出现多排一门课

这类的情况。

(3) 每门课程教学所需的课时数必须要被满足，也就是每个班级每周的上课课时*上课的周

数=每门课程的教学课时数。其中要注意的是，国庆假期等放假，停课情况不在排课系统的考虑范围之内。

(4) 同一时间教师的安排不能有冲突，也就是同一个教师不能同一时间在两个地点（教室）

上课，也不可以在同一时间，同一地点，教授两门不同的课程。

(5) 同一时间教室的安排不能有冲突，也就是同一时间同一教室，不能安排两批不同的班级

学不同的课程。

(6) 全日制的教学任务能且只能安排在周一至周五的白天，这里的白天是指上午的4节课和

下午的4节课。

(7) 业余制的教学任务能且只能安排在周一至周五的晚上（4节课），以及周六和周日全天

（上午的4节课和下午的4节课）。

以下的条件由排课的老师人工协助给出，可以认为是排课中各种所需的条件变量。 (1) 每学期课程课时的安排

每学期每门课程的课时有可能会是36学时，48学时或者72学时等等，这些信息需要排课的老师给出。同时，每门课程的开始时间，第几周开始，（因为并不是所有的课程都是第一周开始，由的课程会在期中开始），这些信息均需要由排课的老师给出。

(2) 哪些课程是主干课，哪些课程不是主干课,这些信息同样由排课老师给出，因为计算机

无法通过课程的名字就知道哪些课程更为主干。

(3) 任课老师与课程之间的联系，也即哪门课由哪位老师上，甚至同一专业，同一年级，相

同的课程，如英语课，某个班级的英语课由某位老师上课，都由排课的老师指定，不存在任意的情况。

(4) 某些任课老师因为要进修，开会的关系，有些时间不能来上课，也即由这些任教某些课

程只能安排在一周的一些指定时段中，以上信息也需要由排课的老师给出。

(5) 某些课程必须在有特定功能的教室上课，如多媒体教室，视听教室，机房等。每门课程

１６

上海交通大学学士论文 网络学院排课系统的实现

所需教室功能的信息由排课老师给出。默认情况下，任何课程都需要在多媒体教室完成。 (6) 一同上课的班级由排课老师给定。教室的容量不能小于上课的学生数。特别需要注意的

是，对于非主干课程，可以在多个多媒体教室联网上课。而主干课程必须在同一个教室完成。而如果上的是选修课的话，因为上选修课的人数和可能选修这门课程的班级相加的人数不一定相同，所以排课的老师还需要给出实际选上这门课的同学的人数。 (7) 几个班级合并上课的问题。几个不同的班级，由同一个教师上的相同课程，这几个班级

是否可以或必须合并在一起上（即同一时间，同一地点）的问题，由排课老师做出决定 。 (8) 由于业余制有校外的教室，当主教室排课时间与校外教室使用有冲突的时候，能灵活的

改变主教室的排课时间。（也就是能告知修改过的课程表是否有冲突） §3.3.2排课系统会尽量争取满足的条件(soft constraints)

(1) 主干课尽量安排在上午完成。

(2) 同一专业的英语课尽量安排在同一时间位置一起上，如同一专业有4个班级，则最好前

两节课1，2班并上，后两节课3，4班并上。 (3) 同一门课程在一周中的相隔时间希望至少相隔两天。 (4) 尽量优先使用网络学院的教室。

(5) “大学英语”课尽量安排在视听教室上。 (6) 体育课尽量安排在3，4节课上。 (7) 周三的下午尽量不排课。

§3.4小结

以上的各种性条件，不论是必须完成的性条件(hard constraints)，还是应尽量争取满足的条件(soft constraints)，都是在与网络学院的排课教师多次反复的磋商后得到的结果。而需要排课老师协助完成的那些条件变量，则是在开发这个排课系统中不断遇到问题的解决。

比如，本来“几个班级合并上课的问题。几个不同的班级，由同一个教师上的相同课程，这几个班级是否可以或必须合并在一起上（即同一时间，同一地点）的问题，由排课老师做出决定。”这一点我并没有想到，但是在开发的时候，就发现做不下去了，因为在这种两可的情况下，会让计算机很难“做人”的，所以这个问题只能交由排课的老师完成。

而且，在上面的所有条件中，可以看出，所谓的必须完成的性条件(hard constraints)是绝大多数排课系统都要完成的。而在应尽量争取满足的条件(soft constraints)部分，则每个学校和学院的差别就很大了。

１７

上海交通大学学士论文 网络学院排课系统的实现

第四章 本课题所做排课系统的实现

§4.1 本排课系统的排课过程

如图4.1所示，排课的时候首先由排课老师从教务处取得详细的课程设置，包括所有专业的课程目录，课时数，课程开始的时间，那些是主干课，哪些不是，每周上课的次数，对该课程的具体要求等等，以及可以用来上课的教室的信息。

然后，排课老师向任课的老师发出请求时间表，也就是询问任课老师什么时候可以来上课，什么时候没空不能来上课。

最后，如果有选修课的话，排课的老师还要统计每门选修课的实际人数。

等以上准备工作都完成以后，排课的老师则将以上的规则整理，输入排课系统。同时，

加上各种排课规则优先顺序和一部分性条件。交由排课系统来尝试排课。

Figure 4.1: 排课的过程

由于，资源的有限性和性条件的作用，交由排课系统的信息有可能存在互相矛盾的地方，也就是没有办法排出一张课表。

如果遇到这种情况，则需要排课的老师与任课的老师相互协商，或是在各门课程中相互协商，以避开矛盾或冲突。如果，最后协商无效，则只能由排课老师强制调节冲突，也就是取消或削弱一些原来强制完成的性条件。

有的问题协商也不一定能解决，比如资源的明显不够。比如，教师人数的不够，还有就是教室数量的不足，大小不够等问题。遇到这些问题，只能由排课的老师向学校再去申请新的教学资源，例如，要求增加更多的老师和教室等等。否则的话，排课系统肯定是为力的。

等所有的条件可以满足后，排课系统自动排列出符合所有性条件(hard constrains)

１８

上海交通大学学士论文 网络学院排课系统的实现

和最大可能满足优化条件(soft constraints)的课程表。然后，再进行打印，就可以得到网络学院新学期的所有班级的课表了。

§4.2 本排课系统的实现原理

§4.2.1 开发工具和前期准备

本课题所做排课系统的核心开发是用标准C语言完成的。界面的完成是用到了微软的MFC。用C语言做核心的原因一个是因为排课系统是一个NP复杂度的问题，对时间的开销很大。C语言的效率较高，可以有一个较快的速度。另外一个比较重要的原因是，开发排课系统前，由于缺少相关的资料，我并没有百分百的信心可以做出一个排课系统。在这样的情况下，我希望能够先用较熟悉的C语言做出一个实验的版本出来，主要是先看一看我的想法和算法是否正确。否则的话，关键问题错误，其他的问题就根本谈不上了。

§4.2.2排课系统的基本思路和算法

§4.2.2.1排课的几个核心函数 (1) Input函数 (2) Comp函数 (3) Ready函数 (4) Calc函数 (5) Add函数 (6) Del函数

§4.2.2.2排课的流程和各函数的作用

排课的第一步，是由排课的老师在视窗界面中，

输入排课的所需的各项信息。包括有教室的信息，教师的信息，课程的信息，班级的信息，还有各种优化性条件。等排课所需的所有信息输入完毕后，界面的处理函数将以上信息打包成规范化的形式，写入输入文件lecture.in。 Input函数的介绍

Input函数将处理是lecture.in的信息。在Input函数中，要处理的事情主要有三件。首先是要生成一个教师的表格和一个教室的表格。这些表格用来纪录在一周中的时间内，教师或是教室在哪些时候有空。Input函数根据输入的信息，需要将老师不能上课的时间以及

１９

上海交通大学学士论文 网络学院排课系统的实现

教室不能开放的时间填出来。

Input中做的第二件事是“减数”。所谓的“减数”是这样的，某些课程在一周的时间中，要上两次或是三次。这样的直接排课的话，会比较麻烦。通过减数，将这些课拆成完全相同性质的两门课或是三门课（术语应该是Item）。这样在减数以后，在排课的时候，所有的“课程”都是一周只上一次，相对来说考虑起来就比较容易的。

Input中做的另外一件比较重要的事情是周数的合并。其实做不做周数的合并，并不会影响算法的正确与否。做周数合并只是为了提高算法的运行效率。因为，在周数合并之前，比如说，一个学期有18周，则在排课的时候需要考虑这18周的情况。如果一个教室第一周是有空的，那么它第二周是否有空哪，第三周又如何哪？以此类推，要考虑总共18周的情况。可是，如果这18周的情况完全相同的话，我们就可以将这18周合并起来，就当成一周的情况来考虑。这样，算法执行的速度可以至少提高18倍。 当然周数的合并也是有一定条件的。

如图4.3所示的课程甲和课程乙的情况，课程甲的时间跨度就可以从第1周到第9周压缩为“1周”考虑，而课程乙的时间跨度就可以从第10周到第18周压缩为第“2周”。因为可以证明，当一门课程结束的时候，另一门课程还没有开始，则这两门课程无论怎么安排， 教室的安排或是教师的安排，都不会影响到另外一门课。

Figure 4.3: 周数合并的情况一

而如图4.4的情况，课程甲和课程乙有一段冲突的时间。则课程甲和课程乙在周数上就无法合并了。因为，课程甲在第一周的时候，某个时候某个教室空着，并不代表在第十周这个时候这个教室仍旧空着。因为课程乙有可能在第十周的这个时候会用这个教室。所以，到第十周的时候，一个很严重的冲突就发生了，两门课程在同一时间用了同一个教室。这是不能允许的错误。所以，很显然，在这种情况下，课程甲和课程乙的周数都无法压缩或说是将周数合并。

２０

上海交通大学学士论文 网络学院排课系统的实现

Figure 4.4: 周数合并的情况二

另外一种情况是像上图所示，课程甲的长度整个跨过课程乙。则这个时候仍旧可以进行周数的合并。因为在课程乙虽然先结束，但对课程甲不造成任何影响。所以，我们可以假设课程乙的长度和课程甲相当。然后，进行周数的压缩。当然，在课程乙实际结束后，课程乙曾经占用的资源会释放出来，但幸运的是，多出来的资源不会造成任何的冲突。

Figure 4.5: 周数合并的情况三

在Input函数即将完成的时候，最后调用了qsort函数。qsort函数是C语言的标准排序函数，排序的标准由Comp函数参数决定。

所以，Comp函数的内容其实是本排课系统的默认优先集的设定。 在Comp函数中，总共有5个判断函数。

第一个判断函数的作用是将主干课排在前面。因为，在课程输入的时候，每门课程都有一定的属性，像主干课，非主干课，英语课，非英语课，等等。所以，这一标准就是将课程中有主干课属性的放在前面，当都是主干课在比较时，就将有英语课属性的放在前面等等。

第二个判断函数的作用是将课时多的课程放在前面。所谓课时多的课，就是每次上课要连续上3节或是4节的课程，因为我发现这样的课程往往比较难排。所以，有必要将他们提到比较前面一点，先进行安排。

第三个判断函数的作用，是将选择这门课班级人数多的排在前面。因为，上课的人多，意味着相应的教室要比较大，这也是一个相对来说较苛刻的条件，所以有必要先将他们安排好。

第三，第四个函数做的事情是这样的。因为，我们先前将一周内要上几次的课程都拆分开来了，认为他们是几门不同的“课程”。但是，很明显，他们的课程属性完全一样，也就是他们的优先级应该完全一样。在这种情况下，我希望在排序的时候，这些有原来一门课出来的课程都能在队列中紧邻的排列。

这样我就有必要判断哪些“课程”是由原先同一门课程出来的，哪些不是。所以我要做以下两个判断。

一．课程的名称是否一样。 二．上课的班级是否一样。

如果，以上两点完全相同的话，则我们有理由认为这样的两门课就是原先由同一门课程

２１

上海交通大学学士论文 网络学院排课系统的实现

出来的，所以应该在排序的时候紧邻。

完成第一次安Comp标准做的qsort以后，所有要排的“课程”(Item)已经按照较理想的优先级排列成一个队列了。以后，排课的时候，大致尝试在课表中插入课程的顺序就是按照这样的一个队列的顺序。

Ready函数的介绍

在以上的一些Input函数做的一些预处理完成以后，就进入Ready函数。严格意义上讲，Ready函数仍旧是一个预处理的函数。与以上Input函数所做的预处理稍有不同的是，以上的工作只在排课开始的时候做一次。而Ready函数有可能需要在排课过程中进行多次。比如，当一个排课方案不理想，超过规定的搜索次数需要重做的时候，则Ready函数需要被再次调用。

Ready函数中主要完成两件事情，第一件事情是计算本课程可以开始的时间点。所谓课程可以开始的时间点，是这样的。比如，某门课程每次要上3节课，则在上午4节课，下午4节课的正常情况下，这门课只能从上午的1，2节课开始，或是下午的1，2节课开始。又由于，所有的课程持续时间不少于两节课，则从上午的第2节课和下午的第2节课开始其实是没有意义的。因为，第一节课的资源，教室也好，教师也好，肯定都要空着，没有办法有效利用。所以，在这种情况下，这门课程的开始点一周其实是10个，分别为星期一到星期五上午的第一节课和下午的第一节课。如果，有一门课每次上2节课，则这么课的开始点就有20个，分别为星期一到星期五上午的第一，三节课和下午的第一，三节课。

所以，在Ready中第一件事情是计算每门课的开始点有多少和这些开始点在哪里。

Ready中的第二件事情是纪录每门课的关系课程。

所谓的关系课程是指，在同一时间段中，如果课程甲和课程乙中出现以下两种情况之一种以上

一．课程甲和课程乙由同一位老师任教 二．选修课程甲和课程乙的班级有雷同

这样非常明显的是，在同一时间，课程甲和课程乙绝对不可以同时上课。因为，这样势必会引起冲突。做好这样的预处理，在做排课搜索的时候，就可以只考虑教室的冲突情况。 在做关系课程的时候，我用的是邻接表。

事实上，关系课程的表示也可以用0，1的邻接矩阵来表示。但这样的一个矩阵势必是一个稀疏矩阵，同时，在搜索某门课程的关系课程时明显不如用邻接表来的快。所以，用邻接表显得要更好一点。

需要指出的是，在邻接表中，记载的关系课程其实只有在队列中排在本课程后面的关系课程。因为，在队列中排在本课程前面的关系课程都已经排好了，在排本课程的时候，就不需要多“费心”了。

２２

上海交通大学学士论文 网络学院排课系统的实现

Calc函数的介绍

Calc函数的作用是递归的排课。在队列中的课程按照先后顺序被Calc函数调用，然后在自己排好以后，在调用队列中排在本课程后面的一门课程。

Calc函数具体的算法是这样的，尝试着将本课程加入课表中，由于本课程的开始点大于零时才会被调用，所以本课程总可以加入课表。在本课程加入课表以后，要调用Add函数，因为本课的加入，影响了与本课程有关系的课程的加入点，所以需要Add函数来修正。 但本课程加入课表以后，会有两种可能， 一．

本课程加入以后，经Add函数调整后的所有关系课程的开始点还是大于0，则表示

本课程加入以后，后续的课程还是有可能可以安排进来。当然，这里仅仅是可能，是不是最后一定可以加入，现在无法得知，只是表示目前用的排法还有希望，可以再继续尝试下去。 二．

还有的一种可能就是，在本课程加入课表以后，经过Add函数调整以后，有一些课

程的开始点已经为0了。这就表示后面的课无论怎么排，开始点为0的这门课肯定排不进课表了，所以现在就可以停止了。说明，本课程排在课表目前的位置是不正确的，需要换个位置，继续尝试。

在第一种情况下，本课程的排课已经完成了，可以递归的调用下一门课程了。而在第二种情况下，本课程需要在当前的位置回溯出去，需要调用Del函数将先前Add函数修改掉的本课程的关系课程的开始点信息改回来。但是，需要将先前开始点为零的那些关系课程的bad属性（在程序中用fcount记录）加1。所谓bad属性，就是某些课程阻碍其他课程顺利安排的次数。像本课程就是被它的关系课程阻碍，而不能排进当前位置，所以这些课程的bad属性需要加1。

然后，如果本课程有两个以上开始点的话，还需尝试其他开始点的情况。

最后的情况，无非是本课程被顺利的排进了课表，或是没有被排进课表。如果，本课程被顺利地排进了课表，则继续排下面的课程。如果，没有被排进课表，则说明是本课程比较难排，是一个“麻烦制造者”（trouble maker），则要将本课程的bad属性加1。

当然，这里具体要加多少可以再进行调整，有可能加1显得太少了。 Calc函数是一个递归的函数。所以，Calc函数的最终结束有两个可能。 一．队列中所有的课程都被成功的排入课表，排课结束。

二．递归的过程过深，超过了规定的最大递归次数(调用Calc函数的次数)，也就是程序中

MAXTRY的值。因为排课问题的复杂度非常大，如果递归次数过大的话，程序会很长时间的不到响应，而且最后还不一定能将课表排出。所以，有必要设置一个最大的递归调用次数，以免陷的太深，难以自拔。

当然，如果Calc因为遇到MAXTRY的上限而退出的话，则直接从Calc函数的递归中跳

２３

上海交通大学学士论文 网络学院排课系统的实现

出，这也就意味着在此前的所有的Add函数的Del函数没有来得及做，所以有必要将Ready函数重新应用一边。

而且，在从Calc函数跳出后，也说明当前的优先队列有问题，无法在规定时间(MAXTRY)

完成排课的任务，所以需要调整排课系统的优先队列。

对排课系统优先队列的调整是这样的，就是将所有课目中bad属性最高（fcount值最

大）的那个课程放到优先队列的最前面。因为，显然bad属性最高的这门课是比较难排的，不是自己排不进，就是会给其它课程造成很大麻烦。

我这样调整课程队列的优先次序，是基于所谓的“书桌”理论。也就是说，如果一个书

桌非常的杂乱，没有整理过，则这样的杂乱其实也是很有效率的。因为，通常来说，在杂乱书桌上，最常用的会在最上面，而常用度几乎是从上到下一次递减。

所以，我将bad属性最高的放在优先队列的最前面，就是基于这种思想。也就是，将与

其他课程牵连最多的，最难排的课程，现安排好。

Add函数和Del函数的介绍

因为在calc函数中，将一门课程安排进课表，势必引起这门课后面的一些关系课程的开始点的变化，同时也将引起剩下可提供教室信息的变化等等情况。所以，这时候，就需要Add函数将这些信息改变掉。

而Del函数的作用真好与Add函数相反，就是将这些Add函数改动过的信息改回来。因为，Add函数在递归中用到，当需要回溯的时候，就需要调用Del函数。就像栈中push函数和pop函数一样。

需要注意的是，如果Add函数在做到一半，就发现后面一些相关课程的开始点为零了，则Add函数仍旧继续做下去。因为这时候，如果退回去，会很麻烦，就需要HalfDel函数了。所以，索性等Add函数整个完成，再调用Del函数,这样仍旧可以将修改到一半的信息恢复过来，而且过程很清楚。

§4.2.2.2 本排课系统中一些优化条件的处理

除了必须要满足的性条件外(hard constraints)，排课中另外一个很关键的问题就

是优化条件(soft constraints)的处理了。

在网络学院排课中，最关键的一个优化就是尽量要将主干课程安排在上午完成，而将非

主干课程安排在下午完成。

对于，这个问题的处理，我是这样做的。

首先，设置如下的两个三维数组。（见Figure 4.6和Figure 4.7）

２４

上海交通大学学士论文 网络学院排课系统的实现

Figure 4.6: 主干课的搜索路径

三维数组中，第三维数组的值表示的其实是上课的时间安排。第三维数组中的第一位表示的是星期几，第二位值表示的是上午，下午还是晚上。第三位值表示的是每个时间段的第几节课。比如(3,1,2)就代表的是星期四的下午的第三节课（注意，实际代表值是括号内值加1）。等等，以此类推。

而这张三维表格明显分为两个大部分，两个大部分又分为四个小部分。其中，第一个大本分是全日制课程的搜索路径。第二个大部分是业余制课程的搜索路径。

再仔细研究一下Figure 4.6，就可以看出像(0,0,0),(2,0,0)等排在最前面，而它们代表的上课时间是星期一的上午第一节课，星期三的上午第一节课等最佳的上课时间。由此可见，Figure 4.6中的三维数组是被用来作为主干课程的搜索路径来用的。

而事实也的确是这样。在Calc函数中，课程做搜索的时候，就是沿着这样的一个路径，从三维表格的第一项，搜索到最后一项，直到发现尚有空余的空间可以填进去。

而且，在这个三维数组中，（0,0,0）和(1,0,0)这样的比邻天数的上课时间是交叉开来写的，这是为了让课程在搜索的时候，同一门课在一周中的两次上课时间可以不要相隔时间太近。

同样，Figure 4.7 是非主干课程的搜索路径。

２５

上海交通大学学士论文 网络学院排课系统的实现

Figure 4.7: 非主干课的搜索路径

除了主干课程的优化以外，本排课系统中还要求有英语课程的优化，即同一专业的英语

课尽量安排在一起上。

对于这个问题，我的做法比较简单。就是在排英语课程的时候，先判断一下是否已经有

相同专业的英语课排好了。如果是的话，就尝试安排当前的英语课排在先前已经排好的时间位置上。如果不是的话，就将它当成普通的课程来安排。

当然，这样的做法太简单，有时候不能很有效的将同一专业所有的英语课程安排在一个

时间段上课。

§4.3 本排课算法的小结

本课题排课的算法其实是我在接触到相关的资料前，自己想出来的。所以，如果说有什么好的地方的话，我想应该是比较有想象力，毕竟是原创的，和别人的做法有一点不一样。当然，成也箫何，败也箫何。正由于我在做这个排课系统之前，没有接触到一些成熟和成功的排课算法和方法，缺少了一个学习和在学习的基础上发展的机会，所以我的算法其实相当的原始，有许多不尽合理的地方。比如在排出一张可行(feasible)的课表基础上，比较理想的做法是可以考虑应用遗传算法将那些排的相对最不合理的课程强制安排放在比较一个合理的位置上，然后再不断进行交叉进化，最后得到一张相当理想的课表。

２６

上海交通大学学士论文 网络学院排课系统的实现

还有一点我的排课系统做的比较简陋的是，在对教室进行深度搜索的时候，我只考虑了教室的大小一项属性。当然，如果教室只有大小这一个属性的话，则这样的考虑是完全正确的。但问题是，网络学院的教室和普通的教室不一样，它有很多的属性，比如多媒体(M),视听(V)还有机房（C）。这样的话，因为我没有考虑其它的几项属性，所以搜索的时候，无法保证教室的选择是很正确的。造成的后果是，造成原来有可能可以获得安排的课程由于所需的教室被其它的课程事先用掉，而无法获得安排。当然，如果考虑教室的属性的话，则时间的复杂性就又会提升。

总之，本课题的这个算法虽然是一个可行的算法，而且经过了实验的证明，但确实不够

精细，有一些可以改进的地方。不过，排课问题的确是一个比较难的题目，要做的好很不容易。

第五章 本排课系统的使用介绍

§5.1 信息的输入

§5.1.1教室信息的输入

如图5.1,需要输入的教室的信息有，教室名，教室的大小和教室的性质（多媒体，视听还是机房），其中多媒体是教室性质的默认属性。在输完一个教室的信息以后，排课老师可以继续的输入下一个教室的信息，或是返回前一个教室信息处进行修改，也或是直接按“输入完毕”完成教室信息的输入。

Figure 5.1 教室信息的输入界面

２７

上海交通大学学士论文 网络学院排课系统的实现

§5.1.2班级信息的输入

如图5.2，需要输入的信息有班级所属学院的名称，所属系的名称，班级的代号还有就是班级的人数。其中，班级的人数在做排课的时候会与教室的大小进行比较，如果整个班级都参加所选的课程，则认为在这个教室中的人数就是班级的人数（或几个班级人数的和）。但如果遇到选修课的情况，某些课程并非一个班级中所有人都参加，则在课程的输入时需要再输入实际的上课人数。

Figure 5.2 班级信息的输入界面 §5.1.3课程信息的输入

如图5.3，需要输入的信息有课程的名字，学期的课时数，每周上课的次数，每次上课的节数，还有就是课程开始的周数。显然，通过以上这些信息，排课系统可以非常容易的算出学期的周数。

当然，如果在以上的信息输入时，不小心输入错误，则排课系统并没有这个能力自动将错误发现并修改。只有排课的老师通过前进和后退操作来进行检查，修改和确保输入信息的正确性。

除了以上需要输入的信息，还要求输入的有这门课程对教室的要求。比如，英语课就要就在视听教室上，而计算机实验就必须要求机房。在默认情况下，所有的课程都要求在多媒体教室完成。

除此以外，每门课程的信息中还要包括这门课是否为主干课的信息。同时，由于排课的老师要求将英语课的上课时间尽量排在一起，并行排列，则排课系统还需知道这门课是否为英语课，以便在排课的时候做优化。

２８

上海交通大学学士论文 网络学院排课系统的实现

Figure 5.3 课程信息的输入界面 §5.1.4教师信息的输入

教师信息的输入有两种不同的情况。图5.4是全日制的教师信息表。可以看见，除了教师的姓名需要填入以外，还需要标记哪些时段教师有事不能来上课。选中特定的多选按钮，代表该课时的时候，该教师无法来上课。比如，下图表示，华罗庚老师在星期二的上午1到4节课，以及星期四的下午1到4节课有事不能上课。默认情况是，所有多选按钮都未被选中，也即在星期一上午到星期五的下午，老师都可以来上课(available)。

２９

上海交通大学学士论文 网络学院排课系统的实现

Figure 5.4 全日制课程教师信息的输入界面

图5.5是业余制的老师用的。其和全日制教师信息输入的区别就是上课的时间不同而已。全日制是上星期一到星期五的白天，而业余制是上星期一到星期五的晚上和星期六和星期天的整天。

Figure 5.5 业余制课程教师信息的输入界面

§5.2课表的生成

待所有的信息正确无误的输入完成后，只要在菜单栏中选择“生成课表”选项，则排课

系统将自动按照先前输入的信息和规则进行排课。

由于，排课的复杂度比较大，所以有可能系统响应的时间会比较慢一点。

当排课系统将可行的课表排出以后，则自动按照班级作为单位进行存档，保存为课表文

件。

３０

上海交通大学学士论文 网络学院排课系统的实现

第六章 总结和展望

§6.1本课题完成的总结

排课系统可以节省大量的人力资源已经在各文献上获得证实。而从本课题完成后所实验的情况来看，也的确是如此。

本课题由于是针对上海交通大学网络教育学院的要求所做的开发，所以对于网络学院的要求能够较贴切的完成。可以方便，快速，准确的排出一张较理想的课表。

但同时，本课题的研究还存在很多不足的地方。首先是，由于中文排课问题的资料非常的匮乏，所以我在开始做排课系统的时候，完全是基于自己的想法和构思来开发这个系统。虽然，由于这个原因，我的想法虽然比较新颖，与别人的做法不雷同，但是因为我对排课问题是从零开始研究，基础很低，所以我的这个排课算法也的确比较原始。

虽然，现在的这个排课方法是一个可接受的方法，但明显不是一个最佳的方法。因为，如果不考虑效率的话，最理想的课表，其实还是人手工排出来的课表。事实上，这样的课表才能够达到最“美观”的效果，所以理想的排课方法也应该是模拟人类的排课方式来进行排课。而我所采用的方法，虽然有各种的优先级，但本质上仍是一个基于线性的排课方法。所以，难以做到像人类手工排出来课表那样的“漂亮，整齐”。

而且，在我一开始做排课系统时，还曾经想过要做一个提示的功能。就是在排不出来的情况下，可以告诉排课的老师，哪里是瓶颈，或是将哪个条件削弱一点点，问题就可以解决了。但是在做到后来，发现要完成这样一个提示，对于排课系统的人工智能的要求实在是比较高的。所以，最后没能够完成这样一个任务，感到比较的遗憾。

总之，排课问题并不是一个非常简单的问题，但是一个和有意思的问题。如果后来的同学有机会继续作这个课题的话，我希望后来的同学能够先多了解一下国外现在的一些比较成熟和成功的方法，然后再去结合实际情况开发，我想这样做出来的产品应该会比我完全自己闭门造车来的好。

§6.2对于排课系统的期望

上面的部分，对于排课的算法讲的比较多。其实，在做排课系统的时候，我的另外一个遗憾是没能将这个排课系统做成一个基于网络的排课系统。

我校的网络教育学院已经有了一个很好的教务管理平台，包括选课系统，成绩管理系统等几个部分。用到排课系统的用户虽然不多，有可能只有排课的老师而已，单机版的排课系统虽然可以被接受，但是因为排课问题的解决和教务管理平台有一个紧密的联系，所以如果把这个排课开发为能够通过校园网络使用的系统应该会更好。因为我们所希望的不仅仅是教务处工作的自动化，而是整个网络学院整体工作的自动化。

３１

上海交通大学学士论文 网络学院排课系统的实现

虽然，我由于时间和能力的关系，最终没有能完成Internet上的排课系统的设计，但是基于网络的排课系统，应该会表现的更好一点，所以我还是希望对Internet上排课系统的设计以及与网络学院教务平台的整合提出一些自己的期待。 §6.2.1排课系统的架构

在系统的架构必须考虑现有的软件的开发平台和硬件设备。目前，在网络学院的电子教务平台是三层的主从架构。考虑到已开发软件和人员对这一平台的熟悉度，我觉得排课系统也应架设在三层式架构下。

排课系统需要一个弹性变更与网络环境。所以可以通过对象导向技术针对现行排课系统来解决排课系统所需的弹性变更问题，同时结合COM技术在INTERNET上建置一个实务应用。 §6.2.2 use case技术

整合模式语言(Unified Model Language)表现了对象导向所注重的程序，它采用的软件开发程序=使用案例导向(use case driven)+系统主架构(architecture- centered)+螺旋式(interactive)+渐增式(incremental)。但为了不同环境对发展程序的不同策略，UML与发展程序又分开以求使用者和研究者有较大的自由空间，所以在不同的开发程序下仍然使用相同的模式语言来表达与沟通。

UML让企业信息人员有一个共通一致的表达方式来作为信息系统的蓝图。并藉由一致的设计理念去完成容易互相沟通、互相协调，而让大家接受的系统架构。而use case 就定义出com组件所应提供的服务，透过其表达出系统的外部观点。最完美时我们所创造的COM组件能完全迎合使用者对系统的期望。 §6.2.3 COM/DCOM标准对象模型

COM提供了一些标准的定义来规定对象间如何通讯与分享资料，使得组件能透过标准或自订的COM的接口来沟通 更因为COM是一个Binary interface使得任何的程序语言都可以用来发展COM的系统，透过对象的标准化模型加速了组件式架构系统的开发—这尤其有助于Multi - tier solution之发展。

透过对象发展模型，可以毫不费力的移植到PC平台上继续使用，不管是在内部的AP或外购的AP上引用这个模块。这个关键就在于清楚定义接口而非结构的优点上。 由以上例子可知COM的二个特性：

1. 于程序语言-所以可以用任何支持Active x的工具。 2. 于应用软件-透过完善的interface重复使用于不同环境。

３２

上海交通大学学士论文 网络学院排课系统的实现

在如火如荼的对象导向研究中，在同一系统内C++无疑是一个相当严紧的对象处理与开发工具，但却没有定义如何与外界的对象做交换和存取，COM看来似乎解决了这个问题。 COM的优点对于不同的对象有

1. 对企业而言:维护成本随着弹性的增加而降低其教育训练与学习成本。管理成本也随

着组件化和DCOM的制订而降低。面对程序开发者的异动，采用组件导向得以在公司的系统受到最小的影响。

2. 对开发者而言:程序设计者可以使用不同的工具去开发一套系统，不用过度迁就开发

软件。技术经理可以依据系统不同部份的需求采取不同的开发软件。比如使用FoxPro开发语音部份，采用Visual Basic发展整合部份。

3. 对市场而言: 象征着软件组件可以自由买卖朝向积木式的开发模式可以获得工业化

的生产。一方面可以增进软件的可靠度；一方面可以增进开发速度与弹性。如此一来客户可以更自由的制订他们所需的系统规格，不用受限于软件包的工作流程与自行开发的昂贵成本。

由于透过阶段式的发展模式，在每一个实施阶段都可以获得与使用者的最佳响应。在第一阶段时我们获得使用者对于输入处理接口的意见，并随即在WEB上进行修正。第二阶段的自动排课系统我们可以先摒除排课协商的。原因有二。第一、相关课程的协商应先保障本系学生的最大利益后再进行两系间的协调。第二、先省略协商问题有助于将排课阶段的规则与流程进行最基础的事件分析与建立互动关系。虽省略排课协商却能可以透过自动排课中所隐含的排课调整获得可接受的结果。第三阶段的工作在于假设第二阶段的排课结果无法满足时需取得数据库资料进行协商。第四阶段则在发展VIEW自动存取数据库的资料到WEB上。以及相关的排课信息都可获得查询。下图是这个系统的循环开发模式、对象导向分析的诸多工具中以use case做为COM设计的基础。

Figure 6.1：排课系统发展模式

３３

上海交通大学学士论文 网络学院排课系统的实现

致 谢

首先，要感谢申瑞民教授给我在网络学院做毕业实习的机会，正是由于这样的机缘，我才得以有机会做排课问题得研究。

本文的研究工作是在申老师的悉心指导下完成的。在做排课系统的过程中，申老师给了我很多的关心和帮助，使得我能够深入的了解网络学院的排课过程，并对我的课题的研究和实现作了悉心的指导和鼓励，他的指点给了我许多教益。

除此之外，申老师勤奋忘我的工作作风、对于工作积极进取的精神、以及对于我们的严格要求使我受益匪浅，并且值得我们终身学习。

同时，还要感谢实验室的张同珍老师，在课题的研究过程中，不断的得到来自张老师的帮助和指点，而且张老师的时时鼓励也是本文课题能够顺利完成的一大动因。

另外，还要感谢实验室的孙健师兄和彭德华师兄，他们的研究和实践是我工作的一个基础和榜样。在课题的研究期间，同样得到了他们的诸多帮助，以及在我最需要的时候，提供了不少参考的资料。

最后，还需要感谢实验室的申丽萍老师和曹老师以及实验室的各位同学，我在实验室的工作能进行的很顺利同样是因为得到了你们的帮助和关怀。

谢谢！

３４

上海交通大学学士论文 网络学院排课系统的实现

参考文献与附录：

[1] D Abramson and J Abela, (1991) ‘A parallel genetic algorithm for solving the school timetabling problem”, Technical report, Division of Information Technology, C.S.I.R.O., April 1991.

[2] Boizumault P., Gueret C. and Jussien N. (1994) “Efficient Labelling and Constraint

Relaxation for Solving Time Tabling Problems” International Logic Programming Symposium - Workshop on Constraint Languages and their use in Problem MoDelling. pp116-130

[3] Bruns R. (1993) “Knowledge-Augmented Genetic Algorithm for Production Scheduling”, IJCAI ‘93 Workshop on Knowledge based Production Planning, Scheduling and Control.

[4] EK Burke, DG Elliman, and RF Weare, (1995) “A Hybrid Genetic Algorithm for Highly Constrained Timetabling Problems,” 6th International Conference on Genetic Algorithms (Pittsburgh, USA, 15- 19 July 1995) .

[5] Burke E.K., Elliman D.G. and Weare R.F. (1994) “A University Timetabling System Based on Graph Colouring and Constraint Manipulation”, Journal of Research on Computing in Education. Vol. 27. issue 1, pp1-18.

[6] EK Burke, DG Elliman, and RF Weare, (1995) “ Examination Timetabling in British Universities - A Survey”, to appear in proceedings of the 1st International Conference on the Practice and Theory of Automated Timetabling (ICPTAT’95, Napier University, Edinburgh, 30th Aug - 1st Sept 1995).

[7] EK Burke, JP Newall, and RF Weare, (1995) “A Memetic Algorithm for

University Exam Timetabling” to appear in proceedings of the 1st International Conference on the Practice and Theory of Automated Timetabling (ICPTAT’95, Napier University, Edinburgh, 30th Aug - 1st Sept 1995).

[8] Colorni, A., Dorigo, M., Maniezzo, V. (1990) “Genetic Algorithms and Highly Constrained Problems; The Timetable Case”, Parallel Problem Solving from Nature I,

Springer-Verlag, pp.55-59.

[9] Carter M.W. (1986) “A Survey of Practical Applications of Examination Timetabling Algorithms” OR Practice 34, pp 193-202.

[10] D Corne, HL Fang, and C Mellish, (1993) “Solving the Modular Exam

Scheduling Problem with Genetic Algorithms,” Proceedings of the 6th International Conference in Industrial and Engineering Applications of Artificial Intelligence

３５

上海交通大学学士论文 网络学院排课系统的实现

and

Expert Systems , pp. 370-373, Gordon and Breach Science Publishers.

[11] Corne, D., Ross,P.,Fang H-L (1994) “Fast Practical Evolutionary timetabling”,

Lecture Notes in Computer Science 865 , Springer-Verlag, pp250-263.

[12] D Corne, P Ross, and HL Fang, (1994) “Evolutionary Timetabling: Practice, Prospects and work in Prgoress”, in the proceedings of the UK Planning and Scheduling SIG Workshop, Strathclyde, September 1994.

[13] Davis L. (1991) “Handbook of Genetic Algorithms” Van Nostrand Reinhold [14] Davis L. and Ritter F. (1987) “Schedule Optimization with Probabilistic Search”

Proceedings of the 3rd IEEE Conference on Artificial Intelligence Applications, February 1987, Orlando, Florida, USA, pp231-236.

[15] Hancock P.J.B. (1994) “An empirical Comparison of Selection Methods in Evolutionary Algorithms”, Lecture Notes in Computer Science 865, Springer-Verlag, pp80-94

[16] Johnson D.S., Aragon C.R., McGeoch L.A. and Schevon C. (1991) “Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning” Operations Research 39, pp378-406.

[17] Kang L. and White G.M. (1992) “A Logic Approach to the Resolution of Constraints in Timetabling” European Journal of Operational Research 61 pp306- 317.

[18] Ling, S.E. (1992) “Integrating Genetic Algorithms with a Prolog Assignment Problem as a Hybrid Solution for a Polytechnic Timetable Problem”, Parallel Problem Solving from Nature II, Elsevier Science Publisher. pp321-329.

[19] Paechter B., Cumming A., Luchian H. and Petriuc M. (1994) “Two Solutions to the General Timetable Problem Using Evolutionary Methods” In the proceedings of the 1994 IEEE Conference on Evolutionary Computing

[20] J Thompson and KA Dowsland, (1993) “Multi-Objective University Examination Scheduling,” EBMS/1993/12, European Business Management School, Swansea University, UK.

[21] Tripathy A. (1984) “School Timetabling - A case in Large Binary Integer Linear Programming” Discrete Applied Mathematics 35.3 pp313-323.

[22] Radcliffe N.J. and Surry P.D. (1994) “Formal Memetic Algorithms”, Lecture Notes in Computer Science 865, Springer-Verlag, pp1-16.

３６

上海交通大学学士论文 网络学院排课系统的实现

[23] P Ross, D Corne and HL Fang, “Improving evolutionary timetabling with Delta evaluation and directed mutation”, in Parallel Problem Solving from Nature III, ed.

Y.Davidor, Springer-Verlag, 1994.

[24] Welsh D.J.A. and Powell M.B. (1967) “An Upper bound for the Chromatic Number of a Graph and Its Application to Timetabling Problems” Comp. Jrnl. 10, pp85-86.

A. Colorni, M. Dorigo, and V. Maniezzo. A genetic algorithm to solve the timetable problem. Technical Report 90060, Politecnico di Milano, 1990. submitted to Computational Optimization and Applications Journal.

３７