（计算机应用技术专业论文）基于整数规划的混沌遗传排课算法研究.pdf

摘要 基于整数规划的混沌遗传排课算法研究 摘要 排课是高校教学管理工作中的一项十分繁重且相当复杂的工作。随着 各高校的不断扩招，教室和教师资源日益紧张。在这种情况下，利用计算 机自动排课，生成结构合理、满足各方需求的课表，对保障高校教学管理 工作的正常运行，具有十分重要的意义。 排课问题是典型的组合优化和不确定调度问题，已经被证明是n p 完 全问题。国内外研究人员提出了众多的排课模型以及排课算法。这其中的 整数规划方法，由于所建立的模型通用，受到研究人员的重视。然而，其 计算复杂度过高，因此逐渐淡出了人们的视野。近年来，随着计算机硬件 和软件的飞速发展，整数规划方法又重新受到人们的重视。 本人结合在教务处工作的经验，对排课问题所需考虑的各个方面进行 了详细分析。在此基础上，以本校教务管理中的排课问题为实例，建立了 基于整数规划的数学模型。在分析了分支定界法、割平面法等求解整数规 划问题的常用算法后，本文使用一种混沌遗传算法求解该问题。 最后，本文介绍了排课系统的数据库结构设计以及排课算法中各步骤 的具体实现方法，并以学校的排课历史数据，对排课系统进行了测试。经 过测试，排课系统的计算结果以及计算时间较为理想。 关键词：排课，整数规划，遗传算法，混沌 a b s t r a c t s o l v i n gc o u r s et i m e t a b l i n gp r o b l e m b yah y b r i dc h a o t i cg e n e t i ca l g o r i t h m b a s e do ni n t eg e rp r o g r a m m i n g a b s t r a c t i t i sav e r yh e a v ya n dc o m p l e xjo bf o ra c a d e m i ca f f a i r sm a n a g e m e n to f e v e r yc o l l e g et os o l v et h ep r o b l e mo f c o u r s et i m e t a b l i n g w i t ht h ec o n t i n u o u s e x p a n s i o no ft h ec o l l e g e s ，i ts e e m st h a tt h er e s o u r c e so fc l a s s r o o m sa n d t e a c h e r sa r e i n c r e a s i n g l yp r e c i o u s i nt h i sc a s e ，t og u a r a n t e et h e n o r m a l o p e r a t i o no fa c a d e m i ca f f a i r sm a n a g e m e n t ，i ti s o fg r e a ts i g n i f i c a n c et o a u t o m a t i c a l l yg e n e r a t ear e a s o n a b l ys t r u c t u r e dc o u r s et i m e t a b l ew i t ht h eu s e o fc o m p u t e r ，w h i c hc o u l dm e e ta l lt h en e e d so ft h ec o l l e g e t h ep r o b l e mo fc o u r s et i m e t a b l i n gi sat y p i c a lc o m b i n a t o r i a lo p t i m i z a t i o n a n ds c h e d u l i n gp r o b l e mo fu n c e r t a i n t y , w h i c hh a sb e e np r o v e dt ob ea n p - c o m p l e t ep r o b l e m d o m e s t i ca n df o r e i g nr e s e a r c h e r sh a v ep u tf o r w a r da n u m b e ro fc o u r s et i m e t a b l i n gm o d e l sa n da l g o r i t h m s d u et oi t su n i v e r s a l m o d e l ，i n t e g e rp r o g r a m m i n gm e t h o dg o tr e s e a r c h e r sa t t e n t i o n h o w e v e r , t h i s m e t h o dg r a d u a l l yf a d e do u to ft h ev i s i o no fr e s e a r c h e r sb e c a u s eo fi t sh i g h c o m p u t a t i o n a lc o m p l e x i t y i nr e c e n ty e a r s ，w i t ht h er a p i dd e v e l o p m e n to f i i i 北京化t 大学硕 学位论文 c o m p u t e rh a r d w a r ea n dm a t h e m a t i c ss o f t w a r e ，r e s e a r c h e r sp a ya t t e n t i o nt ot h e u s eo fi n t e g e rp r o g r a m m i n gm e t h o dt os o l v et h ec o u r s et i m e t a b l i n gp r o b l e m a g a i n w i t ht h ew o r ke x p e r i e n c ea ta c a d e m i ca f f a i r so f f i c e ，a l la s p e c t so ft h e p r o b l e mo fc o u r s et i m e t a b l i n g a r e a n a l y z e d i nd e t a i la n da n i n t e g e r p r o g r a m m i n gm o d e li se s t a b l i s h e d a f t e rt h ei n t r o d u c t i o no ft w oc o m m o n l y u s e da l g o r i t h m s ，b r a n c ha n db o u n da l g o r i t h ma n dc u t t i n gp l a n ea l g o r i t h m ，t o s o l v ei n t e g e rp r o g r a m m i n gp r o b l e m ，t h i sp a p e ru s e sah y b r i dc h a o t i cg e n e t i c a l g o r i t h mf o rs o l v i n gt h ep r o b l e m f i n a l l y , t h i sp a p e rp r o v i d e st h ed e s i g na n di m p l e m e n t a t i o no ft h ec o u r s e t i m e t a b l i n gs y s t e ma n dt e s t st h es y s t e mw i t hp r e v i o u sc o u r s et i m e t a b l ed a t a t h er e s u l ta n dc o m p u t a t i o nt i m eo ft h es y s t e ma r ep r o v e dt ob ed e s i r a b l e t h r o u g ht h et e s t k e yw o r d s ：c o u r s e t i m e t a b l i n g ，i n t e g e rp r o g r a m m i n g ，g e n e t i c a l g o r i t h m ，c h a o s 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律结果由本人承担。 作者签名：磷 日期： 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文的规 定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京化工大 学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可 以允许采用影印、缩印或其它复制手段保存、汇编学位论文。 保密论文注释：本学位论文属于保密范围，在2 年解密后适用本授 权书。非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名：圣缝 导师签名： 日期：2 q q 生圣目ib 日期：塑! ：鱼：兰： 第一章绪论 第一章绪论 本章介绍了排课问题的背景，概括了排课问题的研究历史及现状，介绍了整数规 划的方法，最后，阐述了本文的研究目的并给出了本文的结构安排。 1 1 排课问题的背景 近年来，随着高校扩招力度的加大以及专业设置与课程设置的不断改革，各高校 都面临教学计划越来越庞杂、教室和教师资源日益紧张的问题。传统的手工排课，在 其工作繁琐、工作量巨大、效率低下、难以同时照顾到各种需求等方面的缺点也就越 来越突出。要求教务处的排课教师在每个学期末的短短几周时间内，单纯依靠以往的 手工排课经验，排出能够避免上课教室、上课教师以及上课班级之间发生冲突的课表， 显得越来越困难。更不要指望手工排出的课表会尽可能结构合理、尽量满足教师对于 上课时间片的要求、尽量缩短学生赶往各上课教室之间的距离、尽量避免上课教室出 现大片空余座位等目标的实现。 而且，根据本人在教务处工作过程中的观察，手工排课由于过于依赖排课教师的 经验，而排课经验又很难通过语言文字加以概括。因此，一旦排课教师因为退休、调 换工作岗位等原因离任，继任者很难在短时间内掌握手工排课方方面面的要求，将会 给学校教学管理工作的正常运行带来巨大影响。因此，各高校都急需引进一个适合本 校教学资源情况和本校特殊排课要求的计算机智能排课系统，从而降低排课的时间和 人力成本，提高排出课表的质量，确保教学管理工作的正常运行。 因此，研究能够适应高校排课要求且自动化程度高的智能排课系统，在高校教学 管理工作中具有非常重要的意义，本文正是在此背景下完成的。 1 2 排课问题的研究历史及现状 排课问题是调度问题的一种【l 】。w r e n 在1 9 9 6 年将排课问题描述为：将资源按照 约束条件安排进有限的时间和空间内，并满足特定的目标和最大的扩展性【2 1 。就其实 质而言，排课问题是一个有约束的、非线性的、模糊多目标优化的、n p 完全的时空 组合问题【3 1 。 排课问题的复杂性主要源于需要满足大量的约束条件。这些约束条件包括课表的 冲突问题、授课时段的限制、教室资源问题等。为了编排出更为合理的、人性化的课 表，排课过程中还需要考虑课程重要程度、教师对于上课时间片的要求等。由于各个 学校情况不同、约束条件和评价最优解的标准也有较大的差距，给排课算法的设计带 北京化工人学硕上学位论文 来了困难。 自2 0 世纪5 0 年代末期，国外就对排课问题展开了研究。6 0 年代初期，c c g o t l i e b 4 】 就对课程表问题提出了形式化描述，这标志着对于排课问题的研究正式跨入了科学殿 堂。7 0 年代中期，s e v e n 5 】等人论证了排课问题是n p 完全问题，这也就奠定了排课 问题的学术地位。根据计算理论和难解性理论，到目前为止，尚无n p 完全问题的多 项式解法存在【6 1 。当问题的规模增大时，解的数量将呈指数增长。 由于排课这一时空组合问题需要满足大量约束条件，并尽量达到各种人为设定的 目标以提高排课质量，因此研究人员自然而然的想到用整数规划【7 】的方法构造排课问 题的数学模型。然而，由于整数规划问题的计算复杂度过耐8 1 、实现困难，如果约束 条件和目标方程过多，很容易导致所谓的组合爆炸，因此，研究人员转向了其他排课 方法的研究。 随着算法复杂性理论的完善，人们不再追求排课问题的最优解，而更多的转向实 际应用的角度。能够得到较好的解的近似算法，或者以一定的概率保证解的质量的随 机算法的研究越来越受到重视。9 0 年代以来，涌现出了大量基于神经网络【9 d 0 1 、遗传 算法【i i - 1 3 1 、蚁群算法【1 4 1 、进化计算【1 5 】、模拟退火【1 6 1 、本地搜索【1 7 1 、约束编程【18 1 、禁 忌搜索【1 9 1 、目标规划【2 0 】及其混合优化策吲2 1 2 4 1 的智能排课算法。 这些方法在不同程度上提高了搜索效率，但应用于我国高校，特别是面临高校扩 招后普遍存在的课程量大、教室和教师资源紧张、排课约束条件多且经常变化等问题， 这些排课算法的应变能力较弱，应用受到限制。往往在一个高校使用很成功的排课算 法，到了另一个学校使用，会遇到诸多问题，例如需要针对某高校的约束条件，大范 围修改排课算法的代码。 我国很多高校都面临教室和教师资源紧张的问题，因此，对于这些高校的排课问 题，找到满足所有约束条件的可行解，都已经非常困难，更别提找到最优解或者较优 解了。而且有的时候，满足所有约束条件的可行解都无法找到。例如本人所在高校的 教务处，试用过多种智能排课系统。但是，由于本校教室资源过于紧张，按照指定的 约束条件，根本无法得到排课结果。因此，需要对约束条件灵活设计，对于那些因自 身资源紧张而无法得到排课结果的高校，需要适当放松部分约束条件。 近期随着计算机软硬件的进步，使得解决大型整数规划问题成为可能，并且一些 商业数学软件也提供了简单整数规划问题的求解方法。目前国外研究人员，对于研究 使用整数规划的排课方法，表现得异常活跃【2 5 拙】。 纵观前人的研究结果，可以看出，大规模的、考虑诸多约束条件的排课问题由于 各种原因，仍然没有通用的解决办法。鉴于此，本人希望结合自身在教务处工作的经 验，提出一套更为灵活的处理约束条件，具有更高适应性的基于整数规划的排课算法。 2 第一章绪论 1 3 整数规划方法概述 整数规划是一类要求问题中的全部或一部分变量为整数的数学规划【2 9 1 。如果所有 变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合 整数规划。本文所使用的是纯整数规划，以下简称整数规划。 在数学规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要 求结果必须是整数。例如，所求解的问题是机器的台数，工作的人数或装货的车数等。 为了满足整数的要求，初看起来似乎只要把已得的非整数解四舍五入化成整数就可以 了。实际上，化成整数后却不见得是可行解和最优解，所以应该有特殊的方法来求解 整数规划。 整数规划是从1 9 5 8 年由r e 戈莫里提出割平面法之后形成独立分支的，3 0 多年 来发展出很多方法解决各种问题。解整数规划最典型的做法是逐步生成一个相关的问 题，称它是原问题的衍生问题。对每个衍生问题又伴随一个比它更易于求解的松弛问 题( 衍生问题称为松弛问题的源问题) 。通过松弛问题的解来确定它的源问题的归宿， 即源问题应被舍弃，还是再生成一个或多个它本身的衍生问题来替代它。随即，再 选择一个尚未被舍弃的或替代的原问题的衍生问题，重复以上步骤直至不再剩有未解 决的衍生问题为止。目前比较成功又流行的方法是分枝定界法和割平面法，它们都是 在上述框架下形成的。 整数规划与组合最优化从广泛的意义上说，两者的领域是一致的，都是在有限多 个可供选择的方案中，寻找满足一定标准的最好方案。有许多典型的问题反映整数规 划的广泛背景。例如，背袋( 或装载) 问题、固定费用问题、和睦探险队问题( 组合 学的对集问题) 、有效探险队问题( 组合学的覆盖问题) 、送货问题等。因此整数规划 的应用范围也是极其广泛的。它不仅在工业和工程设计和科学研究方面有许多应用， 而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。 在多目标规划问题中引入了整数变量以后，即便是线性问题，也变得难以解决。 可行域不再是凸的，由此造成的困难远比从单目标线性规划到整数规划造成的困难更 大【3 0 】。因此，在大多数情况下，不能通过在多目标线性规划中引入整数变量加以解决。 m l 规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、 选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整数规划都与0 1 规划等价，用o 1 规划方法还可以把多种非线性规划问题表示成整数规划问题，所以 不少人致力于这个方向的研究。求解o 1 规划的常用方法是分枝定界法，对各种特殊 问题还有一些特殊方法，例如求解指派问题用匈牙利方法就比较方便【3 。 3 北京化t 大学硕t 学位论文 1 4 本文的研究目的与结构安排 虽然目前已有大量的排课算法出现，但是由于各高校的教学资源差异较大、排课 的指导原则大相径庭、排课结果的评价标准不同，造成排课算法的移植性较差。往往 在一个高校使用的排课算法，移植到其他学校无法使用并且难以修改。在这种背景下， 本文提出了一种更为灵活的处理约束条件、具有更高适应性的基于整数规划的排课算 法，并成功应用于本校教务管理系统中。 由于大型关系数据库都是基于关系代数理论建立起来的，因此，可以很容易的通 过数据库中的s q l 语句操作，实现整数规划模型的约束条件和目标方程。目前各高 校广泛使用教务管理系统，而各种不同的教务管理系统，在数据库结构设计上，并无 本质的区别。因此，基于整数规划的排课系统具有很强的可移植性，通过修改初始化 模块和课表更新模块，以及根据高校政策调整与约束条件和目标方程相关的s q l 语 句，即可在其他高校使用。 本文的内容组织如下： 第一章为绪论，介绍了排课问题的背景，概括了排课问题的研究历史及现状，介 绍了整数规划的方法，明确了本文的研究方向。 第二章为基于整数规划的排课模型，对排课问题进行了详细分析，建立了基于整 数规划的排课模型，介绍了求解整数规划问题的常用方法。 第三章为求解整数规划的混沌遗传算法，介绍了遗传算法以及混沌遗传算法，给 出了混沌遗传算法求解整数规划问题的具体实现。 第四章为排课算法的设计与实现，介绍了排课算法的数据库结构设计，给出了排 课算法各模块的实现方法，并对排课算法进行了分析。 第五章为总结与展望，概括了本文的研究成果，指出了本领域有待研究的问题以 及发展方向。 4 第二章基于整数规划的排课模型 第二章基于整数规划的排课模型 排课问题的难点在于：其并非简单的排列组合问题，而是一个在受到教学管理环 节中的诸多因素约束的情况下，寻找最优解或较优解的问题。根据排课问题的自身特 点，使用整数规划的方法建立排课问题的数学模型最为直观。而且，随着近年来依托 大型关系数据库建立的诸多教学管理系统在我国高校的广泛使用，排课问题的数据来 源以及计算结果，都需要保存在关系型数据库中。由于关系型数据库是依据关系代数 理论建立起来的，因此使用整数规划建立的排课模型，可以较为方便的将约束条件和 目标方程转化为s q l 语句对二维数据表的操作。而且，近年来使用整数规划模型求 解排课问题，又重新成为排课领域的研究热点，证明整数规划模型非常适合解决排课 问题。因此，本文使用基于整数规划的方法建立排课问题的数学模型。 本章首先对排课问题进行了详细的分析，然后根据分析建立了基于整数规划的排 课模型，最后，介绍了求解整数规划问题的常用方法。 2 1 排课问题详细分析 排课是一项非常繁重且复杂的工作，以北京化工大学为例，排课涉及到4 1 个专 业、8 0 0 余名教师、1 0 0 0 0 多名学生、2 0 0 0 多门课程的合理组织安排。而教室资源和 教师资源却在招生规模不断加大的情况下，日益紧张起来，这显然对排课问题提出了 更高的要求。在讨论排课模型以前，有必要对排课问题的业务流程、数据流程、所研 究的对象、约束条件以及排课结果的衡量标准展开讨论。 由于教学思想和教育体制等方面的差别，各高校教学管理思路不尽相同，因此对 于排课问题考虑的对象、约束条件以及衡量标准，也存在一些细微的差别。但是，排 课问题所面对的关键难点寻找时空组合的最优解或较优解没有丝毫改变。以 下将对排课问题进行详细分析。 2 1 1 排课问题的业务流程 排课问题始于教学计划的制定。目前国内各高校的教学计划，根据教学对象的不 同，分为教师一班级以及教师一学生两种模式。教师一班级模式的教学计划，教师授 课的基本单位为班级，因此在排课算法中根据班级判断是否冲突；教师一学生模式的 教学计划，教师授课的基本单位为学生，因此在排课算法中根据学生判断是否冲突。 两种模式只是授课对象范畴不同，对于算法设计，也只是约束条件略微不同。整体建 模过程、算法结构以及问题规模并没有显著差异。 本文不对两类教学计划的好坏进行比较分析。目前，大部分高校采用教师一班级 5 北京化工人学硕士学位论文 模式的教学计划；只有少数试点高校，例如清华大学和浙江大学，采用教师一学生模 式的教学计划。因此，在当前状况下，研究依照教师一班级模式的教学计划进行排课 的排课算法，更具有普遍意义。针对各专业以及各年级，教学计划规定了每个学期所 应该开设的必修课以及限选课。限选课只对本专业学生开设，本专业学生可以自由选 择，其他专业学生无法选修。但是每个学生都必须满足本专业教学计划中，每个限选 课模块的最低通过学分要求以及最低通过门数要求。 除了必修课和限选课，学校还开设公共选修课，公共选修课不限制选课学生的年 级和专业。实际上，公共选修课是根据教师一学生类型的教学计划开设的。但是，由 于原则上允许学生选修两门同时上课的公共选修课，因此并不根据学生判断课程是否 冲突。在主体上，仍然是依照教师一班级模式的教学计划。因此，在本文中，我们并 不讨论公共选修课的排课问题，只需要为公共选修课的特定上课时间和上课地点做标 记，在智能排课系统中不在这些时间点排课即可。公共选修课程可以通过手工排课方 式完成：或者，在排完必修课和限选课以后，对约束条件进行放松，取消判断班级冲 突的约束条件，通过智能系统进行自动排课。 必修课和限选课都根据班级判断课程是否冲突。为了方便起见，在本文中，必修 课和限选课的上课人数被称为合班人数。 必修课不涉及学生网上选课的问题，而对于限选课，学生需要根据自己的兴趣爱 好等个人情况在网上选课。根据选课与排课顺序的不同，排课又分为先选后排方式以 和先排后选方式。先选后排方式，在为课程安排上课时间和上课地点以前，先将课程 信息发布到教务网站供学生选择。根据学生的选课情况，得到各门课程相对准确的上 课人数，然后再进行排课；先排后选方式，根据历年排课数据分析以及排课教师的经 验，大致估计各门课程的上课人数，为课程安排上课时间和上课地点以后，再将课程 信息发布到教务网站供学生选择。 这两种排课方式各有优缺点。对于先选后排方式，由于在排课前可以得到各门课 程相对准确的上课人数，可以在排课过程中充分利用教室资源，避免出现上课教室空 闲大片座位的情况。但是，由于学生在选课阶段并不知道上课时间和上课地点，因此 在排课结束后的学生补退选课程阶段，一些学生会改选其他限选课，学生选课过程会 比较繁琐。在补退选课程阶段，学生需要根据各课程所在教室的空闲座位情况进行选 择：如果某门课程所在教室已经没有空闲座位，那么学生将不能选修此门限选课程。 对于先排后选方式，由于学生在选课的时候已经知道课程的上课时间以及上课地点， 因此学生在补退选阶段，改选其他课程的几率较小。但是在排课阶段，需要根据历年 课表以及排课教师的经验估计各门课程的大致上课人数。而在估计过程中，存在许多 不可预测的因素，往往估值与实际上课人数之间存在较大的偏差，因此极其容易将上 课人数较少的课程安排在容量较大的教室中。 目前，国内大多数高校采用先选后排方式，以下我们将根据教师一班级模式的教 6 第二章基十整数规划的排课模型 学计划和先选后排的排课方式，对排课问题的业务流程进行分析。 学校教务处在每个学期末，会从教学计划中提取出下个学期的开课任务。开课任 务与班级表通过专业代码和年级代码两个字段连接，形成班级执行计划。例如，针对 开课任务中某一专业某一年级的某门课程这一条记录，通过专业代码和年级代码两个 字段，与班级表中具有相同专业代码值和年级代码值的若干个班级连接，形成若干条 班级执行计划记录，即将每条针对年级的开课任务拆分成若干条针对班级的执行计 划。 教务处根据本校各专业特点、教师情况、教室容量情况，对班级执行计划进行合 班操作。对班级执行计划进行合班操作以后，形成执行计划。合班操作的指导原则是： 相近专业的班级尽量在一起上课、上同一门课的所有教师的授课班级数量尽量平均、 尽量避免上课教室空闲大量座位情况的发生。例如，下个学期共有7 0 个班级需要上 “高等数学( i ) 这门课程，下个学期共有l o 名老师可以讲授“高等数学( i ) ，那 么就应该尽量将每7 个相近专业的班级合并在一起，将7 0 条班级执行计划的记录合 并为1 0 条执行计划的记录。如果学校的教室容量分别为2 1 0 人、1 5 0 人、1 2 0 人、9 0 人、3 0 人，那么应该尽量避免将6 个班级合并在一起，因为6 个班级的学生人数在 1 8 0 人左右，只能安排在教室容量为2 1 0 人的教室，势必造成教室空闲3 0 个座位左右。 随着高校扩招规模不断加大，造成教室资源异常紧张，因此需要尽量减少教室的空闲 座位数量。合班操作通过排课老师制定的合班表完成。 教务处根据课程所属的开课学院，将执行计划下发到各个学院，各学院教学秘书 根据本学院教师情况，对执行计划中的每条记录添加起止周、周学时、教师代码、教 室类型、时间片要求等信息。教室类型包括普通、多媒体、语音、金工、实验、制图 丘盘 守。 各学院教学秘书添加完毕以后，教务处根据班级学生表，将执行计划中的必修课 程添加到学生课表中。然后将执行计划中的限选课程的课程信息以及公共选修课的课 程信息，发布教务网站上以便学生进行选择，并将学生选课结果添加到学生课表中。 这样，每个学生的学生课表包括必修课以及自己选择的限选课和公共选修课。 学生选课结束后，教务处根据学生选课情况，更新执行计划中每条记录的合班人 数。在更新人数后，教务处根据时间片表和教室表进行排课工作，此阶段指定执行计 划中每条记录的上课时间和上课地点。 排课完成后，还需要根据学生补退选课程情况以及教师要求微调执行计划。由于 对执行计划的微调主要是靠排课教师手工操作，因此还需要在微调过程中对进行冲突 检测。此后，根据执行计划发布全校课表、学生课表以及教师课表，并在教务网站公 布。至此，排课工作结束。 排课问题的业务流程如图2 1 所示： 7 北京化t 大学硕十学位论文 2 1 2 排课问题的数据流程 制定教学计划 i 提取下学期开课任务 i i 生成班级执行计划 l 合班生成执行计划 i 添加教师代码等信息 上 选课并更新合班人数 排课 上 i 依补退选更新合班人数 j r 生成并发布课表 图2 - 1 业务流程 f 蟾2 - 1b u s i n e s sp r o c e s s 下面根据排课问题的业务流程，对其中涉及到的数据加以说明。 教学计划表中至少应包含专业代码、年级代码、开课学年、开课学期、课程性质 ( 必修课还是限选课) 、课组代码( 指定课程属于哪一个教学模块) 、课组最低通过学 分、课组最低通过门数、课程代码、学分、学时、考试类型( 考试还是考查) 、教学 区代码等字段。 开课任务表中至少应包含专业代码、年级代码、课程性质、课程代码、学分、学 时、考试类型、教学区等字段。 班级表中至少应包含专业代码、年级代码、班级代码等字段。 班级执行计划表中至少应包含课程代码、学分、学时、课程性质、考试类型、班 级代码、教学区等字段。 合班表中至少应包含合班代码、班级代码等字段。 执行计划表中至少应包含课程代码、学分、课程性质、考试类型、合班结果( 各 个班级代码组合在一起，中间用逗号分割开) 、起止周、周学时、教师代码、教室类 型代码、时间片要求、上课人数、上课时间片、上课地点、教学区等字段。 教师表中至少应包含教师代码、教师姓名、教师权重、所属学院等字段。 班级学生表中至少应包含学号、班级代码等字段。 第_ 二章基十整数规划的排课模型 学生选课表中至少应包含学号、课程代码等字段。 时间片表中至少应包含教学日( 周一至周五) 、时间段、时间片( 教学日与时间 段合并的结果) 等信息。 教室表中至少应包含教室代码、教室容量、教室类型代码、教学区代码等信息。 全校课表中至少应包含课程代码、课程名称、学分、课程性质、考试类型、合班 结果、上课教师、上课人数、上课时间、上课地点、教学区代码等字段。 学生课表中至少应包含课程代码、课程名称、学分、课程性质、考试类型、上课 教师、上课周次、上课日期、上课节次、上课地点、教学区代码等字段。 教师课表中至少应包含课程代码、课程名称、课程性质、考试类型、上课时间、 上课地点、教学区代码等字段。 排课问题的数据流程如图2 2 所示： 2 1 3 排课问题所涉及的对象 图2 2 数据流程 f i g 2 - 2d a t af l o w 排课问题涉及到的相关数据主要包括时间、班级、课程、教室和教师这5 个要素。 对这些数据进行透彻的分析以及适当的预处理，是建立排课模型的基础。 ( 1 ) 时间。由于我国高校所授课程大多以教师讲授的形式进行，因此每周的课 表相对固定。故本文只考虑周课表的安排，随后根据每门课程设定的起止周，将周课 表中的课程安排复制到其他教学周，形成学期课表。 设定每周一至周五为正常教学日，1 周5 天；每天有1 0 节课( 上午4 节、下午4 节、晚上2 节) ，上课方式为一个“课次 占用相邻的两节课，不能在上、下午和下 9 北京化t 大学硕 j 学位论文 午、晚上之间跨时段上课。把每两节课合并成为一个“课次 ，加上课间休息时间定 为一个时间段。排课工作对时间的最小操作单位为时间片。一节课占用5 0 分钟时间， 课间休息5 分钟。因此，可以把每个教学日，划分为五个时间段：第一个时间段为上 午第l 、2 节课，从8 点整到9 点4 5 分；第二个时间段为上午第3 、4 节课，从1 0 点 0 5 分到1 1 点5 0 分；第三个时间段为下午第5 、6 节课，从1 3 点3 0 分到1 5 点1 5 分； 第四个时间段为下午第7 、8 节课，从1 5 点3 0 分到1 7 点1 5 分；第五个时间段为晚 一上第9 、1 0 节课，从1 8 点整到1 9 点4 5 分。 这样，每个教学周有5 个教学日，每个教学日有5 个时间段，因此，每个教学周 共有2 5 个时间片。由于每周的教学日数量以及每个教学日的时间段数量都不超过1 0 ， 因此，用两位十进制数来表示1 个时间片，就可以达到2 5 个时间片与2 5 个互不相同 的两位十进制数一一对应的目的。设定第一个教学日的第五个时间段，即周一第1 、2 节课，对应的两位十进制数的时间片编码为1 1 ，依此类推，第五个教学日的第五个时 间段，即周五第9 、1 0 节课，对应的两位十进制数的时间片编码为5 5 。则排课问题类 似于填充5 行5 列的的周时间片分布表。 排课问题的周时间片分布表如表2 1 所示，根据时间片的编号，可以形成1 列2 5 行的时间片表。 表2 - 1 周时间片分布 t a b l e2 1w e e kt i m es l i c ed i s t r i b u t i o n 周一周二周三周四周五 第一时间段 1 l 2 13 14 l5 l 第二时间段 1 22 23 24 25 2 第三时间段 1 32 33 34 35 3 第四时间段 1 42 43 44 45 4 第五时间段 1 52 53 54 55 5 ( 2 ) 班级。班级作为教师讲授课程的基本单位，通常一门课程的授课对象是多 个班级的组合。对- 1 7 课程的所有班级人数求和得到该课程的上课人数。由于学生退 学、休学、转专业、留级等原因，班级的人数会发生变化。因此，在排课前，需要根 据学籍表的最新情况更新班级人数。而在每个学期初，通常是学生学籍状态变化最为 频繁的时期。因此，还需要在开学初再次更新班级人数以及课程的上课人数，并通过 上课人数与教室容量比较，对两者差异较大的，还需要进行手工调课，以便更为充分 的利用教室资源。 在我们的执行计划中对应的是合班代码，并不是班级代码。在合班表中，给出了 合班代码与班级代码的对应关系。 1 0 第二章基于整数规划的排课模型 ( 3 ) 课程。每门课程每周需要安排的学时体现为课程的学分，l 学分的概念就是 在每个教学周安排1 个学时( 1 节课) 。例如4 学分的课程，周学时为4 ；3 学分的课 程，周学时为3 ；2 5 学分的课程，周学时为3 。对于周学时不是偶数的课程，比如2 5 学分的课程，周学时为3 。如果按照周学时为3 进行安排，势必造成上午或者下午的 1 节课无法再安排其他课程，因此，在实际操作时，周学时为奇数的课程，排课时的 实际周学时，取为比该课程周学时数大的最小偶数。例如周学时为3 的课程，在排课 时的实际周学时为4 ，只是缩短了起止周或者分为单双周排课，达到课程的总学时要 求。在我校，一间教室在一个学期内，只能安排一门课程。将学分为3 的课程按照周 学时为4 进行安排，缩短了起止周，但是空闲出来的这些时间并不能安排其他的课程， 可以用来调排课或供教师和学生借用。因此，单双周排课只需要在起止周中体现，并 不需要在排课过程中考虑。我们的排课问题仍然只是考虑周课表。 起止周字段由阿拉伯数字、逗号和破折号组合而成。例如某门课程从第3 周到第 1 6 周上课，则表示为“3 1 6 ；如果某门课程从第1 周到第1 8 周的奇数周上课，则表 示为“l ，3 ，5 ，7 ，9 ，11 ，1 3 ，15 ，1 7 。 在所有排课准备工作完成以后，通过周学时( 已将周学时为奇数的课程按照实际 周学时数为偶数对待) 除以“课次”( 2 节课) ，得到在1 个教学周内，所需要占用的 时间片数量。对于需要的时间片数量大于1 的课程，通过在教学计划中复制该课程实 现一周内多次排课，每次安排1 个时间片的目的。复制的课程与原课程的课程代码不 同，在排课中可以看成两门不同的课程。例如英语的周学时为4 ，在1 个教学周内， 所需要占用的时间片数量为2 ，大于1 。因此在执行计划中复制一次该课程以后，周 学时为4 的一门英语课被当作两门不同的英语课进行安排，每门英语课安排1 个时间 片。因此在排课过程中，不再需要考虑周学时。下文中所有讨论的课程，实际均是“课 次 的概念。 每门课程的重要程度不一样，学分的多少可以用来简单的衡量课程的重要程度。 例如，高等数学有5 个学分，而体育只有1 个学分，显然高等数学比体育更为重要。 而在排课时，另外一个需要考虑的因素是：课程的合班数量。显然应该优先安排合班 数量多的课程，否则有可能由于先安排了其他课程，占用了班级的空闲时间片，从而 造成上同一门课程的所有班级的空闲时间段集合不相交，即不存在可供合班中所有班 级同时上课的时间片。因此，在排课时，需要根据课程学分的多少和合班数量的大小 为课程设置权重，在本文中，简单的设置课程的权重等于课程学分乘以合班数量。 ( 4 ) 教室。一般高校均有几个教学区，每个教学区有几个楼可以供教学使用。 因此，可以使用6 位十进制数字唯一表示一间教室。第l 位十进制数字表示教室所在 的教学区；第2 个十进制数字表示教室所属的教学楼；第3 、4 位十进制数字表示教 室所在的楼层；第5 、6 位十进制数字表示教室在该层的具体编号。如此编码的好处 是：可以通过两间教室编码的差值表示两间教室的距离。 北京化工人学硕一 j 学位论文 教室又分为多媒体、语音、制图、金工、实验、普通等类型。在排课过程中，应 满足课程对上课教室的类型要求。由于多媒体教室数量有限，且需求量大，所以并不 能任由学院教学秘书指定。可以根据各学院的开课规模以及开课类型，由教务处规定 各学院可以在多媒体教室上课的课程数量。各学院指定在多媒体教室上课的课程数 量，不得超过教务处的规定。对教室类型进行编码，并用两位十进制数字表示：1 0 表示普通教室，1 l 表示多媒体教室，2 0 表示金工教室，3 0 表示制图教室，4 0 表示语 音教室；实验室的第一位十进制数字为5 ，第二位十进制根据实验室的特定类型进行 编码。例如物理实验室用5 l 表示，无机实验室用5 2 表示，有机实验室用5 2 表示。 ( 5 ) 教师。每个教师均有权重，表示满足教师对排课时间段要求的优先级。在 排课前，需要对所有教师的权重进行初始化，此工作由教务处排课教师负责。 2 1 4 排课问题的约束条件 排课是将教师和班级的学生在时间和空间上，根据各种约束条件进行时空排列组 合，实现正常教学的手段。约束条件主要为了避免冲突和满足学校的规定。避免冲突 是排课问题中要解决的核心问题，因为冲突几乎发生在任意两个或多个排课涉及因素 之间。只有在满足全部约束条件的基础上，才能保证整个教学计划合理j 下常进行。 以下，将根据一般高校所面临的实际情况，罗列出所有需要考虑的约束条件。这 些约束条件分为：唯一性约束、完整性约束和其他约束。 其中，唯一性约束保证排课结果不存在冲突，具体包括： ( 1 ) 在任意一个时间片，同属于任意一个合班的所有班级不能被安排两门及以 上不同的课程，即每个合班代码对应的所有班级，在任意一个时间片，至多只可能被 安排一门课程。由于在执行计划中，- - n 课程只能指定一个教师代码和一个教室代码， 因此，满足了第( 1 ) 条约束，自然而然也就不会造成在某一个时间片，同属于任意 一个合班的所有班级被安排在两间及以上不同的教室或者由两名及以上不同的教师 上课的情况。 ( 2 ) 在任意一个时间片，任意一名教师不能被安排两门及以上不同的课程，即 在任意一个时间片，任意一名教师至多只可能被安排一门课程。根据以上所讨论的教 学计划的特点，实现第( 2 ) 条约束的同时，就避免了在某一个时间片，某一名教师 被安排在两间及以上不同的教室上课的情况。 ( 3 ) 在任意一个时间片，任意一间教室不能被安排两门及以上不同的课程，即 在任意一个时间片，任意一间教室至多只可能被安排一门课程。同理，第( 3 ) 条约 束实现的同时，就避免了在某一个时间片，某一间教室安排了两名及以上不同的教师。 根据执行计划的特点，- - l - j 课程只能指定一个教室代码。但此处所说课程其实是一个 “课次 。由于我们已经将周学时大于2 的课程复制，因此允许周学时大于2 的课程 1 2 第二章基于整数规划的排课模型 在不同的教室上课。例如，周学时为4 的英语课，由于已经在教学计划中复制成为两 门周学时为2 ，即一个“课次”的课程，因此允许这门英语课在两间不同的教室上课。 完整性约束保证排课结果满足教学计划的要求，具体包括： ( 4 ) 对课程安排的总课时必须满足课程的学时要求。 ( 5 ) 任意- f - j 课程都必须安排一个时间片和一间教室，即排课问题必须找到可 行解。如果不能满足此条约束，考虑减小各学院可以在多媒体教室上课的课程数量。 其他约束保证排课结果能够满足学校的特定要求，具体包括： ( 6 ) 在任意一个时间片，任意一门课程的合班人数都必须小于等于教室容量。 我们将此约束放在其他约束中，是因为在实际操作过程中，很多高校允许课程的合班 人数在一定程度上超出教室容量。因此，将课程的合班人数必须小于等于教室容量视 为学校的特殊要求。 ( 7 ) 在任意一个时间片，任意一门课程要求的教室类型必须和所安排教室的类 型相同。多媒体类、金工类、实验类、语音类课程，毫无疑问，需要严格按照课程类 型指定教室类型。其他课程，即在执行计划中教室类型字段为空的课程，可以安排在 普通教室或者多媒体教室，即教室类型代码第一位为1 的教室。 ( 8 ) 任意一名教师，在任意一个教学日，只能在一个教学区上课。由于我校两 个教学区相距比较远，在第一时间段和第二时间段中间的2 0 分钟不可能从一个教学 区赶到另一个教学区。同理，第三时间段和第四时间段中间的1 5 分钟不可能从一个 教学区赶往另一个教学区；第四时间段和第五时间段中间的4 5 分钟不可能从一个教 学区赶往另一个教学区。如果一名教师在同一天在两个不同的教学区上课的时间，相 差一个时间段以上，理论上可以从一个教学区赶往另一个教学区。然而，由于两校区 之间班车发车时间的限制，以及对教师疲劳影响授课质量的考虑，规定一名教师在同 一天内只能在一个教学区上课。 2 1 5 排课结果的衡量标准 排课的目的，是对时间片、班级、课程、教室和教师这几部分资源进行最优化组 合配置，充分发挥各资源的优势来提高教学质量。 ( 1 ) 对于学生，在每个教学日的上午，听课效率最高。因此应充分利用每个教 学日上午的时间，尽量将课程安排在上午，尤其是学分多、合班数目多的课程。 ( 2 ) 为了使学生能够及时消化教师教授的内容，应尽量使学生个人课表中每个 教学日的课时量相对均衡。避免一天全排满课程，而另外一天几乎不上课情况的发生。 ( 3 ) 为了避免大课间教学楼的走廊过于拥挤，应尽量缩短学生在同一天中的第 一个时间段与第二个时间段( 第1 、2 节课与第3 、4 节课之间的大课间) 之间的上课 教室距离和同一天中的第三个时间段与第四个时间段( 第5 、6 节课与第7 、8 节课之 北京化t 大学颁卜学位论文 间的大课间) 之间上课教室的距离