基于整数规划的混沌遗传排课算法研究

论文摘要

排课是高校教学管理工作中的一项十分繁重且相当复杂的工作。随着各高校的不断扩招,教室和教师资源日益紧张。在这种情况下,利用计算机自动排课,生成结构合理、满足各方需求的课表,对保障高校教学管理工作的正常运行,具有十分重要的意义。排课问题是典型的组合优化和不确定调度问题,已经被证明是NP完全问题。国内外研究人员提出了众多的排课模型以及排课算法。这其中的整数规划方法,由于所建立的模型通用,受到研究人员的重视。然而,其计算复杂度过高,因此逐渐淡出了人们的视野。近年来,随着计算机硬件和软件的飞速发展,整数规划方法又重新受到人们的重视。本人结合在教务处工作的经验,对排课问题所需考虑的各个方面进行了详细分析。在此基础上,以本校教务管理中的排课问题为实例,建立了基于整数规划的数学模型。在分析了分支定界法、割平面法等求解整数规划问题的常用算法后,本文使用一种混沌遗传算法求解该问题。最后,本文介绍了排课系统的数据库结构设计以及排课算法中各步骤的具体实现方法,并以学校的排课历史数据,对排课系统进行了测试。经过测试,排课系统的计算结果以及计算时间较为理想。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 排课问题的背景
• 1.2 排课问题的研究历史及现状
• 1.3 整数规划方法概述
• 1.4 本文的研究目的与结构安排
• 第二章 基于整数规划的排课模型
• 2.1 排课问题详细分析
• 2.1.1 排课问题的业务流程
• 2.1.2 排课问题的数据流程
• 2.1.3 排课问题所涉及的对象
• 2.1.4 排课问题的约束条件
• 2.1.5 排课结果的衡量标准
• 2.2 排课模型的建立
• 2.2.1 参数集合
• 2.2.2 变量
• 2.2.3 约束条件
• 2.2.4 目标方程
• 2.3 求解整数规划问题的常用方法
• 2.3.1 分支定界法
• 2.3.2 割平面法
• 2.3.3 匈牙利法
• 第三章 求解整数规划的混沌遗传算法
• 3.1 遗传算法
• 3.1.1 遗传算法发展历史
• 3.1.2 遗传算法的基本操作
• 3.1.3 遗传算法的实现步骤
• 3.1.4 遗传算法的特点
• 3.2 混沌遗传算法
• 3.2.1 混沌及其特性
• 3.2.2 混沌遗传算法的基本操作
• 3.2.3 混沌遗传算法的实现步骤
• 3.3 求解整数规划问题
• 3.3.1 染色体的编码方式
• 3.3.2 约束条件的作用
• 3.3.3 目标方程的作用
• 第四章 排课算法的设计与实现
• 4.1 算法设计
• 4.1.1 开发工具
• 4.1.2 数据库设计
• 4.2 算法实现
• 4.2.1 主函数
• 4.2.2 数据初始化
• 4.2.3 构造染色体
• 4.2.4 混沌交叉
• 4.2.5 混沌变异
• 4.2.6 计算适应度和选择
• 4.2.7 生成课表
• 4.3 算法分析
• 第五章 总结与展望
• 5.1 总结
• 5.2 展望
• 参考文献
• 致谢
• 研究成果及发表的学术论文
• 作者和导师简介
• 北京化工大学硕士研究生学位论文答辩委员会决议书