高校排课问题的模型与求解

第２３卷第４期

山东科技大学学报（自然科学版）

Ｖ０１．２３Ｎｏ．４

２００

４年１２月

ＪｏｕｒｎａｌｏｆＳｈａｎｄｏｎｇＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ（Ｎａｔｕｒａｌ．Ｓｃｉｅｎｃｅ）Ｄｅｃ．２００４

文章编号：１６７２—３７６７（２００４）０４—０１１１—０３

高校排课问题的模型与求解

郑中华１，赵卫东１，简伟平２

（１．山东科技大学信息科学与工程学院，山东泰安２７１０１９；２．泰山职业技术学院，山东泰安２７１０００）

摘要：给出了以行政班为编排单位的排课问题的模型，探讨了其有解性和约束条件的一致化表示，并针对传统回溯法的不足，通过动态规划的方法找出了克服策略，提出求解算法。指出了下一步的研究方向。

关键词：排课；鸽巢原理；关系；产生式；动态规划中图分类号：ＴＰ３９１

文献标识码：Ｂ

Ｔｈｅ

Ｍｏｄｅｌ

ｏｆＵｎｉｖｅｒｓｉｔｙＣｏｕｒｓｅＳｃｈｅｄｕｌｉｎｇａｎｄＳｏｌｕｔｉｏｎ

ＺＨＥＮＧＺｈｏｎｇ．ｈｕａｌ，ＺＨＡＯＷｅｉ—ｄｏｎ９１，ＪＩＡＮＷｅｉ．ｐｉｎｇａ

（１．Ｃｏｌｌｅｇｅｏｆ

Ｉｎｆｏ．ａｎｄ

Ｅｎｇ．，ＳＵＳＴ，Ｔａｉａｎ，Ｓｈａｎｄｏｎｇ２７１０１９，Ｃｈｉｎａ；

２．Ｔａｉｓｈａｎ

Ｃｏｌｌｅｇｅ

ｏｆＶｏｃａｔｉｏｎａｌ

Ｔｅｃｈｎｏｌｏｇｙ，Ｔａｉａｎ，Ｓｈａｎｄｏｎｇ２７１０００，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ｔｈｉｓｐａｐｅｒｇｉｖｅｓ

ｔｈｅｍｏｄｅｌｏｆｕｎｉｖｅｒｓｉｔｙ

ｃｏｕｒｓｅ

ｓｃｈｅｄｕｌｉｎｇａｎｄｄｉｓｃｕｓｓｅｓｉｔｓｓｏｌｖａｂｌｅｃｏｎｄｉｔｉｏｎｓ

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

ｏｎ

ｔｈｏｓｅａｌｌａｂｏｖｅｗｅｐｒｏ—

ｐｏｓｅ

ｔｈｅａｌｇｏｒｉｔｈｍａｎｄｆｕｒｔｈｅｒｒｅｓｅａｒｃｈｄｉｒｅｃｔｉｏｎ．

Ｋｅｙｗｏｒｄｓ：ｃｏｕｒｓｅｓｃｈｅｄｕｌｉｎｇ；ｐｉｇｅｏｎｈｏｕｓｅｐｒｉｎｃｉｐｌｅ；ｒｅｌａｔｉｏｎ；ｐｒｏｄｕｃｔｉｏｎ；ｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇ

１

排课问题的描述

这就把排课问题归结成了一个排列组合问题。

排课是教务管理的核心和难点问题之一。为

２排课问题的有解性

了描述排课问题，首先定义课时单元Ｃｏｕｒｓｅｉ，其由鸽巢原理【４Ｊ，当空闲时间属性集合和课时中Ｃｏｕｒｓｅ表示开设的课程，下标表示该门课的第单元集合间有关系Ｉ

ＴｃＩ。ｎＴ。。ｈｅｎＴ—Ｉ≥

ｉ个课时，那么所有的待编排课时就可以表示成集

Ｉ｛ＣｏｕｒｓｅＡｌ，ＣｏｕｒｓｅＡ２，…．ＣｏｕｒｓｅＡｉ；ＣｏｕｒｓｅＢｌ，合｛ＣｏｕｒｓｅＡｌ，Ｃ０ｕｒｓｅＡ２，ＣｏｕｒｓｅＡｉ；ＣｏｕｒｓｅＢｌ，ＣｏｕｒｓｅＢ２…．．ＣｏｕｒｓｅＢｉ；…．．．｝Ｉ时排课问题即

Ｃｏｕｒｓｅｔｋ，ＣｏｕｒｓｅＢｉ；｝。其次定义空闲时间属性集有解。但排课过程中常常要满足各种各样的约束合Ｔ。ｌ。、Ｔ。ｈ¨Ｔ。。，其中Ｔ。ｌ。表示班级的空闲

条件，纵观这些约束条件，它们对排课过程产生的时间属性集合，Ｔ。。。。ｈ。，表示教师空闲时间属性集

影响主要集中在两方面，一种是对特定资源的需合，Ｔ一表示教室的空闲时间属性集合。每个空

求（时间资源或空间资源）导致了局部资源瓶颈的闲时间属性集合中的元素视作是容纳课时单元的

产生，使得虽然总体上满足有解条件，但局部不满容器，每个元素为一个向量（ｗｅｅｋ，Ｄａｙ，Ｓｅｃｔｉｏｎ），

足有解条件而导致求解失败。例如有多门课要求Ｗｅｅｋ表示周次，Ｄａｙ表示周几，Ｓｅｃｔｉｏｎ表示节使用多媒体教室，在当前条件下，虽然所有教室的次。排课问题就是将课时单元按照一定的约束规时间属性集合的基数与所有课程的待排课时的基则安排到时间属性集合Ｔｄ。ｎＴ。。。ｈ。ｎＴ。。上，

数满足上述有解性条件，但要求使用多媒体教室

收稿日期：２００４—０６—２４

作者简介：郑中华（１９７６．），男，山东章丘人，硕士研究生，主要从事人工智能、决策支持方面的研究

万　

方数据

１１２

山东科技大学学报（自然科学版）第２３卷

课程的待编排课时单元集合的基数大于多媒体教室时间属性集合的基数，则整个排课过程将会在此处终止。另一种是对于课时排布特性的要求，

使得集合ｌＴ。ｌ。。ｎＴ。。。ｈｅｎＴ—ｌ中的许多元素成

为不可用元素，这也导致了资源的相对不足。例如排课要求课时安排要有连续性，即在一门课程的一个进程内，编排的课程表在此进程内的任意两个周的授课节次应当是一致的，此约束条件导致集合Ｔ。ｈ鹞ｎＴ。ｈ。ｎ

Ｔｒ一中的许多元素不能排

人课时单元。实际排课问题有解的条件为Ｔｄ。ｎＬ。ｈｅｒｎＴｒ—Ｉ＞Ｉ｛ＣｏｕｒｓｅＡｌ，ＣｏｕｒｓｅＡｌ，Ｃｏｕｒｓｅ蝻，ＣｏｕｒｓｅＢｉ，｝Ｉ，更进一步量化的评价有鳃性，应当视具体情况再做分析，主要相关联的因素是教学资源的丰度、约束条件和选择的排课算法。

３排课问题的约束条件

排课问题的复杂性源于排课要满足大量的约大，很难设计出一个适用于所有高校的通用排课根据约束条件对排课过程产生的影响将其分为两类，一类是直接时空相关约束，其所产生的效果体现在编排过程中对时空范围的限定上。此类约束条件呵用一个五元组来表示（ｏ，Ｓ，ｔ，Ｃ，ｉ），Ｏ∈Ｏ，Ｏ是约束对象集合，其中元素是由所有开设课程、开课班级、任课教师构成；Ｓ∈Ｓ，Ｓ是空间集合，其中的元素是所有的教室；ｔ∈Ｔ，Ｔ是时间属性集合；ｃＥＣ，Ｃ＝｛０，１｝，集合Ｃ称为选择集合，０表示避开，１表示选定；０＜ｉ≤１，ｉ∈Ｉ，Ｉ称为约束强度集合，因为排课过程中的约束条件存在固有的模糊性，还存在众多约束条件之间的优先顺序的问题，所以引入了约束强度集合Ｉ来解决。Ｉ是一个由［０，１］之间的实数构成的集合，用于表示约束条件的强弱，随着ｉ的增大约束强度也逐渐增大，若ｉ＝１称为必须满足。任一五元组Ｒ必然满足Ｒ∈Ｏ×Ｓ×Ｔ×Ｃ×Ｉ的某一子集，则所有的直接时空相关约束条件总可以用关系数据库模型中的关系来表示，在系统实现时就可以实现为关系数据库中的一个表。

另一类称之为非直接时空相关约束，此类约束对具体某一时空范围内课时的排布产生影响。对于此类约束条件用产生式来表示，产生式是专

万　

方数据家系统中用来表示推理过程和行为等动态知识的一种方式，它是以“如果满足这个条件，就应当采取某些操作”表示的语句。产生式的ＩＦ部分被称作条件，ＴＨＥＮ部分被称作操作，这两部分均用谓词逻辑来表示。例如有下列约束条件：当一门课在一周内安排的次数超过两次且可供排课的天数又大于上课的次数时，则要求两次课之间应当间隔适当的天数。此约束条件可用如下产生式表示：ＩＦ（Ｄａｙｓ＞ＴｉｍｅｓＯｆＣｕｒ）Ａｎｄ（ＴｉｍｅｓＯｆＣｕｒ＞１）ＴｈｅｎＩｎｔｅｒｖａｌ＞０，其中Ｄａｙｓ代表上课的天数，ＴｉｍｅｓＯｆＣｕｒ代表一周内上课的次数，Ｉｎｔｅｒｖａｌ是以天表示的课时间隔。排课时，首先通过条件匹配来寻找触发规则，有可能有一条以上规则的条件部分和数据库中数据匹配，则要进行冲突解决，冲突解决的策略存在有多种如专一性排序、规则排序等，最后确定启用规则应用到编排过程中。

在系统中提供此两类约束条件的输入、修改接口，在编排过程中能够自动应用这两类约束则系统就具备了通用性。

４排课问题的求解

排课问题的求解目标，就是在满足各种约束条件的前提下，合理利用教学资源，以取得最好的教学效果。若要求得最优解，通常列出所有可能的结果，从中选出一个最优的，由于存在组合爆炸，课表最佳解的时间复杂度是课表规模的指数级，因此对各种排课算法的研究均以求得较优解为目标。

国外对排课算法做了很多研究，但普遍没有考虑教室资源不足的问题，我国由于高校扩招，教室资源普遍紧张，不符合我国的实际。国内有人对应用模拟退火算法［７｜、遗传算法（８】求解排课问题进行了探讨，但此类方法普遍时空复杂度较高，离实用化还有一段距离。常用的求解方法是贪心算法结合回溯法，即在求解过程中不要求最优解，首先找到一个可行解就使求解过程继续进行下去，直到发生待编排课程无资源可供分配时，则中断求解过程，调整先前排出的结果，然后再继续进行编排过程。这种求解策略存在许多问题，诸如回溯点难于控制、求解的结果只能是可行解而非较优解、时空复杂度较高等。

在求解过程中产生回溯的原因在于根据图灵机计算模型，计算过程是读写头从输入带上读一个字符，再决定下一步的操作，这种方式计算机不

束条件，在实际当中各所高校的具体情况差别较算法。如果对约束条件能够实现一致性的表示，再提供相应的描述和实现工具，设计出来的算法无疑具备了真正意义上的通用性。

第４期郑中华等：高校排课问题的模型与求解

１１３

知道先前的求解结果和状态，只能通过回溯来获别，很难准确估算出算法的时间复杂度，但时间复得。另外在排课过程中系统缺乏关于资源的全局杂度将不超过Ｏ（Ｎｋ。ｉ。ｇｃｌａ。ｘ

ＮＴｅ。ｈｅｒ×Ｎｃｔ。×

知识，没有相应的全局编排策略对整个编排过程ＮＴ髓ｃｈｅｒ×ＴＲ㈣＾∞ｉｇｒＩ×ＴｌａｙＯｕｔ），其中Ｎｋｍｉｎｇｃｌａ∞是

进行控制，资源的不合理分配降低了资源的利用听课班的数目，Ｎａ。。是班级开设课程的最大周上

率。真正克服回溯问题应当从制定全局控制策略课次数，Ｎ‰ｈ。是教师所承担课程最大周上课次

人手，通过用动态规划的方法对回溯产生的原因数，Ｎ‰ｃｈｅ，是教室安排的最大周上课次数，

进行了分析，总结出可以避免回溯的策略：

ＴＲ—Ａｓｓｉｇｎ是分配教室所花费的时间，ＴＬ如。。是产生

（１）人数优先，即上课人数多的课程优于上课课时排布规划所花时间。

人数少的课程。这避免了由于先排单班课，到最后每个班级的ＩＴｃｌ８ｓｓＩ满足要求，而合班课的ｌ５

结束语

ＴｃＩ。１ｎ

ＴｃＩ础ｎ

ＴｃＩａｓｓ３…Ｊ却不满足的情况。

该模型与求解方法已在实际中得到应用，取

（２）人数相同的条件下，进程跨度大的课程优得了较好的效果。以上对问题的探讨局限于以行先。这可以避免因先排小跨度课程而造成可供编政班为授课单位的情况，随着素质教育的深入，高排进程的零碎化。

等院校教学方式将逐渐向完全学分制过渡，在完（３）人数和进程跨度相同，则周课时大的课程全学分制条件下授课打破了原来行政班的编制，优先。

教师将面对通过学生自由选课而形成的听课班来（４）课时编排从按照递增的次序来编排，即先进行授课，在冲突检测、消解方面会遇到许多新问排周一再排周二这样一直往下进行，对于某一天题，有待进一步研究。则是按照上午、下午和晚上的顺序来编排。

参考文献：

在具体实现时策略还可以继续扩充，总的目［１］萨师煊，王珊．数据库系统概论［Ｍ］．北京：高等教育

的是在ＩＴｃｌａｓｓｌ、ＩＴ。ｈｅｒＩ、Ｉ

Ｔ—Ｉ一定的情况下，

出版社．２００２．

保证ＩＴｄ。ｎＴｔ。ｈｅｒｎＬ—Ｉ尽量取到最大值。

［２］卢开澄．计算机算法导引一一设计与分析［Ｍ］．北

系统采用的排课算法如下：

京：清华大学出版社，１９９６．

（１）检测资源是否充足，若存在瓶颈则给出提［３］胡运权，郭耀煌．运筹学教程［Ｍ］．北京：清华大学出

示并终止，否则转（２）；

版社。２００３．

”（２）应用各类优先原则，排序听课班，从中取［４］陈东灵韩丛英，等．组合数学［Ｍ］．东营：石油大学

出一个听课班；

出版社，２００２．

［５］陈谊，杨怡，等．基于优先级自动排课算法ＰＣＳＡ的设

（３）求出听课班所对应的行政班和任课教师计与实现方案［Ｊ］．北京工商大学学报，２００２，（６）．所对应的时间属性的交集，即：Ｔｃｌ。ｎＴ。。。ｈｅ。；

［６］董艳云，钱晓群，等．基于课元相关运算的高校排课算

（４）分配教室；

法［Ｊ］．西南交通大学学报，１９９８，（６）．

（５）求行政班、教师和教室的空闲时间属性交

［７］刘继清，陈传波．模拟退火算法在排课中的应用［Ｊ］．

集，即：Ｔｃｌ。。ｎＴ。。。ｈ。。ｎＴ一；

武汉船舶职业技术学院学报，２００３，（９）．

（６）统计ｆＴ。ｌ。ｎ

Ｔ。。。。ｈｅｒ

ｎ

Ｔ。一Ｉ是否符合要

［８］唐勇，唐雪飞，等．基于遗传算法的排课系统［Ｊ］．计

求，若不符合要求则转（４），否则转（７）；

算机应用，２００２，（１０）．

（７）生成课时的排布规划；［９］陈本庆，马永强，等．改进型回溯法在高校排课中的应

（８）将排课的结果写入数据库中；

用［Ｊ］．成都信息工程学院学报，２００３，（６）．

（９）所排听课班是否是最后一个听课班，若是［１０］胡小兵，鲁宏伟．基于模糊专家系统的排课系统关键

技术的研究［Ｊ］．长沙电力学院学报，２００１，（４）．则结束算法，否则转（２）。

［１１］蔡自兴，徐光祜．人工智能及其应用［Ｍ］．北京：清华

由于ｌＴ。ｌ。Ｉ、ｌＴ。ｈ。ｌ、Ｉ

Ｔ，一Ｉ是与课程的进

大学出版社。１９９６．

程密切相关的，不同学校、不同班级存在较大差

万　

方数据

内容需要下载文档才能查看

高校排课问题的模型与求解

作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：

郑中华， 赵卫东， 简伟平

郑中华,赵卫东(山东科技大学,信息科学与工程学院,山东,泰安,271019)， 简伟平(泰山职业技术学院,山东,泰安,271000)

山东科技大学学报(自然科学版)

JOURNAL OF SHANDONG UNIVERSITY OF SCIENCE AND TECHNOLOGY(NATURAL SCIENCE)2004,23(4)10次

参考文献(11条)

1.萨师煊;王珊 数据库系统概论 20022.卢开澄 计算机算法导引-设计与分析 19963.胡运权;郭耀煌 运筹学教程 20034.陈东灵;韩丛英 组合数学 2002

5.陈谊;杨怡 基于优先级自动排课算法PCSA的设计与实现方案[期刊论文]-北京工商大学学报(自然科学版)2002(06)

6.董艳云;钱晓群 基于课元相关运算的高校排课算法 1998

7.刘继清;陈传波 模拟退火算法在排课中的应用[期刊论文]-武汉船舶职业技术学院学报 2003(09)8.唐勇;唐雪飞 基于遗传算法的排课系统[期刊论文]-计算机应用 2002(10)

9.陈本庆;马永强 改进型回溯法在高校排课中的应用[期刊论文]-成都信息工程学院学报 2003(06)

10.胡小兵;鲁宏伟 基于模糊专家系统的排课系统关键技术的研究[期刊论文]-长沙电力学院学报(自然科学版)2001(04)

11.蔡自兴;徐光祜 人工智能及其应用 1996

本文读者也读过(10条)

1. 肖明.曾莉 基于拉丁矩的高校排课算法[期刊论文]-数字技术与应用2010(8)2. 许荣泉.秦小屿 排课问题的研究与改进[期刊论文]-软件导刊2010,09(3)3. 顾宏民 高校排课方法探讨[期刊论文]-辽宁广播电视大学学报2009(2)

4. 刘国锋 鸽巢原理在数学竞赛中的应用[期刊论文]-世界华商经济年鉴·科学教育家2009(9)5. 余航 高等代数的解题方法探讨[期刊论文]-高等数学研究2007,10(1)6. 黄学松.吴艳 排课问题的数学表述[期刊论文]-管理信息系统2002(3)

7. 沈群.SHEN Qun 关于棋盘构形中同色矩形问题的一些探讨[期刊论文]-太原科技大学学报2006,27(3)8. 罗璇.罗琳 基于以人为本理念的高校排课方法探讨[期刊论文]-河北广播电视大学学报2009,14(6)9. 林志雄.LIN Zhi-xiong 排课数学模型及其算法[期刊论文]-龙岩学院学报2006,24(6)

10. 任克强.赵光甫.张国萍.REN Ke-qiang.ZHAO Guang-fu.ZHANG Guo-ping 高校排课问题的模型与算法[期刊论文]-计算机与现代化2007(10)

引证文献(11条)

1.陈辉.王伟 大学教室课程安排实现与应用[期刊论文]-青年文学家 2009(15)

2.孟庆全 排课程序优先级的确定与最简单算法的实现[期刊论文]-安徽工程科技学院学报（自然科学版） 2005(2)3.王彦丽.方胜吉 医学院校排课系统的设计与实现[期刊论文]-医学信息 2008(10)4.邹晨 自动排课的研究与实现[学位论文]硕士 2005

5.夏云龙 排课系统导入数据时代码名称转换问题的研究[期刊论文]-商情 2011(1)6.夏云龙 排课系统导入数据时字段名称转换问题的研究[期刊论文]-中国科技博览 2011(8)7.夏云龙 对解决异构数据转换问题算法的研究[期刊论文]-煤炭技术 2012(7)

8.张明.孟宪涛.李岩 教学管理数学模型的建立与应用[期刊论文]-沈阳师范大学学报（自然科学版） 2010(3)9.王学军 一种基于案例和约束的排课系统[期刊论文]-计算机与现代化 2008(6)10.季家刚 基于J2EE的高校教务管理信息系统的设计与实现[学位论文]硕士 200511.吴美香 基于CBR的复杂问题求解方法研究[学位论文]硕士 2005

本文链接：http://wendang.chazidian.com/Periodical_sdkjdxxb200404034.aspx