（计算机应用技术专业论文）智能课表编排系统的研究与实现.pdf

摘要 摘要 随着计算机的广泛应用和互联网技术的高速发展，在全国高校中许多教学 管理系统相继投入使用。课程编排及课表管理是教学管理的必要组成部分，其 课表编排质量直接关系到后继教学活动的开展，因此排课功能在整个教学管理 中占有重要地位。 排课问题已经被证明是一个n p 完全问题，因此，在实际项目的研发中，开 发出符合要求的排课系统有一定难度。本论文分析了远程教学支撑平台的教务 流程的特点以及高等学校制定课表的原则，对排课需求进行了分析、描述，建 立了排课问题的组合优化数学模型。 论文对各种排课算法进行了研究。根据实际需求，最终提出了一个比较符 合实际情况的基于贪婪策略的排课问题求解算法一一i c s a g ( i n t e l l i g e n t c u r r i c u l a rs c h e d u l i n ga l g o r i t h mb a s e do ng r e e d ym e t h o d s ) 算法。 论文给出了i c s a g 算法的详细设计方法，并编程加以实现。最后对此算法 进行了测试，测试表明此算法能够从实际的排课情况出发，有效地满足了事先 规定的各种排课限制条件，达到了实际应用需求。 根据智能课表编排系统的需要，将这个i c s a g 算法应用于实际系统开发 中，实现了一个w e b 环境下的智能课表编排系统。经过测试，排课结果和用户 使用性能达到设计要求。 最后，在智能排课系统的工作基础上，初步实现了一个选课系统。其选课 操作能够基于排课结果正确执行，选课系统与排课系统保持了数据的一致性， 保证了操作的可靠性。 关键词课表；排课；贪婪策略 a b s t r a c t a b s t r a c t w i t ht h ew i d e l yu s eo fc o m p u t e ra n dr a p i dd e v e l o p m e n to fi n t e m e t ，m a n y t e a c h i n gm a n a g e m e n ts y s t e m sh a v e b e e ns u c c e s s f u l l yu s e di nd o m e s t i cu n i v e r s i t i e s t h ec u r r i c u l u ms c h e d u l i n gs y s t e mi sas u b - m o d u l eo fe d u c a t i o nm a n a g e m e n t s y s t e m ， a n dt h eq u a l i t yo fc u r r i c u l u mt i m e t a b l ew i l ld i r e c t l yr e l a t e st oo t h e rt a s k so f t e a c h i n g m a n a g e m e n t ，s ot h ec u r r i c u l u ms c h e d u l ep l a y sak e yr o l e i n t h et e a c h i n g m a n a g e m e n tw o r k a st h ec o u r s e - t i m e t a b l ep r o b l e mh a db e e np r o v e dt ob ean pc o m p l e t e n e s s c a t e g o r yp r o b l e m ，t om a k eo u tas a t i s f a c t o r yc u r r i c u l a ra r r a n g i n gs y s t e mi sad i f f i c u l t t a s k t h i sp a p e ra n a l y z e dt h ec h a r a c t e r i s t i c so ft h et e a c h i n gm a n a g e m e n tf l o wa n d p r i n c i p l e s o f u n i v e r s i t y c u r r i c u l a r s c h e d u l i n g , a n da n a l y z e d ，d e s c r i b e dt h e r e q u i r e m e n t so ft h ec u r r i c u l a rs c h e d u l i n g , a n dt h e nc r e a t e dt h ec o m b i n a t o r i a l o p t i m i z a t i o nm o d e lo ft h ec o u r s e - t i m e t a b l ep r o b l e m t h i sp a p e rr e s e a r c h e dm a n yk i n d so ft h ea l g o r i t h m so fc o u r s e - t i m e t a b l e a r r a n g i n g f i n a l l yib r o u g h to u t 雒a l g o r i t h mb a s e do nt h eg r e e d ym e t h o dt h a tc a r l f u l f i l l e dt h er e a ls i t u a t i o n t h ei c s a g ( i n t e l l i g e n tc u r r i c u l a rs c h e d u l i n g a l g o r i t h mb a s e do ng r e e d ym e t h o d s ) a l g o r i t h m i nt h i sp a p e r , id e s c r i b e dt h ed e s i g no ft h ei c s a ga l g o r i t h m , a n dt h e n i m p l e m e n t e di t 、加mp r o g r a m m i n gl a n g u a g e , a n df i n a l l yt e s t e dt h ea l g o r i t h m t h e r e s u l to ft h et e s t i n gw o r kp r o v e dt h a t ：t h i sa l g o r i t h mg e ts t a r tf r o mt h er e a ls i t u a t i o n o fc u r r i c u l a rs c h e d u l i n g , a n dc a r lf u l f i l la l lt h er e s t r i c t i o n sb r o u g h tu pp r e v i o u s l y i t c a l lr e a c ht h el e v e lo fr e a la p p l i c a t i o nr e q u i r e m e n t a c c o r d i n gt ot h er e a lr e q u i r e m e n to ft h ei n t e l l i g e n tc u r r i c u l a rs c h e d u l i n gs y s t e m ， ia p p l i e dt h ei c s a ga l g o r i t h mt ot h es y s t e mp r o j e c ta n di m p l e m e n t e da ni n t e l l i g e n t c u r r i c u l a rs c h e d u l i n gs y s t e mb a s e do l lw e be n v i r o n m e n t a f t e rt e s t i n g , t h ec o u r s e a r r a n g i n gr e s u l ta n dt h ep e r f o r m a n c eo ft h es y s t e ma c h i e v e dt h ed e s i g nt a r g e t b a s e do nt h ew o r ko ft h e i n t e l l i g e n t c u r r i c u l a r s c h e d u l i n gs y s t e m ，i i m p l e m e n t e d a p r e l i m i n a r yc o u r s e - s e l e c t i n gs y s t e m t h eo p e r a t i o n o f c o u r s e - s e l e c t i n gc a nr u nc o r r e c t l yw i t ht h ec o u r s ea r r a n g i n gr e s u l t t h ec u r r i c u l a r s c h e d u l i n gs y s t e ma n dt h ec o u r s e - s e l e c t i n gs y s t e mc a na s s u r et h ed a t ac o n s i s t e n c y a n dt h er e l i a b i l i t yo ft h eu s e r s o p e r a t i o n s k e y w o r d sc o u l s et i m e t a b l e ；c u r r i c u l a rs c h e d u l i n g ；g r e e d ym e t h o d i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：盏虬日期：j 生动盟 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：三扯导师签名：季觚日期：2 盟 第1 章绪论 第1 章绪论 1 1 课题的研究意义 近年来，随着高校新生的扩招力度加大，专业设置、课程设置不断向深度 和广度发展，各高校都面临着教学资源紧张的问题。要在每学期期末的短暂时 间内集中进行排课工作，拿出一份能够统筹全校教学资源的课表，对高校的教 务处来说是一项非常艰巨的任务。 面对这样的新情况，以前传统的手- r a l ! 课方式工作繁琐、工作量巨大、效 率低下的缺点已越来越突出，己经难以适应新时代智能化教学管理的需求。因 此，各个高校都急需引进一个适用于本学校实际排课情况的计算机智能排课系 统，以降低排课的时间成本和人力成本，提高排课效率和排课质量。 所以，研究高效、灵活、自动化程度高的智能排课系统，不仅在高校的教 学管理工作中具有重要意义，也是新时代教育背景下的迫切需求。 1 2 课题的项目背景 随着网络技术的发展，利用网络进行教学和管理，使远程教育得到了蓬勃 的发展。本人所在课题组研究的“远程教学支持系统”便是顺应网络教育的发 展需求，开发的通用性远程教学管理平台，旨在： 为大中小学校提供基于w e b 的教学和管理方式； 实现网络化管理学校、教职工、学生信息和教学资源； 实现网络化教学管理、排课、学生选课、考试安排、成绩管理等学校日 常教学管理活动。 “远程教学支持系统 的实现，可以使教务人员、教师、学生在任何一台 连接i n t e r n e t 的计算机上完成传统教学模式中的各项教学活动和任务。 本人所做的研发工作智能课表编排系统，便是以“远程教学支持系统一 为整体依托平台的一个重要子系统。进入该课题的研究之前，“远程教学支持系 统 已实现了学校的分级管理、教职工管理、学生管理、班级管理、课程管理、 教室管理等等系列基础功能。本课题的研究任务是基于“远程教学支持系统 这些已有的功能和已建立起来的底层数据，研发一个智能课表编排系统，将其 嵌入到整个运行平台中以参与使用，保证智能排课功能和系统其他模块能够无 缝地协同工作，以协助“远程教学支持系统 全套功能的完善。 北京工业大学t 学硕j 二学位论文 曼曼曼! 曼葛! 皇皇曼曼i i m i m- m ! 曼鼍曼曼皇皇曼曼皇鼍曼鼍曼曼曼曼曼鼍曼皇 1 3 排课问题概述 排课是教学任务中的首要核心工作。排课的实质是为老师、学生的教学活 动合理安排时间上和空间上的教学资源，以保证教学活动有计划有秩序地进行。 其主要任务是给课程安排时间、分配教室，同时要保证没有冲突发生。 编排课表时，在保证教学资源的时间空间合理分配以及教学秩序能够有条 不紊进行的基本前提下，课表的安排也要保证教学质量。例如，数学课、英语 等必修课程尽量安排在上午，同一课程一周内的两个讲次之问的间隔尽量在一 天以上，以保证学生有充足的作业、消化时间等等。除此之外，还有其他细节 问题，比如同一个班的课程尽量安排在相距不远的教室里，避免课间休息时间 内出现大规模、长距离的人员流动等等。在教学改革不断深化，招生人数逐年 增加的情况下，做好有限教学资源的分配调度工作是有积极意义的。 排课系统的核心是处理排课问题所用的算法。使用有效的算法才能事半功 倍，也是保证排课系统的可行性、运行稳定、结果正确性的必要条件。排课问 题是一个n p 完全类问题，由于其本身的复杂性，寻找一个高效智能化的排课 算法是具有相当的难度的。 课表编排具有规模大、约束条件复杂以及执行过程中不断变化等特点，难 以实现自动化。以前很多学校的排课工作只能靠教务处的排课人员凭经验手工 完成，这一般需要花费大量的时间和精力，而且每学期初的调换课也是教务处 必须的额外工作负担。要想使各类资源优化利用，排课时需要考虑涉及全校上 上下下、方方面面的因素，入脑处理数据的能力有限，很容易出错，一旦出错 就会打乱正常的教学秩序导致教学事故。所以，完全以手工为主的排课管理已 远不能适应新形势的要求，这就需要有一个较为实用的排课系统使学校课表编 排工作能够实现自动化、高效化、人性化特点。应该如何实现这样的系统已成 为教学管理人员和技术专家共同面对的一个令人困扰的难题，这也是排课问题 仍是当前研究热点的原因所也。 1 4 排课问题研究历史及现状简述 排课问题也可称为课程时间表问题( c o u r s e - t i m e t a b l i n gp r o b l e m ) ，是一个 涉及多因素的基于时间规划和组合优化的问题。由于该问题具有的难度和挑战 性，许多研究者在其中投入了大量精力，并取得了丰硕成果。从二十世纪五十 年代以来，国际上就有人开始研究计算机自动排课问题。1 9 6 2 年，g o t l i e b c c 教授就对课程表问题进行了形式化描述l l 】，第一次将排课问题形式化描述为一 系列规划组合问题。到了7 0 年代，s e v e n 等人将排课表问题理论化【2 1 ，证明 该问题是一个n p 完全类问题，根据计算理论和难解性原理，排课问题到目前 2 第l 章绪论 曼曼曼曼曼曼曼曼曼! 皇曼曼曼! 曼鼍曼曼曼曼i 一 _ie l l ii 量 为止，还没有多项式算法。当问题的规模增大时，解的数目呈指数函数增长， 在一般的实际情况中是不可能准确地求出最优解的。 随着算法复杂性理论的完善，人们不再强调一定要求得最优解，更多的研 究转向实际应用的角度。能够得到较好的解的近似算法，或以一定的概率保证 解的质量的随机算法的研究越来越受到重视。于是兴起了现代智能优化技术， 出现了崭新的智能优化算法，诸如人工神经网络、遗传算法、蚁群算法、进化 计算、模拟退火、禁忌搜索及其混合优化策略等。自从2 0 世纪8 0 年代以来， 这些优化技术在诸多领域得到了成功应用，也使得排课问题的研究也出现了崭 新面貌，直到今天仍有巨大的发展空间。 1 5 本文所做工作及主要特色 1 5 1 本文所做工作 为了研制智能课表编排系统，本人基于已有的“远程教学支持系统的功 能和数据，认真做了大量需求分析。在对比了目前存在的排课算法的优点和缺 点和权衡了需求分析中的各种因素之后，提出了一种基于贪婪搜索策略的排课 问题解决方案，所做的具体工作如下： ( 1 ) 分析了远程教学支撑平台的教务流程的特点以及高等学校制定课表 的原则，对排课需求进行了分析、描述，建立了排课问题的组合优化数学模型。 ( 2 ) 提出了一个比较符合实际情况的基于贪婪策略的排课问题求解算法 一一i c s a g ( i n t e l l i g e n tc u r r i c u l a rs c h e d u l i n ga l g o r i t h mb a s e d0 1 1g r e e d y m e t h o d s ) 算法。此排课算法经过课元排序后，将每个课元的排课操作分为课元 时间贪婪求解和课元教室贪婪求解两大步骤。 ( 3 ) 编程实现了提出的i c s a g 算法，并对此算法进行了测试。测试结果 表明：i c s a g 算法大大简化了教师、学生、教室这三者的冲突处理过程，具有 较快的求解速度；此算法从实际情况出发，有效地满足了事先规定的各种排课 限制条件。 ( 4 ) 实现了一个基于w e b 的智能课表编排系统。此系统分别实现了排课 专家、教务排课人员、普通教师、学生等各种角色的功能界面。 ( 5 ) 对整个智能排课系统作了功能测试和系统测试，测试证明：i c s a g 算法嵌入到智能排课系统中仍能正确运行，并且不占用过多的系统资源，能够 取得较快的运行速度和满意的排课结果；排课系统各部分功能界面均能正确呈 现，界面具有易操作性和友好性。 ( 6 ) 基于智能排课系统生成的课表结果，初步设计并实现了一个选课系 统，该系统分为选课管理员的选课管理和学生登录选课两部分功能：对这两个 北京工业大掌工学硕士学位论文 角色的功能进行了分别测试和综合测试，测试表明：选课系统能够基本实现每 学期全校学生选课的任务。选课系统能够基于排课结果正确运行，保持了数据 的一致性和选课操作的可靠性。 1 5 2 主要特色 由于排课问题是一个有约束的、多目标的、难解的组合优化问题，所以采 用纯数学算法，或者仅基于某个单一的算法框架进行排课，是很难实现的。本 文研究的智能排课系统的核心排课算法，是基于贪婪算法的基本思想，并引入 各种具体排课策略加以实现的，这是求解排课问题的较明智选择。 本文以北京工业大学教务排课特点为需求分析的基础，研究排课问题中的 复杂因素和约束条件；在本人对目前各种已有的排课算法的学习和研究的基础 上，对己有排课算法的不足加以规避和改进，建立能够较大程度地反映实际排 课情况的智能排课系统，提出了一个课表自动编排算法，并且在系统中加以实 现和应用。 1 6 本文组织结构 本论文正文内容的组织结构如下： 第二章智能排课系统的需求分析：描述课表制定原则；对本系统作了需求 分析；对系统使用角色进行划分。 第三章排课模型的建立：总结了排课问题的概念模型；建立了排课问题的 组合优化模型，其中做了符号约定、总结了约束条件、指名一般意义下的目标 函数定义；分析了排课问题的求解复杂度。 第四章智能排课算法简介：简单介绍了目前存在的各种排课算法，指出了 排课问题当前的研究趋势及存在的问题；阐明了本系统采用贪婪法进行排课的 原因。 第五章本系统贪婪排课算法的详细描述：介绍了排课系统的使用流程；描 述了本系统i c s a g 贪婪排课算法所作的若干排课约定和i c s a g 算法的具体排 课策略；对i c s a g 算法进行了分析总结。 第六章系统的实现与测试：介绍系统总体架构和排课系统的模块划分：介 绍了排课使用的测试数据；展示了课表生成结果。 4 第2 章智能排课系统需求分析 第2 章智能排课系统需求分析 本章首先总结了课表制定一般原则，然后对本系统做出了排课需求分析， 划分了排课系统的使用角色。 2 1 课表制定的原则 课表编排的科学与否，直接影响到教学活动的有序和效果，必须在充分认 识课表功能的前提下，依照编排原则，进行科学地编制。关于排课原则，文献 【3 】【6 】从人文因素角度对排课问题作了分析，从大体上来说，课表的功能包括 内部功能和外部功能。 内部功能： ( 1 ) 课表是教学活动的总调度，是学生在校活动的有序排列。 ( 2 ) 课表是教学计划在时间和空间上的具体体现。 ( 3 ) 课表是在校教师、学生、管理人员与教室、教学设备及各种教学器材 等诸多事物相互联系、相互作用的纽带与桥梁。 外部功能： ( 1 ) 课表是学校教学思想、改革措施的外在反映。 ( 2 ) 课表是学校教学体制、管理体制的一种特殊表达形式。 ( 3 ) 课表是优化教学秩序和教学环境，充分合理地利用学校的一切人力、 物力资源，提高教学质量的重要保证。 课表编排涉及学校上上下下、方方面面的工作。编排部门要协调好教学、 科研等各种关系；处理好教师、学生、教室、场地、时间多种矛盾；最大可能 满足各院系、部门、各教研室的不同要求。因此，课表编排过程就是完成一个 动态的闭合系统工程，在制定和执行课表过程中，需要坚持多方面原则。 ( 1 ) 整体化原则 课表要为完成教学计划服务，为提高学校教学质量和实现培养目标服务。 学校的中心工作是教学，课表要从教学需要出发，使教师、教室、场地、时间 等首要保证教学需要。课表要面向全体学生，一切为学生的德智体全面发展德 复合型人才服务。课表要照顾教师和学生的利益和要求，但必须局部服从全局， 在整体利益不受到损害的前提下，局部和个体利益可以给予照顾。 ( 2 ) 最优化原则 学校管理的目标是以最少的资源( 人力、物力、财力和时间等) 达到最好的社 5 北京r t 业大学t 学硕十学位论文 会效益，这就是最优化原则。编排课表要从最优化原则出发，对现有的教师、 场地、教室、设备及学生状况等进行调查和研究，以寻求各种教学活动的最佳 编排组合方式。要达到课表科学、合理、周密、可控，以创造出最优的教学环 境和教学次序，使教师发挥最优的教学效果，使学生的学习效果和质量达到最 优。 ( 3 ) 有序性原则 任何系统都有其自身存在的具体的时空形式。时空形式不同，构成不同的 系统结构作为动态闭合系统存在的课表，根据教学计划的要求，各学制、各专 业、各年级、各班都有自己的课程编排方式，由于教师、场地、教室、时间、 班级的相互联系而形成一个有机会的整体，相互作用、相互制约、相互影响、 使课表系统按照固定有的规律井然有序地运行着。 ( 4 ) 开放与闭合原则 课表在编排过程中应该表现为开放式。编排部门应广泛征求学校各院系、 各部门、各教研室的意见。了解他们的要求和愿望，对于上课时间、场地安排 学科术科课程的搭配充分尊重教师的意见。但是，课表在管理形式上有是闭合 的。正式课表下达后，它就成为指挥教学活动的总调度、总权威、任何人、任 何部门未经教学管理部门同意不得擅自更改和调整。否则正常的教学次序就会 被打乱，打破稳定和平衡。当然，个别课程的调整在所难免，但这只能是在统 一指挥下的调度，是局部的、暂时的。只有这样才能保证课表结构的稳定性， 维持系统的动态平衡，保证教学活动的有序。 ( 5 ) 反馈原则 在控制系统中，控制与反馈互为前提，处于统一体中，由于反馈的方向是 由被动系统到主动系统，所以它是一种反作用。课表确定之后成为一个控制系 统，管理部门要及时听取执行过程中的反映，了解教学活动、教学次序、教学 效果，形成多条反馈渠道，及时、全方位收集反馈信息。例如，由教师到教研 室到院系到教学管理部门的反馈渠道；由学生到辅导员到院系到教学管理部门 的反馈渠道。利用反馈信息，最大限度地把课表在执行过程中暴露出的矛盾解 决在萌芽之中。情况是复杂的，外界变化因素很多，实践中总有一些意想不到 的问题出现，课表编排不可能十全十美，也不可能适应外界的一切变化，因此 信息反馈是课表控制系统的必不可少的过程和手段。 2 2 本系统需求分析 2 2 1 排选课详细需求分析 从手工排课的角度来看，排课问题需要考虑的因素，几乎是全校性的。学 6 第2 章智能排课系统需求分析 校是一个有机组合而成的整体，其个组成部分既各司其职，有密切合作，以保 证日常正常教务工作的运转和教学任务的完成。从排课过程可能引起潜在冲突 的角度，可以将排课问题涉及因素逐项考虑如下： ( 1 ) 时间：在排课问题中涉及关于时间的概念有学年、学期、周、天、 时段、节、课时等。上课时间一般是按照周来计算的( 指周课表) ，从开学第l 周至第n 周。每周的课表一般来说是一样的，但也有可能存在不一样的周，如 单双周或某些课程不是从第一周开始的情况。 每周分为m 天( m 7 ) 排课。每天可分为三个时段上午、下午和晚上。每 个时段分为p i 个排课时间单位( 一个排课时间单位算作一大节课，或称之为一 个排课时间片) ，比如上午为p l ，下午为p 2 ，晚上为p 3 。一节课可以是单课时， 也可以是两个课时或多课时，每个课时可以算作- d , 节课进行授课。 在一周内，开课多次的课程，应该选择相隔一定的天数进行排课，如一周 三讲次的课程，可以在周一、周三、周五分别上一个讲次。其中m 、n 、p 以 及同一课程的多次上课方式，不同的学校有不同的安排。系统应给出相应的机 制来设置这些参数。 ( 2 ) 课程：每个课程都有自己的编号、名称、开课学院和课程性质属性。 课程属性划可以划分为：公共必修课、公共选修课、学院必修课、学院选修课、 专业必修课、专业选修课。 每门课程可以指定一些特定的教师来教授。每门课程可以有多个班级合并 上课，合班班级往往是同届的同专业或相似专业，但有时候是跨系的。有的课 程，如公共选修课，在排课时可以不指定授课对象，其授课对象待选课活动结 束后才可确定。有的课程是面向一定授课对象的选修课，比如学院选修课、专 业选修课，此类课程在排课时，应该为所面向的所有班级安排统一的上课时间， 以保证该专业或者该学院的每一位同学都有同等机会选修此课程。 每门课程都有特定的学分，一个学分对应一定数量的课时，在排课时，基 于该课程所具有的课时数安排上课的起始周、截至周以及周学时安排。 另外，对于每一个专业，每一个学年应该完成一定的课程任务。教务机构 应该为每一个专业制定培养计划，以保证教学任务的落实和审核工作。 ( 3 ) 教学区域：大学的校园占地面积通常比较大，可以有多个教学楼宇， 连接得比较紧密的楼宇可以视为一个教学区域。引进这个概念的目的是为了减 少学生和教师在课间的走动范围。 ( 4 ) 教室：每个教室都有编号、名称、教室类型。每门课程应规定特定的 上课教室类型，如普通教室、多媒体教室、语音教室、实验室等。每个教室都 隶属于某个教学区域。每个教室在同一时间内只能接纳- i 1 课程的授课，并且 教室容量应该大于至少要等于上课总人数。但是，上课的人数远远小于教室容 7 北京工业大学工学硕十学位论文 量时，这种情况也是不合理的。另外，大学的上课教室一般是流动的，但也会 有极个别的班级具有固定的上课教室，在排课前应予以绑定。 ( 5 ) 学院：每个学院有编号和名称。每个学院的学生按照入学时间的不同， 划分为不同界别。每个界别设置若干专业，教务处为每个界别的每个专业制定 培养计划，安排其每个学期应该修完哪些课程。 ( 6 ) 班级：每个班级有一个班级编号。每个班级隶属于某个学院的某一个 专业，并且按入学时间分为不同届别。在排课时，每个班级同一时间只能上一 门课程。 ( 7 ) 教师：每个教师都有自己的职工编号和姓名。每个教师同一时间只能 上- i - j 课程。每个教师都可以提出自己期望的上课时间和不期望的上课时间。 并且某些“资深”的教师可以给予较高的排课优先级，排课时给予优先照顾。 ( 8 ) 预排课与调课：在进行自动排课之前，对于某些关键课堂，可以预先 进行上课时间安排和教室安排，以确保这些关键课堂的排课质量；在自动排课 运行之后，还可以对排课结果做出人为的局部调整。 ( 9 ) 课表：课表生成之后应该能够以不同的视图呈现，以方便各类人员的 查询。可以查看全校的排课情况，也可以查看单个教师、单个班级、单个教室 的排课情况。 ( 1 0 ) 选课：在一个学期的课表确定之后，由教务人员组织全校性的选课 活动。为保证选课任务的顺利进行，教务处应该为每个专业设置规定的选课时 段，并且为每个待选课的课堂设置限制选课人数。 每个学生应该在所属专业规定的选课时间登录选课系统进行选课操作。学 生选课结束后，可以看到该学生个人的课表。 在选课结束后，如果学生在选课时存在某些方面的选课失误，可申请教务 处教师补选退选课。另外，如果某些课堂选课人数不足，教务处可以考虑取消 该课堂，通知学生该课堂已经取消，应补选其他课程。 2 2 2 排选课系统角色划分 如图2 1 所示，根据上面的需求分析，整个排选课系统的功能权限对不同的 对象应有所区隔。可以使用排课系统的人员划分为5 个使用角色：排课专家、 教务管理员、教师、学生、选课管理员。 其中排课专家是使用排课系统的主体和关键角色，由其负责所有排课数据 的组织、运行排课等所有排课操作。教务管理员、选课管理员具有以不同视图 查看排课课表的权限。教师和学生仅具有查看自己课表的权限。 选课系统有两个使用角色：选课管理员和学生。在课表编排之后，选课活 动之前，由选课管理员进行各项选课设置，然后学生登录选课，全校选课任务 结束后，由选课管理员进行选课后的一些处理工作。 第2 章智能排课系统需求分析 图2 - 1 排选课系统角色划分 f i g u r e2 - 1t h eu s e l r o l e so fc o u r s es c h e d u l i n ga n ds e l e c t i n gs y s t e m 在图2 1 中，排课专家、选课管理员、教务管理员是将教务处人员角色进一 步划分所得到的三种登录角色，以使教务处各类人员各司其职。介绍如下： 排课专家具有最大的使用权限，他的使用权限包括： 课程管理：管理本学校所开课程信息，一个课程的信息包括课程编号、课 程名称、开课学院、课程性质、学分等属性。 专业、班级管理：分学院录入每一届别有哪些专业，每个专业设置哪些班 级。为每一届别的每个专业设置培养计划，规定其每学期应该学哪些课程。 教室管理：包括校区管理、楼宇管理、教室类型管理、教室信息录入。录 入每一个教室的信息时，需要输入该教室所在的校区楼宇、教室类型、教 室容量。 排课设置：排课设置包括所有排课前必须录入的数据，包括排课课表的建 立、时间模式库的录入与维护、全校时间片优先值、各种排课限制条件的 9 北京工业大学工学硕士学位论文 录入、组建排课课堂等等。 排课：排课包括预排课、运行排课和排课后调整三个步骤。 课表查询：经过排课生成课表数据后，可以按照全校课表、单个教师、单 个班级、教室课表等多种视图进行查看。 选课管理员在智能排课系统中只具有按照各种视图查看课表的权限，而不 能对排课结果做出干预。但是在选课活动时，选课管理员专门负责以下两部分 任务： 选课设置：在选课前需设置好每门选课课堂的限选人数、规定每个专业的 选课时段。在全校的学生选课结束后，选课管理员可查看每个课堂的选课 情况，如果某些课堂选课人数过少，可考虑取消课堂安排补选。 补选退选：因学生在选课过程中的误操作、或者因某些课堂已取消，可由 选课管理员为个别学生单独进行退选补选的操作。 教务管理员负责学校人员的基本管理工作，包括教师基本信息的管理和学 生基本信息的管理。他在智能排课系统中也只具有按照各种视图查看课表的权 限。 除上述三个教务处的人员身份，可以参与使用本系统的还有两个角色，即 教师和学生： 教师只具有查看自己上课课表的权限，该课表中，只列出该教师在本学期 的所授课程的上课时间地点。 学生在规定的时段内登录选课系统可以进行选课操作；选课结束后可以看 到专属于自己的个性化课表。 2 3 本章小结 本章从排课的实际情况出发，整理了排课时的各方面因素。这些排课的需 求分析将作为设计排课算法和排课系统的重要基础。 排课系统登陆角色的划分使教务处人员分工更加明确，便于开展教务管理 工作。 1 0 第3 章排课模型的建立 第3 章排课模型的建立 本章总结了排课问题的概念模型，在此概念模型基础上建立了排课问题的 组合优化数学模型，分析了实际情况中课表求解的难度。 3 1 排课问题概念模型 从概念模型上讲，排课是一个四维空间上的组合优化求解问题。这四维分 别为教师、学生、时间和教室，约束条件为教学计划和各种现实情况的特殊要 求【刀。排课问题的实质就是解决各因素之间的冲突，最终形成符合需求的课表， 并以不同对象的视角加以呈现，如图3 1 所示。 图3 - i 课表问题概念模型 f i g u r e3 - it h ec o n c e p tm o d e lo fc o t t r 靶t i m e t a b l ei ) r o b l e t n 衡量一个课表是否符合需求，有两方面的含义：首先，课表应该是没有冲 突的，它必须满足一些硬约束条件：其次，编排出来的课表还应满足一定数量 的软约束条件，以实现课表编排的人性化原则。常见的硬件约束条件和软件约 束条件总结如下： 1 课表的可行性硬约束条件：硬约束条件是在排课过程中必须满足的 约束条件，又可细分为基础硬约束条件和附加硬约束条件，分别如表3 1 、表 3 2 所示： 北京工业大学工学硕二t 学位论文 表3 1 基础硬约束条件 见l b l e3 1b a s i ch a r dr e s t r i c t i o n s 基础硬约束条件 1 每位教师在同一时间段内，最多只能参与个教学任务。 2 每个班级在同一时间段内，最多只能参与一个教学任务。 3 每个教室在同一时间段内，最多只能安排一个教学任务。 只要满足表3 1 中三个条件就能够保证排课过程中不发生冲突。 表3 - 2 常见附加硬约束条件 t a b l e3 2a d d i t i o n a lh a r dr e s t r i c t i o n s 附加硬约束条件 1 求解的教室容量一定要大于授课对象的总人数。 2 满足教室特殊要求，某些教室在固定时间段不能占用。 3 满足教师特殊要求，某些教师在固定时间段不能排课。 4 满足班级特殊要求，某些班级在固定时间段不能排课。 表3 2 中的附加硬约束条件是指课表在满足了表3 1 基础硬约束条件，即已 保证没有排课冲突的情况下，还需要进一步满足的硬规定条件，以保证课表的 切实可行性。 2 课表的可用性嗽约束条件：衡量一张课表是否是一张高质量的课表， 除了应该满足上述硬约束条件以保证课表的切实可行性之外，还应该考虑大量 的人文因素，以求尽可能地达到课表编排的人性化标准。这些人为因素可以总 结为一系列的软约束条件，它们是衡量排课方案优劣的标准。在排课过程中， 通常应该纳入考虑范围的常见软约束条件在表3 3 中列出。 表3 - 3 常见软约束条件 t a l b l e3 3s o f tr e s t r i c f i o n s 软约束条件 1 周排课次数大于l 的课程，要尽量有合理的间隔天数。 2 重要课程要安排在一天中较好的时间段。 3 若同天内同一门课程连续排课节数不是很多，最好不跨越午休等大段的休息 时间。 4 体育课一般不安排在上午第一个时间段，并且体育课后一般不安排要求逻辑 思维的课程。 5 教室容量超过课元授课对象总人数的部分要尽量小( 节省资源) 。 6 尽量将同一课元的不同讲次安排在同一教室。 7 班级课表每天的排课量要趋于平均。 8 尽可能缩小班级在连续的两个时间段内更换教室的距离。 9 尽量满足教师提出的主观排课喜好。 1 2 第3 章排课模型的建立 3 2 排课问题组合优化数学模型 由于排课问题所考虑的因素非常繁多，在总结排课问题的数学模型之前， 在此先做统一的符号约定，然后再对排课组合优化模型的约束条件和目标函数 加以表示。 3 2 1 符号规定 课程集合：l2 ，l ，2 ，p ) ，参加排课的课程共有p 门。 班级集合：c2 c 1 ，c 2 ，c n ，参加排课的班级共有n 个。 一个班级的人数表示为：c n u m ( c ) ( c c ) 。 在高校排课时，很少只进行单班课的排课，一般都是排合班课，将若干个 班级组织成为一个授课对象组，一个授课对象组可以表示为： c c 擅o u p 2 c 1 ) c 2 ，c o ) c ac cg l g ) ，一个授课对象组有g 个班级。 教师集合：h2 h l , h 2 ，h m ) ，参与排课的教师共有m 位。 时间片集合：t2 t t , t ：，t q ，一个星期共有q 个时间片可以排课。其中 每个时间片可表示为一个二元组：t i = ( d a y t h ，n o d u l e ) 。d a y t h 标识时间片在星期 几( 天次) ，n o d u l e 标识时间片处在第几节课上( 节次) ； 赫 教室集合：r2 _ ，r 2 ，k ，全校共有k 个教室进行排课。 教室类型集合：s2 s l ，s 2 ，s d ) ，全校共有d 种不同的教室类型。 一个教室的容量、类型分别表示为：c a p ( r ) 、t y l e r ) ( r r ) ； 3 2 2 组合优化的约束条件 排课问题的求解目标是寻找一个从授课任务到时间教室的映射关系f ： f ：l c c l e c 专( t ，r ) t x r ( 3 1 ) 式( 3 1 ) 中l e c 表示编排一个课表的所有排课任务的集合，l e c 表示一个排课 任务。式( 3 1 ) 的映射关系满足约束条件，并且具有最优的目标函数值。这里把 满足合法课表的强制约束条件作为排课模型的约束条件，表示如下： 首先约定： 北京t 业大学t 学硕士学位论文 x c ： ：1 黧：c n 在时间。在教室上教师k 的课程)ahml p r k t q 2 “否则 。( 3 - 2 ) 约束1 ：一个班级在同一时间只能参与一个排课任务 1 ，( n = l 2 ，n ，q = l 2 ，q ) ( 3 3 ) 约束2 ：一个教师在同一时间只能参与一个排课任务 1 ，p = l 2 2 ，p ，q = l ，2 ，2 ，q ) ( 3 - 4 ) 约束3 ：一个教室在同一时间只能安排一个排课任务 胁e 问e 删e p ：x c n h 州。辄厶勘= l ，2 ，q ) ( 3 - 5 ) 约束4 ：教室容量不小于一个排课任务的授课对象总人数，且教室类型满足 规定的类型 设班级c n 、教师j i i m 、课程z ，、教室r k 所在排课任务为 ( 3 6 ) l e c = ( 1 p ，h 。，c g r ，p ，s ，w ) 其中，c 。c g r ，c g r 是包括班级c n 在内的一个授课对象组；s 代表该排课任 务要求的教室类型。则约束4 表示为 r 4 ：n u m ( c g r ) c a p ( r k ) ；t y p e ( r k ) = s ( 3 7 ) 3 2 3 目标函数定义 在排课过程中，一般都是在满足硬约束的基础上尽量地去满足软约束条件， 因此一般把软约束条件作为目标函数。因为这些软约束条件比较复杂，并且常 常含有难以用符号表达的人文因素，所以这里暂且用一个函数f i x ) 表示，并假 设使得胀) 求取最大值的排课方案为最佳排课方案。 由此，根据目标函数和约束条件，建立排课问题决策优化模型的一般形式， 如公式( 3 8 ) 所示： m a xf ( x ) r i r ： ( 3 - 8 ) r 3 r 1 4 m & k 纠 p 一 m 删 r m k k 料m 艄脚 复r 第3 章排课模型的建立 3 3 排课问题复杂度分析 上一小节总结了排课问题的数学模型，它是一个组合优化问题。文献【8 阐 述了一般时间表求解问题的复杂度。经典的组合规划问题的求解，主要依靠约 束条件来实现。只要约束条件充分，那么最优的组合方案就能被唯一确定。因 此，从理论角度来说，组合规划作为描述课表问题的数学模型并无不妥，但在 实际工作中，随着论域范围的膨胀，即组合方案数的增加，规划问题也就变得 十分复杂。 我们可以考察一下一种极其简单的课表情况，假设工作日仅为周一至周五， 一天内仅有3 个排课单元，则从课表安排类似空格填充的角度看，课表变为3 5 的表格，如图3 2 所示。 图3 - 2 一张3 5 的课表 f i g u r e3 - 2a3 5t i m e t a b l e 设课表的空格数为n ，一个开课任务的计划排课次数为m ，则此门课程上课 的组合方案数为c ：，考虑m = 1 ，2 ，3 ，1 1 - - - - - l ，2 ，1 5 ，当n 和m 变化时， 课表编排方案数的变化情况如表3 4 所示。 表3 4 课表组合方案数量变化举例 n b l e3 - 4t h ei n c r e a s eo fc o u r s ef i m e t a bea s s e m b l yn u m b e r s 义 1234 567891 0l l1 21 31 41 5 1 l234 567 8 9l o1 11 21 31 41 5 2 0l36l o1 52 l2 83 6 4 55 56 67 89 11 0 5 3oo 141 02 03 5