基于启发式算法的高校排课系统的设计与实现

基于启发式算法的高校排课系统的设计与实现 摘 要 每学期的排课问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 是教务管理软件设计中的重点和难点。在组合优化范畴 NP NP J2EE MVC UML JAVA WEB J2EE- IV - 关键词:启发式算法,教务管理,排课, 设计及数据库的设计。 方式的排课系统的软件结构设计、软件流程设计、排课算法设计、关键模块 图,详细介绍了基于 的需求分析、软件设计与实现的整个过程。使用 架构,将面向对象技术应用于教务排课系统 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 和 设计部分遵循 排课的教务管理流程,使计算机最大程度的应用于教务管理的各个环节。 整,最后由计算机自动 机自动生成各学期初始课程设置表,再由教务人员进 行调 了一种依据教学 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ,由计算 论文分析了采用计算机排课的用户需求,提出 忌搜索算法的搜索速度和搜索的力度。 的合理设计,提高了禁 出了满足要求的优化解。论文通过对禁忌搜索算法中 参数 决排课中优化问题,得 其次应用学习策略,经过参数优化的禁忌搜索算法, 来解 供了一个好的起始点; 发式算法,它能够求出较优的初始解,给禁忌搜索算 法提 探测策略的新的一步启 本文通过分析排课问题的特点,首先提出了一种基 于前景 再用智能算法搜索出最优解。 传统启发式算法通过一步式算法得出初始解, 排课的效率。 计了新的算法,提高了 完全问题的算法进行了分析和优化,结合排课的特点, 设 完全问题。本文在查阅大量相关文献的基础上,对现有解决 内,排课属于 基于启发式算法的高校排课系统的研究与设计 The Research and Design of University CoursesArrangement Base on Heuristic AlgorithmAbstract The courses arrangement is a key in soft development of educational management soft. The courses arrangement can be seen as NP-complete problems in combination optimization theory. On the basis of investigations on correlated literature, this paper analyzes and optimizes the existing algorithms of NP-complete problems, then designs a new algorithm according the characteristics of courses arrangement in our university. By using this algorithm, the efficiency of courses arrangement has been improved greatlyTraditional heuristic algorithms obtain the initial solution by using one-step algorithm, and then search the best solution through intelligent algorithm. This paper started with the analyzing of course arrangement’s characteristic. First, a new one-step heuristic algorithm is advanced base on foreground search strategy. It can receive a better solution which gives a nice beginning to tabu search algorithm. Second, it applied learning strategy to optimize the tabu search algorithm, resolved the optimization of course arrangement problem, received the optimized solution that meet the requirementThis paper increased search speed and deepness of tabu search algorithm through designing rational parameters This paper analyzed the demand of course arrangement, presented a educational management flow that automatic generate initial courses setting table by computer, adjust course setting table by education manager, automatic arrange course by computer. It furthest applies computer in the process of educational managementThe design complied J2EE criterion and MVC framework. It used Object-Oriented technique in educational management system which includes demand analysis, software design and implementation. The paper presented the design of system includes framework, flows, algorithms, primary modules and database tables by using UML diagrams Key Words : heuristic algorithm, educational management, course arrangement, J2EE - V - 基于启发式算法的高校排课系统的研究与设计?录 目 摘 要I AbstractV 第 1 章..1 1.1 1 1.2. 2 1.3. 3 1.3.13 1.3.23 第 2 章5 2.1. 5 2.1.1 5 2.1.26 2.2. 6 2.2.16 2.2.27 2.2.39 2.2.4.10 2.3..11 2.3.1.11 2.3.2.12 2.3.3.13 2.3.4 Exploring..14 2.3.5 Learning14 2.3.6.15 第 3 章..16 3.116 - VI - 教务管理系统的特点 排课系统需求描述 算法分析 算法 算法 学习策略 前景探测策略 靠边策略 基于拟人策略的启发式算法 算法描述 传统的直接启发式算法 问题的数学描述 算法的提出背景 基于启发式搜索的排课算法 启发式搜索理论 一般搜索原理 启发式搜索理论 排课系统的算法策略 本文的组成 本文的主要内容 论文的主要内容及论文组成 国内外研究水平和发展趋势 课题的来源及意义 引言 基于启发式算法的高校排课系统的研究与设计 3.217 3.3.18 3.3.1..18 3.3.2..22 3.4..23 3.4.1..23 3.4.2.24 3.4.3.26 第 4 章.28 4.1 J2EE..28 4.1.1 B/S.28 4.1.2 J2EE29 4.2 MVC.32 4.2.1.32 4.2.2 MVC34 4.3..38 第 5 章..41 5.141 5.1.141 5.1.2..41 5.243 5.3.45 5.448 5.4.1.48 5.4.249 5.4.3.50 5.4.4..51 结 论53.54 - VII - 参考文献 冲突的检测和处理 自动排课 教学班调整 初始课程设置 主要模块设计 数据库设计 软件结构及流程控制设计 排课系统用例说明 排课系统用例图 排课系统分析 排课系统分析设计 系统级平台概述 设计模式 设计模式 设计模式 体系结构 构架 应用面临的挑战及多层 体系结构 排课系统架构 排课过程的约束条件 计算机编排课表的逻辑模型 人工排课操作的基本模型 计算机编排课表的逻辑模型 加强学校课程表编排管理 确立高校课程表编排原则 高校课表编排若干问题的思考 教务系统的工作流程 基于启发式算法的高校排课系统的研究与设计 致 谢56 - VIII - 基于启发式算法的高校排课系统的研究与设计 第 1 1.1 础技术框架平台以及办公自动化、本科生教务 管理、研究生教务管理、人事管 [1] 。 置的课程安排时间和地点,从而使整个教学能 够有 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 有秩序地进行。至今为 课表编排是一个涉及多种因素的组合规划问题,它要保证在课程安排中教 [2]- 1 - 用领域中。 很自然地进入到这一应 突出。由于计算机具有运算速度快、处理能力强等特点, 工排课的缺点就越来越 生人数的不断上升,课程设置不断向深度和广度发展,手 育体制改革的深入,学 月的时间,工作量大、排出的课表不宜调整。随着我国教 花费教务人员一、二个 名学生和近百个专业的教师安排出合理的课程表往往需要 。然而为上万 门课程等情况),并且要满足教师的要求和教室资源等约束条件 同一个时间段安排了多 级安排在了同一个时间、同一间教室,或为同一名教师在 同课程的两个或多个班 师、学生、教室不能产生冲突(所谓冲突,就是将需上不 得课表问题至今仍未完全解决。 复杂以及规律不断变化等特点,使 要求 和经验。但是,由于它具有规模大,约束 ,取得了许多研究成果 止,国内外对课表的研究工作已经进行了长达四十年之久 复杂,其实质就是为学校所设 排课工作在高校教学管理中十分重要、又相当 用系统建设急需解决的技术难点之一。 ,也是“数字校园”应 功能模块。其中自动排课模块是教务系统的重要组成部分 管理、开课计划、学生选课等 教务系统包括专业管理、课程管理、教学方案 理、学生管理和科研管理,以及资产管理、后勤管理等系统的软件开发 数字校园”应用系统建设的基 “数字校园”应用软件建设项目应该包括:“ 一体的一种新型数字化的工作、学习和生活环境。 学、科研、管理、校园生活为 “数字校园”是以校园网为背景而构建的集教 课题的来源及意义 引言 章? 基于启发式算法的高校排课系统的研究与设计1.220 50 60 [3] 1975 1962 Gotlieb 1975 Even 在美国 STAM J,COMPUT 上发表类的“ On the complexity of timetable and [4][5] multicommodity flow problem NP 高到了理论的高度。这类问题的求解是典型的 时间表与多物流的决策问题 的求 机算法的尝试都未能获得满意结果。因此,人 们寻求有效算法的探索才告一 段 [6] 。 近 40 0-1 0-1 线 Mihoc 和 Balas Krawczk Junginger Tripathy 问 NP [7] 。 - 2 - 大多数学校的课表编排问题来说没有实用的价值 际相差太远,所以对于 将课表编排转化为二部图匹配问题。这样的数学模型与实 简单的情况下才可以 完全问题,只有在极为 问题,但是图的染色体问题也是 图论的角度来求解课表 题并提出了大学课表的数学模型。此外,有些文献试图从 则把课表问题视作整数线性编程 将课表问题简化为三维运输问题,而 则提出一种线性编程的方法。 将课表公式化为一个优化问题, 性优化问题的分支??定界技术却只适用于规模较小的课表编排, 变量的解,但是其计算量非常大。解决 整数规划模型将问题归结为一组 年来,人们对课表问题的计算机解决法做了许多尝试。其中,课表编排 课程表这个问题上 具来实现自动编排实际 落,而将更多的精力转移到如何借助计算机这一现代化工 型,研究设计一种计算 解。用计算机解决这个人文决策问题,从数学角度建立模 课表的复杂性的认识提 述确立了课表编排问题的学术地位,把人们对计算机编排 。他的论 完全类问题 ”证明了课表问题是一个 等人 年, 并提出过一些新的算法模型,但始终未能找出一个有效算法。 等问题作了许多探索, 程表的数学模型,接着人们对这个模型算法、解的存 在性 提出了一个构造课 年, 方法,目的是找到一个解决问题的有效算法。 年以前的一段时间里,人们主要从构造算法模型入手,研究其解决 。直到 年代初,国外就有人开始对课程表问题进行了研究 年代末、 世纪 国内外研究水平和发展趋势 而且对于推动教学的发展也起到非常重要的作用。 排课任务中解脱出来, 短、人力省和质量高的优点,不但能使教务人员从繁杂的 件的可行结果,具有排课时间 用计算机进行排课能够快速地得到满足约束条 基于启发式算法的高校排课系统的研究与设计 20 90 Uastapu Arabinda Tripathy Montreal [8] Jean Aubin 和 Jacques Ferland 等 法、图论方法、拉格朗日松弛法、二次分配型 法等多种方法。由于课表约束复 [9] 20 80 期,具有代表性的有:南京工学院的 UTSSA University Timetable Scheduling System TISERTimetable Scheduler [10][11][12][13] 各个学校的教学体制,不宜进行大量的推广。 各个学校应从自己的实际情况 出 1.3 1.3.1J2EE MVC UML JAVA WEB 1.3.2UML - 3 - 建模工具进行详细设计。 算机排课需求分析,确定需求??利用 ?计算机排课过程分析??计 本文按照以下顺序展开论述:排课算法分析? 本文的组成 计、软件流程设计、排课算法设计、关键模块设计及数据库的设计。 方式的排课系统的软件结构设 图,详细介绍了基于 过程。使用 软件设计与实现的整个 架构,将面向对象技术应用于教务排课系统的需求 分析、 标准和 特点,提出了改进的“基于拟人策略的启发式算法”,并遵循 校教务管理系统”排课的业务 本文在传统启发式算法的基础上,结合在“高 本文的主要内容 论文的主要内容及论文组成 发,开发出适合自己的排课系统。 表编排系统往往依赖于 以“班”为单位,运用启发式函数来进行编排的。这 些课 。这些系统大都是模拟手工排课过程, 教学组织管理与课程调度系统等 系统,大连理工大学的智能 系统,清华大学的 年代初 世纪 。在国内,对课表问题的研究始于 个有希望得到成功的办法 想将问题分解,将是一 纯靠数学方法是行不通的,而利用运筹学中分层规划 的思 大规模课表编排问题单 学编程解决课表问题的巨大障碍。国外的研究表明, 解决 大,这已经成为应用数 杂,用数学方法进行问题描述时往往导致问题规模剧 烈增 。目前,解决课表问题的方法有:模拟手工排课 大学的 、加拿大 大学管理学院的 性的有印度的 年代以后,国外对课表问题的研究仍十分活跃。比较有代表 世纪 进入 基于启发式算法的高校排课系统的研究与设计 - 4 - 结论,对本文的工作进行总结。 并且对关键数据表及关键用例进行了详细设计。 结构和功能进行了系统描述, 第五章:排课系统的分析设计,对排课系统的 第四章:排课系统架构,介绍本文设计实现排课系统采用的软件架构。 此基础上构建高校排课模型。 课进行需求描述和分析,并在 第三章:排课系统的需求分析,对高校教务排 启发式排课算法。 个拟人策略提出改进的 边策略”、“前景探索策略”及“学习策略”,基于这 三 算法,并在此基础上提出“靠 第二章:排课系统算法策略,介绍传统启发式 课题的结构和关键词。 单的描述了论文的研究 出论文的主要内容、结构和重点,指出了关键的问题,简 简单的介绍了论文的背景,提 第一章:引言,论述了本文立题的学术意义, 各章内容如下: 基于启发式算法的高校排课系统的研究与设计 第 2 2.12.1.1全是随意的,没有利用已解决问题的任何特性 ,因此除了那些最简单的问题之 heuristic Search informed search 2.1.1.1状态空间表示法是用“状态”和“算符”来表示问题的一种方法。其中, “状态”用以描述问题求解过程中不同时刻的 状况:“算符”表示对状态的操2.1.1.2后继节点、子节点),然后检查目标状态是否 在其中出现。若出现,则搜索成- 5 - 可供操作的状态及“算符”时为止。 目标状态出现或不再有 功,找到了一个状态作为当前状态。重复上述过程,直到 状态(或称后继状态、 前状态,选择适用的“算符”对其进行操作,生成一组子 始状态(即初始节点)作为当 状态空间搜索的基本思想是:首先把问题的初 状态空间搜索 状态时,由初始状态到目标状态所用算符的序列就是问题的一个解。 一种状态。当到达目标 作,“算符”的每一次使用就使问题由一种状态变换为另 状态空间表示 这个给定的状态空间。 题就是如何有效地搜索 是完全确定的,然后决定了一个状态搜索空间,剩下的问 态,目标状态、动作都 题领域的信息常常可以用来简化搜索,我们假设,初始状 )。有关具体问 )或有信息搜索( 是启发式搜索( 种更有效率的搜索方法 外,一般都要占用很多时间或空间(或者两者均有)。一 这些节点的扩展次序完 索中找到一个解,所需要扩展的节点数目可能是很大的, 杂问题求解。在盲目搜 盲目性,效率低,耗费过多的计算空间与时间。不便于复 本身的特性,所以具有 略。由于搜索总是按照规定的路线进行,没有考虑到问题 息不能用来改进控制策 按规定的控制策略进行搜索,在搜索过程中获得的中间信 单的问题。盲目搜索是 搜索方法,或者叫做无信息搜索,一般适用于求解比 较简 优先搜索等,它们均属于盲目 搜索的方法有很多,比如宽度优先搜索、深度 一般搜索原理 启发式搜索理论 排课系统的算法策略 章? 基于启发式算法的高校排课系统的研究与设计 2.1.2[14] 。 2.1.2.1f x g x + h x g x So x h x x Sg x x h x p hs p p’ p’ p 2.22.2.1NP P! = NP [15] 。 [16],[17] 人 - 6 - 。它们一般是模拟 种称之为直接启发式算法 一张合法课表,常使用的是一 安排每门课程进而得到 一类是改进型算法。构造型算法一般是按照某种次序逐步 大类:一类是构造型算法,另 目前求解排课问题的启发式算法大致可分为两 发式算法 似最优解的算法,即启 题,往往利用问题的一些启发式知识来探求能快速求其近 用的需要,对于这类问 法能保证在多项式时间内得到最优解。因此。为了实际应 的假设下,找不到一个算 一难问题。即在 高校排课问题是典型的 算法的提出背景 基于启发式搜索的排课算法 的启发函数。 的最优估价可以被看作是用来解决问题 ,使得其最佳解决方案可以被更有效的求得。而对于解决 一个相对简单的问题 放松成 的方法是通过将问题 ,一种常用的得到启发式函数 对于问题 称为启发函数。 处于最优路径上的概率等。 节点的距离,也可以是节点 到目标 题的启发性信息,其形式要根据问题的特性确定。例如,它可以是节点 的最优路径的估计代价,它体现了问 到目标节点 是从节点 出的代价; 已经实际付 到节点 为从初始节点 ,其中 形式为: (评价函数),其一般 为启发性信息。用于估价节点重要性的函数称为估价函 数 解有关的控制性信息称 得最优解。像这样可用于指导搜索过程,且与具体问题求 较高的节点,以利于求 性信息,估计出节点的重要性,就能在搜索时选择重要性 用与问题求解有关的特 同就形成了不同的搜索策略。如果在确定节点时能充分利 要考察的节点,确定的方法不 在搜索过程中,关键的一步是如何确定下一个 启发性信息和估价函数概述 因而原则上只需要搜索问题的部分状态空间,效率高 。这种搜索针对性强, 最有希望的方向前进,加速问题的求解过程并找到最优解 发性信息,用以指导搜索沿着 启发式搜索是在搜索中加入了与问题相关的启 启发式搜索理论 基于启发式算法的高校排课系统的研究与设计 发式算法,简单、直接、快速,其启发式知识 往往是针对具体问题的特点提出 的,虽然通用性较差,但是如果启发式知识得 当,则往往能快速地得到较好的Exploring Learning 2.2.2UTTP1 、 2 、 3 或 44 [18][19]- 7 - 。一般包括以下三个层次: 的约束条件 现为排课方案满足一定 是为给定的每个课元合理地分配时空片簇。“合理地”体 簇。因此排课的任务即 午、下午或晚上且连续的若干个时空片的集合称作时空片 称作时空片。将课室相同,时间在同一个上 时间片。课室 间片和课室构成的序偶 时间称作时间片,由时 教师,周学时)称作课元。将一周内可供安排的每节上课 元组(课程,班级列表, 为了方便。将每次授课所包含的几个要素组成的 程等等。 节;同一教师可以讲授多门不同的课 次授课,每次授课的时间连堂 门课程可根据周学时多 学可包含多个自然班级;每个班级上课的课室不固定;一 具有如下特点:一门课程的教 根据我国高校的典型情况,约定高校排课问题 校排课系统的一个数学描述,将约束条件进行量化,确定了优化目标。 )的约束多样性和目标模糊性.本文首先给出了高 鉴于高校排课系统( 问题的数学描述 的搜索算法。进一步提高了课表的质量。 略来跳出“局部陷阱” 算法是在前者的基础上引入了拟人策 得的课表; 高于直接启发式算法所 程中同时也对课表进行了局部优化,所得课表的质 量明显 索算法,它在构造课表的过 算法从效果上相当于是一个局部搜 个算法: 这两类算法的特点。包含有两 本文给出的启发式算法吸收了构造型和改进型 在实用的系统中大都是采用直接启发式算法。 性,但是往往收敛慢。 解。而现代优化算法尽管具有通用性和理论上的全局最优 作。相比之下,直接启 算法有时需要在预先产生的若干个初始合法课表上进行工 现代优化算法,但这些 课表更加合理,如禁忌搜索、模拟退火算法、遗传算法等 课表上进行改进使得 合法 予“受限制最多”的含义不同。改进型算法则一般是在 程”,而差别仅在于赋 工排课的经验,基本策略都是“优先安排受限制最多的课 基于启发式算法的高校排课系统的研究与设计 1 ? ? ? ? ? ? 等 。 2 ? ? ? ? 3 C 是 TR TR 1 , 2 , „ , S W ? 01 ? i ? i s 1?设 t i ? C fi , t = W X +W X + „ + W X( 1 ) 1 l 2 2 s s fi , t i t X ? 0 , 11 ? j ? s j 在 t i j X 1 X 0 。 j j 2 设 t Et ? fi , t( 2 ) t ? c Et t - 8 - 的不满意度。 为可行解 并称 是可行解,定义评价函数(罚函数): 定义 ,否则 个约束条件,若违反, 的安排是否违反了第 中课元 表示 中的不满意度。其中. 在可行解 为课元 并称 是课元,定义函数 是可行解, 定义 。为了在数量上体现这些约束条件的满足情况,我们引入两个概念。 ,并对它们赋予相应的权重 特殊约束条件依次编号为 。将所有的优化约束条件和 即一张最满意的课表 束条件和特殊约束条件的可行解 .最优解为最大程度满足优化约 即一张课表 足了全部硬约束条件的解就是可行解 的时空片簇的方案,满 问题的解定义为给每个课元按照其周学时数分配互不相交 可导出所有时空片簇的集合。将 是所有时空片的集合,由 所有课元的集合, 如,住在校外的教师、老教师需要在上课的时间和地点方面酌情关照等等。设 提出的一些特殊的合理要求。比 )特殊约束条件。主要是指班级、教师个人 求;等等。 尽可能满足每个课元教学的合理要求.比如对多媒体课室的要 元交错安排; 尽可能将文理科课程的课元、主副课程的课 课元分配好的时间片和好的课室; 尽可能给重点课程的 程的多个课元的时间要间隔均匀.而课室则尽可能相同; 同一课 )优化约束条件。旨在使课程的安排尽可能合理、科学,例如: 比如,由于某种原因要求某些特定时间不能排课 其它必须满足的条件 一天; 属于同一门课程的不同课元不能安排在同 同一个时间片内最多只能有一门课; 每个教师在 每个自然班在同一个时间片内最多只能有一门必修课; 课元; 每个时空片最多只能分配给一个 和容量满足课元的要求; 如体育馆 课室类型 按课元周学时分配大小相当的时空片簇,且 )硬约束条件。主要包括: 基于启发式算法的高校排课系统的研究与设计 2[UTTP] min Et( 3 ) t 3 t W , W , „Ws 1 2W ? 01 ? i ? s i 条件.则可以人为地赋予该条件较大的权重, 使得产生的课表可以满足实际要3 Et t 。 2.2.3UTTP32.2.3.1 2.2.3.23 C 在 TR TRC sub sub - 9 - (它同时也表示了剩余时 中形成的部分课表 的课元子集 条件 即满足硬约束 在任一时刻,称由所有已被“合法”安排了时空片簇 定义 最佳分配策略 到小依次来给课元安排时空片簇。 按照课元的优先权由大 的时空片簇就少,所以应该优先安排。优先权策略就是, 越多,从而可供其选择的满意 一般地,课元的优先权值越大,课元的约束就 每个课元的优先权。 属性的线性组合来确定 数等。根据这些属性可以给课元赋以优先权,比如可采用 教师、所属课程包含的课元个 课元一般具有属性:类型、周学时、班级数、 优先权策略 略:优先权策略和最佳分配策略。 式来描述直接启发式算法。它们通常要采用如下两个策 课表。这里结合 空片簇,直到得到整张 课元的优先权次序来依次给每个课元安排其“理想”的时 束性赋予以优先权,然后按照 直接启发式算法,一般是首先根据各课元的约 传统的直接启发式算法 达到较小值的可行解 式.就是求取尽可能使 使用启发式算法来求解 求。 要优化标准侧重于某个 殊约束条件的权重较小。当然,人们在实施排课时,若需 的确定,一般来说,优化约束条件的权重较大.而特 对于权重 解。 。的最优解,简称为最优 即为相对于权重 式的可行解 满足 是可行解 描述: 式作为我们的目标函数。于是我们可以对高校排课问题作如下形式 的做法, 取 校的实情,我们参照许多文献 由于排课问题的模型没有定式,考虑到我国高 基于启发式算法的高校排课系统的研究与设计 4 TRC c ? C - C TRC sub sub sub c c 5TRC c ? C ? C FS sub sub c ts ? FS c 对 tsgc , ts , TRC W X + W X + „ +Ws Xs 4 sub l l 2 2 其中 W 1 ? j ? s 为评价函数 Et 中的权值, Xj ? 0 , 1 表示在部分 课表 j TRC ts c 后 c j sub X 1 X 0 。 j j TRC TRC gc,ts,TRC sub sub ? fc , TRC 。 min gc , ts , TRC 的 ts c 。 ts ? FS sub 2.2.4 procedure Heuristic input C TR output TRC sub begin TRC C FailSet Φsub subfor c1 to C do 1 TRC c FS sub - 10 - 的可行时空片簇集 中获取课元 .在课表 ‖算法中不能安排的课元集 Φ, ,其中 设初始格局为 确定每个课元的优先权值,并将课元按照其优先权值由大到小排序 :课表 ,时空片集 :课元集 根据上面的两个策略,对直接启发式算法描述如下. 算法描述 分配给课元 最佳分配策略就是将满足 ,则有 最后能到达一目标格局 显然,若从格局 ,否则 个约束条件,若不满足,则 的安排是否满足第 分配给 中若将 满意度为: 的不 ,定义课元 的可行时空片簇集。对于任意的 是该格局下课元 ?Φ 的安排。设 下,考虑课元 在某活格局 定义 的可行时空片簇。 的空闲时空片簇为课元 一个能合法安排下 中每 ,称 下,对于课元 在某活格局 定义 否则称为死格局。 非目标格局为活格局。 标格局(即可行解)。剩余课元中尚有课元可合法安 排的 时空片簇的格局称为目 空片集)为系统在此时刻的格局。所有课元均已被安 排了 基于启发式算法的高校排课系统的研究与设计 2 FS c FailSet 中 3 Fs min gc , ts , TRC 的 ts ? ts FS sub c TRC sub end for end .Heuristic Exploring Learning2.3Heuristic UTTP 2.3.1TRC c ? C - C P sub sub TRC p sub 2.1 图 2.15 p2 c 4 2 1-2 、 2-3 、 3-4 、 4-5 1 ? 2 和 4 ? 5 - 11 - 。这就是时空片簇的靠边策略。即,在某格局下,从部分课表中的所有最大空 闲 。我们仅考虑靠边的两个空闲时空片簇 时空片簇: 的空闲 个大小为 而言,实际上它对应 ,对于课元 。假定 其大小为 最大空闲时空片簇 所示。 如,某个最大空闲时空片簇如图 的空闲时空片簇都有可能是其可行时空片簇。例 中任意大小为 分课表 。在部 的安排,其周学时为 下,考虑课元 在某活格局 靠边策略 提出了如下三个新的排课策略。 算法的基础上针对 为了避免盲目搜索,提高所得解的质量,我们在 基于拟人策略的启发式算法 元的某种优先次序。 算法具有学习的能力,它能够学习到课 较大程度上消除这种敏感性,而 算法能在 课结果往往会因课元的优先次序不同而差别较大。下面给出的 次序很敏感。即,排 算法的结果对于课元优先 通过实验我们发现, 安排,给它们换一个较满意的可行时空片簇.直到当前课元能安排下为止。 整一个或者多个课元的 是,在遇到这种情况时算法就进行一定限度的回溯, 即调 况。一些文献中采用的办法就 当然,算法中可能会遇到某课元无法安排的情 ,并更新格局 给课元 分配 ,将满足 ?Φ .若 加入 Φ将 .若 基于启发式算法的高校排课系统的研究与设计 边策略一方面可以缩小搜索范围,另一方面可 以使得时空片的剩余空间更 好利2.3.2α TRC c ? C - C FS sub sub c ts ? FS TRC ? c ? ts sub TRC c ts α sub hc , ts , α TRC ? c ? ts C - C ? c sub sub hc , ts , α ;若最终到达的是一死格局,则 hc , ts , αW × |FailSet| , 其中 0 FailSet W 0 2.2 图 2.2 - 12 - 搜索过程 所示。 个数。其搜索过程如图 是比任何可行解的不满意度都大的一 是该死格局中未能安排的课元集。 ,该可行解的不满意度即为 可行解 中的课元进行排课。若最后能达到一目 标格局 出发,使用最佳分配策略依次对 从新格局 来度量每个新格局的前景: 局。用 的后继格 处后所得的新课表)均可能是格局 安排在 中将课元 (在 ,新格局 的可行时空片簇集.对于任意的 格局下课元 是该 ?Φ 的安排。设 下,考虑课元 在某活格局 前景探测策略 用,为后面课元的安排留下更多的机会。 簇.直观上看,采用靠 时空片簇的靠边子时空片簇中获取当前课元的可行时空片 基于启发式算法的高校排课系统的研究与设计 α min hc , ts , α 的 ts c 。 ? ts FS2.3.3TRC 1 式 fc , TRC 2.3 图 2.3 - 13 - 们得到两个基于拟人策略的排课算法,其描述如下。 。基于上面的策略,我 很自然地得到能使算法有较好结果的课元的某种优先次序 若干回合的学习就可以 课结果都对课元的优先权次序敏感。使用学习策略,通过 法及前景探测策略的排 也是一种拟人的策略。通过实验,我们发现直接启发式算 范围。这种策略实质上 的地方。因此,该策略能比前景探测策略具有更大的 搜索 极小跳到前途可能更好 时相当于到达了局部极小值点。学习策略就是如何从局部 用它到达一目标格局或死格局 前景探测策略可看作是一个局部搜索策略,使 学习策略模型 所示. 略进行下一轮排课,如图 然后再应用前景探测策 是最不满意的课元.对最不满意的课元增加其优先权值, 为其中未能安排的课元 元;若不能得到一个可行解,而是到达一个死格局,则认 ,然后挑选出最不满意的课 来计算每个课元在这张课表中的不满意度 ,则按照 略,若得到一个可行解 学习策略就是,根据前景探测策 学习策略 行解,它选择往更好的可行解方向继续搜索。其效果显然比最佳分配策略要好。 际上可能探测到许多可 略又可视作是一种局部搜索策略,因为在其搜索过程中实 步。从效果上看,该策 次从当前的格局走向下一个格局之前。总是要向前看若干 略,它模拟对弈者的经验,每 该策略是从搏弈中受到启发得来的一种拟人策 分配给课元 格局,即将满足 个新格局作为下一个 下,选择前景最佳的那 前景探测策略就是在当前格局 基于启发式算法的高校排课系统的研究与设计 2.3.4 Exploring procedure Exploring // input C TR // output TRC sub begin αTRC C Φ sub sub FailSet Φ // for c1 to C do 1 TRC C FS sub 2 FS C FailSet 中 3 FS min hc , ts , α 的 ts c 。 ? ts FS αTRC sub end for end . 2.3.5 Learning procedure Learning// input C TR TRIES output ETRC TRC sub sub begin for i1 to TRIES do 1 2 Exploring FailSet Φ 时 FailSet 时 TRC sub 3 ETRC TRC 2 sub sub TRC ETRC W × |FailSet| sub sub 0 4 ETRC TRC sub sub 5 c - 14 - .找出最不满意的课元 是目前最小值。则保存 .如果 是部分课表。则 来计算;若 是完整课表,按照式 :若 .计算评价函数 ?Φ 或部分课表 得完整课表 .调用算法 .将课元按照其优先权值由大到小排序 的课表 :具有最小 。迭代次数 ,时空片集 :课元集 基于学习策略的排课算法 算法 并更新格局 分配给课元 ?Φ,将满足 .若 加入 Φ,将 .若 的可行时空片簇集 中用靠边策略来获得课元 .在课表 算法中不能安排的课元集 。其中 设初始格局为 :课表 课元已按其优先权值由大到小排序 ,时空片集 :课元集 基于前景探测策略的排课算法 算法 基于启发式算法的高校排课系统的研究与设计 6 c c // end for end . 2.3.62-1Heuristic Exploring Learning 2 2 3 2 3 为 Onm 、 O n m 、 O n m ×TRIES On + m m n TRIES 是 Learning c Om , Om c 2 Om g Om C 2 2 Om Heuristic Onm c ts , hc , ts , α 2 果 ETRC Onm Exploring sub 3 Onm On Exploring 2 3 On m Learning O 2 3 n m ×TRIES On Om On+m On+m 。 Learning Exploring Exploring Heuristic 2-2Exploring Heuristic Learning Exploring - 15 - 算法所得解的质量。 算法所得解的质量不低于 算法所得解的质量; 算法所得解的质量不低于 定理 算法的搜索范围,故有如下结果: 算法的搜索范围又包含了 算法的搜索范围,而 含了 算法的搜索范围包 算法的解质量,不易从理论上做出定量分析。但由于 进行有针对性的搜索,故对于 我们的算法仅在问题的解空间的一个极小部 分 ,故共需存储空间 来存储时空片集,而其它数据的存储空间不会超过 来存储课元, 。在存储空间方面,三个算法的都需要空间 算法的时间复杂度为 。由此容易得到 算法的时间复杂度为 ,因此 格局的变迁次数不超过 。而算法运行过程中 时间为 算法中一个格局的变迁需要的 。因此 ,需要时间 最佳分配策略并最后计算所得结 时,要在余下的所有课元上应用 计算 的每个可行时空片簇 。对于 算法的计算时间为 。因此 应用最佳分配策略需要时间 ,从而对 的时间为 。计算 要时间 的所有可行时空片簇需 .因此获得 而判断一个时空片簇是否可行需要时间 的可行时空片簇时,时空片簇个数为 证明:在某格局下确定某课元 算法中的迭代次数。 是课元个数, 是课室个数。 。其中, 。空间复杂度均为 算法的时间复杂度分别 算法、 算法、 定理 关于算法的时间和空间复杂度.有如下结果: 算法分析 使用学习策略 的优先权值 否则,增加课元 的优先权值已足够大。则随机选择一个课元增加其优先权值; .若 基于启发式算法的高校排课系统的研究与设计 第 3 重要,学校要做好这项工作,关键要遵循科学 的排课原则,采取有效的管理办 3.1[20] 。 材,有一套具体的规章 制度 关于办公室下班关闭电源制度矿山事故隐患举报和奖励制度制度下载人事管理制度doc盘点制度下载 和办法,易于保证 教学秩序的稳定和一定的教学质 [21] 。 - 16 - 生的自主性大大增强, 班级为单位的学生管理体制,专业的界限也将被打破。学 学分制将淡化原有的以 在教学管理上,因为学分制是与选课紧密相联系的。实行 实施起来有其困难,主要体现 虽然学分制有很多优点,但是目前在普通高校 知识结构趋于多样化,也有利于学科之间的渗透及边缘学科的发展。 灵活性好,有利于学生 能够开设大量的选修课以满足不同学生的不同选择,因而 髓。学分制度要求高校和教师 保证选修课的应有数量和质量,是学分制的精 真正意义上的学分制 选课制,那么也就不是 要条件。如果只有学分制的叫法,而在教学组织中不实施 ,选课制为学分制的必 量。而学分制和选课制相伴而生,学分制以选课制为基础 课程又有统一的教学大纲、教 实行学年制的高校,有较统一的教学计划,各 在我们眼前的迫切任务。 务管理系统的研制是摆 管理教务工作,因此,基于数据集中管理的、学分制的教 理方法已经无法有效的 在学分制条件下,传统的基于单机或者手工模式的教务管 、学年学分制向学分制过渡。 随着教学改革的深入,很多高校正在从学年制 业的学位证书 生可以毕业,拿到该专 课程,一旦学生完成了某个教学计划规定的学分,则该学 专业课程和选修外专业 修课程学分和选修课程学分,其中选修课程又分为选修本 学分分成两个部分:必 学分制管理是这样的:学生的毕业资格根据学分来决 定, 明确的界定,我们这里所指的 由于对符合国情的学分制管理目前还没有一 个 教务管理系统的特点 法,实现课表编排现代化。 表编排管理工作也显得越来越 高等学校办学规模大,办学层次高,高校课程 排课系统需求描述 章? 基于启发式算法的高校排课系统的研究与设计 学生有了选择课程和选择教师的权利,原有的 全班一张课表变成了每人一 张课 3.2[22] 3.1[1] [2][3] [4] [5] - 17 - 自己的学习计划,进行选课。 学生在指定的时间内登录教务系统,根据自己的可选课程,制定下学期 程冲突。 。确保学生的选修课程不与必修课 程,即某个学生在下学期可以选择的课程 排课结束后,系统根据不同的专业、行政班级等信息生成学生可选课 根据教学任务为下个学期进行排课。 在每学期中间,系统根据教学计划生成下个学期的教学任务,教务人员 教务人员制定针对某个入学时间的教学计划。 息、专业信息等等。 教务管理人员进行基本的数据维护,比如课程信息、教师信息、教室信 如下: 。系统流程 此系统的管理之下 。学生从入学到毕业全程都在 工作流程如图 有师生服务的,系统的总体的 基于学分制的教务管理系统是开放的,面向所 教务系统的工作流程 选课为中心,涵盖整个教学流程的教务管理系统是实行学分制管理的重要手段。 据共享、集中管理,以 系统已经不能满足学分制管理的要求,一个基于网络、数 单机的学年制教务管理 管理方法和手段对整个教学过程进行管理。简单的、基于 硬件环境,还必须通过科学的 为了保证学分制的顺利实施,不但要有必要的 正常实施。 排,不然,学分制无法 室、实验实习场地、计算机房,图书馆等教学场所统筹安 效率低下。三是要对教 统必须用计算机进行管理,否则管理的工作量太大,并且 理系统以及学生管理系 为每个学生一张课表。二是学分制下的选课系统、学分管 原来每班一张课表,现 管理的模式。一是教学管理变面向班级为面对学生个体, 教学管理部门必须改变 能会坐在同一课堂上课。这将会加大学生管理的工作量。 、不同年级的学生有可 表,每个学生的学习进度和上课时间不尽相同,不同专业 基于启发式算法的高校排课系统的研究与设计 [6][7] [8][9] [10]图 3.1 3.33.3.1 - 18 - 的要素相互交织在起,给排课问题带来了复杂化,给工作带来了许多困难。 “活动”的和“固定” 涉及到“固定”的要素??课程和教室等场地或设备。这 课教师和开课对象学生,又要 编排课程表即要涉及到“活动”的要素??任 确立高校课程表编排原则 高校课表编排若干问题的思考 教务管理系统的工作流程 教学信息和数据汇总。 管理人员和教职员工根据不同的权限可以随时登录教务社区来查看各种 及是否能获得学位。 学生申请毕业时,教务人员通过毕业审查程序决定该学生是否能毕业以 考试结束后,任课教师可以登录教务系统录入所教授班级的学生成绩。 学生登录教务社区查询自己的考试情况。 考试前教务管理人员通过考试管理系统自动生成考试安排和考场安排, 教务管理人员对学生选课结果进行筛选,公布结果,进行补选和退选。 基于启发式算法的高校排课系统的研究与设计 [1]等信息对象,算法目标是为满足需求(如班级 、课程等)进行合理资源(如 教般采用“穿插使用”的办法,这些学校许多课 程如公共课是跨系、跨专业进行 [2] a b- 19 - 既要明确理论教学的任务,又要规范技能训练的标准; 要有超前意