排课系统的开发和实现.doc

上海交通大学学士论文 网络学院排课系统的实现10:41排课系统的开发和实现摘要要完成一所大学或者一个学院的课程安排是一件非常复杂的问题，如果用人手工进行安排的话，需要极大的精力和时间。而在排课的时候，需要考虑的范围，涉及到教师、课程、教室还有班级情况等等。而在现今的大学排课过程中，整个学校需要考虑的教师，课程信息是成百上千，排课问题由此变为一个异常复杂的组合问题。所以在现实世界的应用中，排课问题的所有排列组合对于人类来说几乎可以被认为是一个天文数字。而一个可以被接受的排课方案是一个满足排课所有制约性要求的方案。在此基础上，如果有人希望能通过一些启发性的设定而得到一个更为优化（更为合理，美观，更为符合人的习惯）的排课方案的话，则这个问题就会变得超乎寻常的困难。所以迄今为止，为了能够用计算机自动完成排课任务已经进行了非常多的尝试。排课的本质问题是将大量的课程安排进有限的上课时间和教室中，与此同时还会涉及到任课老师和学生班级等各种因素互相制约的影响。通常来说，排课中涉及的变量越多，则排课问题就会越复杂。而本课题的排课研究涉及的排课环境是上海交通大学的网络学院。网络学院的排课是排课问题中的一个全新的领域。因为，在网络学院中，教室有了多媒体，视听等各种新的属性，而这在传统的排课问题中是没有的。而且，网络学院的上课时间也更具多样性。不同的专业，有的每天上午最多只能排4节课，而有的专业却可以安排5节课。时间标准的多样性，教室属性的多样性，使得网络学院的排课问题需要考虑更多的因素，从而给排课提出了更高的要求。本文所做的研究工作先是比较了一下当今比较流行的集中排课算法，如线性算法、遗传算法、限制逻辑(CLP)编程等等算法各自的优缺点和适用性。并且，在此基础上，本文针对网络学院排课更为特殊的要求，提出了一个新的算法。最终，基于本文所提出的这个算法，开发出了一个全新的排课模型，使其不但能适应普通的排课环境，还能够很好地满足网络学院更为特殊的排课要求。关键词： 远程教育， 排课， 人工智能， 遗传算法，限制逻辑编程 THE CONSTRUCTION OF TIMETABLES FOR SCHOOL COURSESAbstractThe 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 schools 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 Annealing2.2.2 Constraint Logic Programming2.2.3 Graphic Coloring Heuristics2.2.4 Genetic Algorithms2.2.5 Linear Programming2.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、 归档其中，排课的部分又细分为1、 按专业制定教学培养计划（全部课程，包括毕业设计或论文）；2、 按专业制定每学期教学执行计划；3、 按开设的课程聘请（落实）上课教师；4、 根据教学执行计划、学生人数、学生选课地点、教师要求及教室等情况排课；但是，在电子教务系统中，排课的工作目前仍就是由负责排课的教师手工编排。当学院开设的课程越来越多以后，教师的安排，教室的安排和课程的安排，各种制约条件之间的矛盾会越来越难处理。用手工编排，费时费力费心，还难免会有顾此失彼的情况发生，所以将排课部分由计算机来完成这一工作变的日益重要。而纵观目前市面上说流行的各种排课系统软件，不是小学版的，就是中学版的，主要原因是中小学的上课安排规律性很强，每次上课人数由一个班级组成，不需要换教室，没有上下学期课程不同之分，每天上课都为早上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 1420的中文直译应该是“模拟淬火”算法，不过我没有看到过相关的中文资料，所以决定还是保留其英文的原名比较好。Simulated Annealing (SA)算法被广泛应用于处理各种不同组合优化问题，特别是在学校的排课计划中。其基本的算法描述如下图所示。Figure 2.1: The Simulated Annealing AlgorithmSA算法相对其他的一些全局优化技术有优点也有缺点。优点之一是非常容易实现,几乎可以应用到任意一个组合优化问题中去，能为大多数问题提供解决方案，并能与专家系统等启发式方法相结合解决一系列复杂的问题。所以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： Mapping2.2.2 Constraint Logic ProgrammingConstraint Logic Programming (CLP) 217 是由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所示。StudentLectureS1e1,e2,e3,e6S2e1,e2,e3,e5S3e1,e2,e3,e5S4e1,e2,e5S5e4S6e4,e5S7e2,e4S8e2,e4,e6S9e3,e4,e6S10e3,e4,e6Table 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 810引起了越来越多的关注。有关遗传算法在排课领域中的应用最早出现于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节的课程，因为我发现这样的课程往往比较难排。所以，有必要将他们提到比较前面一点，先进行安排。第三个判断函数的作用，是将选择这门课班级人数多的排在前面。因为，上课的人多，意味着相应的教室要比较大，这也是一个相对来说较苛刻的条件，所以有必要先将他们安排好。第三，第四个函数做的事情是这样的。因为，我们先前将一周内要上几次的课程都拆分开来了，认为他们是几门不同的“课程”。但是，很明显，他们的课程属性完全一样，也就是他们的优先级应该完全一样。在这种情况下，我希望在排序的时候，这些有原来一门课分裂出来的课程都能在队列中紧邻的排列。这样我就有必要判断哪些“课程”是由原先同一门课程分裂出来的，哪些不是。所以我要做以下两个判断。一 课程的名称是否一样。二 上课的班级是否一样。如果，以上两点完全相同的话，则我们有理由认为这样的两门课就是原先由同一门课程分裂出来的，所以应该在排序的时候紧邻。完成第一次安C