重庆大学

硕士学位论文

高校自动排课系统的算法研究与实现

姓名：湛德照

申请学位级别：硕士

专业：计算机技术

指导教师：何中市;高宏宾

20061001重庆大学硕士学位论文中文摘要

摘要

目前，随着我国高校教育事业的不断发展，课程编排问题在一定程度上影响

着教学质量的提高。为了保证教学质量，高校必须制定一套严密、规范的教学计

划和执行合理的课程安排。而课程编排是比较繁重而关键的一环。回顾过去，１９６３

年，Ｃ．Ｃ．Ｇｏｆｌｉｅｂ在文章《ＴｈｅＣｏｎｓｔｒｕｃｔｉｏｎｏｆＣｌａｓｓ－ＴｅａｃｈｅｒＴｉｍｅ－Ｔａｂｌｅｓ）中提出

了课表编排的数学模型，它标志着课程编排课题的研究正式跨入了庄严的科学殿

堂。１９７６年，ＳＥｖｅｎ在论文《ｏｎＴｈｅＣｏｍｐｌｅｘｉｔｙｏｆＴｉｍｅｔａｂｌｅＡｎｄＭｕｌｔｉＣｏｍｍｏｄｉｔｙ

ＦｌｏｗＰｒｏｂｌｅｍｓ》，第一次证明了课表是ＮＰ完全问题。在国内，清华大学于１９８４

年在《清华大学学报（自然版）》上发表了林漳希和林尧瑞在该课题上的实验性研究

成果，接着国内部分高等院校相继开展了这方面的研究工作。本文分析了排课的

数学模型，提出了利用遗传算法解决排课问题的方法，完成的主要工作如下：①探讨课程表问题的约束因素，以优化时间和空间两种资源为目标，通过对

比，我们发现采用遗传算法去解决课表问题是比较理想的解决方法，并讨论了它

的基本原理、步骤及其产生、发展、现状以及存在的问题等情况。

②改进时间安排算法：遗传算法有能简化程序的复杂度和生成最佳课表时间

的优点，本论文提出的时间安排算法以经典遗传算法作为基础，进行了以下几个方面研究工作：１）对遗传算法存在的缺陷进行改进和优化，避免了遗传算法出现

未成熟就收敛等问题；２）提出排课问题的优化求解模型和约束满足模型；３）针

对排课问题研究了染色体编码方式以及遗传操作算子的设计，提出了一种适应度

计算方法，由节次优度、日组合优度等相互联系求解。

③提出教室安排算法：排课问题中，除了时间安排外，为课程选择一个教室是十分重要的，我们提出了教室安排算法，实现资源优化配置。

④系统的实现：针对课表个性化的要求，设置了排课知识库和策略库来动态

地调整准则，以满足不同课表要求，体现该系统具有良好的适用性和实用性。本文以五邑大学排课系统的开发为背景，对整个系统的工作进行了分析总结，

并对后续工作进行了展望。

关键词：排课，遗传算法，组合优化，人工调整重庆大学硕士学袋论文茭文攮要

ＡＢＳＴＲＡＣＴ

Ｒｅｃｅｎｔｌｙ，ｗｉｔｈｔｈｅｃｏｎｓｔａｎｔｌｙｄｅｖｅｌｏｐｍｅｎｔｏｆｈｉｇｈｅｄｕｃａｔｉｏｎ，ｔｉｍｅｔａｂｌｉｎｇｈａｓｖｅｒｙ

ｉｍｐｏｒｔａｎｔｒｏｌｅｉｎｒｉｓｉｎｇｔｈｅｅｄｕｃａｔｉｏｎｑｕａｌｉｔｙ．Ｉｎｏｒｄｅｒ协ｇｕａｒａｎｔ∞ｉｔｓａｄｖａｎｃｅｄ

ｔｅａｃｈｉｎｇａｎｄｓｔｕｄｙｉｎｇｑｕａｌｉｔｙ，ａｕｎｉｖｅｒｓｉｔｙｍｕｓｔｄｒａｗｕｐａｔｉｇｈｔａｎｄｓｔａｎｄａｒｄｔｅａｃｈｉｎｇａｎｄｓｔｕｄｙｉｎｇｐｌａｎａｎｄＣａｌＴｙｏｕｔｔｈｅｒｅａｓｏｎａｂｌｅｔｉｍｅｔａｂｌｉｎｇ．Ｔｈｅｔｉｍｅｔａｂｌｉｎｇｉｓｏｎｅｏｆｔｈｅｈｅａｖｙａｎｄｋｅｙｑｕｅｓｔｉｏｎｓ．Ｉｎ１９６３，Ｃ．Ｃ．Ｇｏｔｌｉｅｂｐｒｏｐｏｓｅｄｔｈｅｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌｏｆ

ＣｕｒｒｉｃｕｌｕｍＳｃｈｅｄｕｌｅＰｒｏｂｌｅｍ（ＣＳＰｆｏｒｓｈｏｒｔ）ｉｎｔｈｅｐａｐｅｒ（ＴｈｅＣｏｎｓｔｒｕｃｔｉｏｎｏｆ

Ｃｌａｓｓ－ＴｅａｃｈｅｒＴｉｍｅ－Ｔａｂｌｅｓ｝，ｉｔｓｙｍｂｏｌｉｚｅｄｔｈｅｒｅｓｅａｒｃｈｉｎｇｏｆＣＳＰｈａｄｅｎｔｅｒｔｈｅ

ｓｃｉｅｎｃ宅ｄｏｍａｉｎｆｉｅｌｄ．Ｉｎ１９７６，Ｓ．ＥｖｅｎｐｒｏｖｅｄｔｈａｔＣＳＰｉｓａＮＰ—Ｃｏｍｐｌｅｔｅｄｐｒｏｂｌｅｍｉｎ

ｔｈｅｐａｐｅｒ（ＯｎＴｈｅＣｏｍｐｌｅｘｉｔｙｏｆＴｉｍｅｔａｂｌｅＡｎｄＭｕｌｔｉＣｏｍｍｏｄｉｔｙＦｌｏｗＰｒｏｂｌｅｍｓ》

ｆｏｒｆｉｒｓｔｔｉｍｅ．ＩｎＣｈｉｎａ，Ｔｓｉｌｌｇｈｕａｕｎｉｖｅｒｓｉｔｙｄｅｌｉｖｅｒｅｄｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｌｙｒｅｓｅａｒｃｈｅｄ

ｒｅｓｕｌｔｏｆｚ｝ｌａｎｇｘｉＬｉｎａｎｄＹａｏｒｕｉＬｉｎａｂｏｕｔｔｈｉｓｐｒｏｂｌｅｍｉｎ（ＪＯＵＲＮＡＬＯＦ

ＴＳＩＮＧＨＵＡＵＮＷＥＲＳＩＴＹ（ＳＣＩＥＮＳＥＡＮＤＴＥＣＮＯＬＯＧＹ））。Ｓｕｂｓｅｑｕｅｎｔｌｙ，ｐａｒｔｓｏｆ

ｎａｔｉｖｅｏｔｈｅｒｕｎｉｖｅｒｓｉｔｉｅｓａｌｓｏｂｅｇａｎｒｅｓｅａｒｃｈｉｎｇｗｏｒｋａｂｏｕｔｔｈｉｓｐｒｏｂｌｅｍ．Ｔｈｅｍａｔｈｅｍａｔｉｃｓｍｏｄｅｌｏｆｔｉｍｅｔａｂｌｉｎｇｉｓｄｉｓｃｕｓｓｅｄｉｎｔｈｉｓｐａｐｅｒ，ｍｅａｎｗｈｉｌｅｔｈｅＧｅｎｅｔｉｃ

Ａｌｇｏｒｉｔｈｍ（ａＡ）ｉｓｕｓｅｄｔｏｒｅｓｏｌｖｅｔｈｅｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ．Ｔｈｅｍａｉｎｗｏｒｋｏｆｔｈｉｓｐａｐｅｒｉｓｌｉｓｔｅｄａｓｆｏｌｌｏｗｓ：④Ｔｈｉｓｐａｐｅｒｄｉｓｃｕｓｓｅｓｎｕｍｅｒｏｕｓｃｏｎｓｔｒａｉｎｔｓｉｎｖｏｌｖｅｄｉｎｔｈｅｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ，

ｗｈｏｓｅａｉｍｉＳｔｏｏｐｔｉｍｉｚｅｔｈｅｔｗｏｒｅ搭ｏｕｌ＇ｃｅｓｏｆｔｉｍｅａｎｄａｐａｃｅ．Ｃｏｍｐａｒｉｎｇ谳像ｖａｒｉｏｕｓ

ｍｅｔｈｏｄｓ，ｗｅｆｉｎｄｔｈａｔｉｔ’ＳａｎｉｄｅａｌｍｅｔｈｏｄｔｏａｄｏｐｔＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｔｏｒｅｓｏｌｖｅｔｈｅ

ｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ，ａｎｄｄｉｓｃｕｓｓｉｔｓｂａｓｉｃｐｒｉｎｃｉｐｌｅ，ｓｔｅｐａｎｄｉｔｓｃｒｅａｔｉｏｎ，ｄｅｖｅｌｏｐｍｅｎｔ，

ｐｒｅｓｅｎｔｃｏｎｄｉｔｉｏｎａｎｄｅｘｉｓｔｅｎｔｐｒｏｂｌｅｍｅｔｅ．＠ＴｈｅｉｍｐｒｏｖｅｍｅｎｔｏｆＴｉｍｅ－ＡｒｒａｎｇｅｄＡｌｇｏｒｉｔｈｍｉｓｇｉｖｅｎｉｎｔｈｉｓｐａｐｅｒａｓｆｏｌｌｏｗｓ：ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｈａｓｔｈｅａｄｖａｎｔａｇｅｓｏｆｓｉｍｐｌｉｆｙｉｎｇｐｒｏｃｅｄｕｒｅａｎｄｍａｋｉｎｇｔｈｅｂｅｓｔｔｉｍｅｔａｂｌｅ．ＴｈｉｓａｌｇｏｒｉｔｈｍｉｓｂａｓｅｄｏｎｃｌａｓｓｉｃＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ．Ｔｈｅｍａｉｎｃｏｎｔｅｎｔａｒｅａｓｆｏｌｌｏｗｉｎｇ：１）ＭａｋｅｓｏｍｅｉｍｐｒｏｖｅｍｅｎｔｓａｎｄｏｐｔｉｍｉｚａｔｉｏｎｏｎｔｈｅｃｌａｓｓｉｃＧｅｎｅｔｉｃ

Ａｌｇｏｒｉｔｈｍ，ａｎｄａｖｏｉｄｔｈｅＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍａｐｐｅａｒｉｎｇｖａｒｉｏｕｓｐｒｏｂｌｅｍｓｓｕｃｈ嬲

ｉｍｍａｔｕｒｅｃｏｎｖｅｒｇｅｎｃｅ；２）Ｗｏｒｋｏｕｔｔｈｅｏｐｔｉｍｉｚａｔｉｏｎｍｏｄｅｌｆｏｒｒｅｓｏｌｖｉｎｇａｎｄｃｏｎｓｔｒａｉｎｔｍｏｄｄｉｎｔｉｍｅｔａｂｔｉｎｇｐｒｏｂｌｅｍ；３）Ｗｅｓｔｕｄｉｅｄｃｈｒｏｍｏｓｏｍｅｃｏｄｉｎｇａｎｄｈｅｒｅｄｉ移ｏｐｅｒａｔｏｒ

ｄｅｓｉｇｎｉｎｇａｉｍｅｄａｔｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ，ｐｕｔｆｏｒｗａｒｄａｆｉｔｎｅｓｓｃｏｍｐｕｔａｔｉｏｎｍｏｄｅｆｒｏｍ

ｓｌｏｔ－ｓｕｐｅｒｉｏｒ，ｃｏｍｂｉｎｉｎｇ－ｓｕｐｅｒｉｏｒ－ｏｎ—ｄａｙ．ｅｔｃ．Ｃｏｎｔａｃｔｓｔｏｓｏｌｖｅｍｕｔｕａｌｌｙ．③Ｃｌａｓｓｒｏｏｍ—ａｒｒａｎｇｅｄａｌｇｏｒｉｔｈｍ：ＢｅｓｉｄｅｓＴｉｍｅ－ＡｒｒａｎｇｅｄＡｌｇｏｒｉｔｈｍ，ｉｔ’Ｓｖｅｒｙ

珏重庆丈学硕士学藏论文英文接要

ｉｍｐｏｒｔａｎｔｔｏｃｈｏｏｓｅａｃｌａｓｓｒｏｏｍｆｏｒａｃｏＢｒｓｅｉｎｔｉｍｅｔａｂｌｉｎｇｐｒｏｂｌｅｍ．Ｗｅｈａｄｗｏｒｋｅｄ

ｏｕｔｃｌａｓｓｒｏｏｍ—ａｒｒａｎｇｅｄａｌｇｏｄｔｈｍ，ｏｐｔｉｍａｌａｌｌｏｃａｔｉｏｎｏｆｒｅｓｏｕｒｃｅｓｉｓｇｕａｒａｎｔｅｅｄ．④Ｔｈｅｒｅａｌｉｚａｔｉｏｎｏｆｔｈｅｓｙｓｔｅｍ：Ｃｏｎｓｉｄｅｒｉｎｇｔｈｅｐｅｒｓｏｎａｌｒｅｑｕｅｓｔｏｆｔｉｍｅｔａｂｌｅ，ＷｅｅｓｔａｂｌｉｓｈｅｄｔｈｅｔｉｍｃｔａｂｌｉｎｇＫｎｏｗｌｅｄｇｅＬｉｂｒａｒｙａｎｄＳｔｒａｔｅｇｙＬｉｂｒａｒｙｔｏａｄｊｕｓｔｔｈｅｓｔａｎｄａｒｄｗｉｔｈｓａｔｉｓｆａｃｔｉｏｎｆｏｒｄ｛ｆｆｅｒｅｎｔｔｉｍｅｔａｂｌｅｒｅｑｕｅｓｔｓ．Ｉｔｉｓｐｒｏｖｅｄｔｈａｔｔｈｅｓｙｓｔｅｍ

ｄｅｖｅｌｏｐｅｄｗｉｔｈｔｈｅａｌｇｏｒｉｔｈｍｈａｓｇｏｏｄａｄａｐｔａｂｉｌｉｔｙａｎｄａｖａｉｌａｂｉｌｉｔｙ．ＴｈｉｓｐａｐｅｒｔｏｏｋｔｈｅｅｘｐｌｏｉｔａｔｉｏｎｉｎｂａｃｋｇｒｏｕｎｄｏｆｔｈｅｔｉｍｃｔａｂｌｉｎｇｓｙｓｔｅｍｉｎＷｕｙｉ

Ｕｎｉｖｅｒｓｉｔｙ，ｃａｒｆｉｅｄｏｎａｌｌａｎａｌｙｔｉｃａｌｓｕｍｍａｒｙｆｏｒｔｈｅｗｈｏｌｅｗｏｒｋ，ａｎｄｍａｄｅａｎｏｕｔｌｏｏｋｔｏｔｈｅｆｏｌｌｏｗ－ｕｐｗｏｒｋ．

Ｋｅｙｗｏｒｄｓ：Ｔｉｍｅｔａｂｌｉｎｇ，ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ＣｏｍｂｉｎａｔｉｏｎＯｐｔｉｍｉｚａｔｉｏｎ，

ＩＩＩ独创性声明

本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取

得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文

中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重麽盍堂

或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本

研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。

学位论文作者签名：配乙签字日期：幽／年，一月≠日

学位论文版权使用授权书

本学位论文作者完全了解重麽盍堂有关保留、使用学位论

文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，

允许论文被查阅和借阅。本人授权重鏖太堂可以将学位论文的全部

或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制

手段保存、汇编学位论文。

保密（），在——年解密后适用本授权书。

本学位论文属于

不保密（）。

（请只在上述一个括号内打“√”）

学位论文作者签名：茫睨郢繇铷手

签字日期：幽占年膳月年日

签字日期：之励缉ｆ矿月ｙ日重庆大学硕士学位论文１绪论

１绪论

１．１排课问题的提出及研究意义

高校的排课是教学管理中最基本、最重要、十分繁重而复杂的工作，它涉及

到全校全部的专业，全部的师生和全部的课程，它的本质就是为所有的课程安排

一组适当的教学时间和地点，使教学能够顺利进行。随着各高校的招生规模扩大，

教师和教室资源显得越发紧张，使得本来就有难度的排课越发困难。

课表的编排属于一类涉及多种因素的组合规划问题【ｌ】，它必须使课程安排中的教室、教师和学生不发生冲突，这是最基本的要求，在此基础上要尽量满足教师

提出的其它要求（比如某教师要求只是上午上课，必须在多媒体教室上课等等）

和学校教室资源的约束。在人工排课的过程中，实现这样的要求是有一定困难的，

为学校排出一个可行的课表要排课工作人员耗费两到三个月的时间，工作量非常

大，而且排出来的结果也未必尽人意。随着各高校的教育体制改革的深入和招生规模的进一步扩大，手工排课的缺点越显突出，我校的情况更为严重，因为教师

和教室资源的限制，排课非常困难。而计算机恰好能帮助解决这个问题，它具有

自动运行、计算速度快等特点，只要有相应的软件系统，就能很好地解决排课的

困难，实现教学管理决策的科学化。

１．２国内外计算机自动排课的研究历史

５０年代末，国外就有人开始研究课表编排问题。１９６２年，Ｇｏｔｌｉｅｂ曾提出一

个课表问题的数学模型怛】，并使用匈牙利算法解决了三维线性运输问题。此后，

人们对课表问题的算法、解的存在性等问题做了很多深入探讨，但是大多数文献

所用到的数学模型都是Ｇｏｆｌｉｅｂ的数学模型的简化或补充。近５０年来，人们对课表问题的计算机解法做了许多尝试。其中，有人将课表编排的整数规划模型问题

归结为求一组Ｏ．１变量的解，但是其计算量非常大，而且解决Ｏ．１线性优化问题的

分支定界技术却只适用于规模较小的课表编排；Ｍｉｈｏｅ和Ｂａｌａｓ（１９６５）将课表公式

化为一个优化问题【３】；另外还有人提出将它当作一种线性编程的方法或将课表问

题简化为三维运输问题；而Ｔｒｉｐａｔｈｙ则把课表问题视作整数线性编程问题并提出了大学课表的数学模型［４１；此外，有些文献试图从图论的角度来求解课表问题，

但是图的染色问题也是ＮＰ完全问题，只有在极为简单的情况下才可以将课表编排转化为二部图匹配问题吲。这样的数学模型与实际相差甚远，所以对于大多数学

校的课表编排问题来说没有实用的价值。进入九十年代以后，国外对课表问题的

研究仍然十分活跃，比较有代表性的有印度的Ｖａｓｔａｐｕｒ大学管理学院的Ａｒａｂｉｎｄａ