学位论文 > 优秀研究生学位论文题录展示

基于遗传算法的学分制下多校区排课系统的研究与实现

作　者: 杨小兵
导　师: 黄青松
学　校: 昆明理工大学
专　业: 计算机软件与理论
关键词: 遗传算法排课 NP完全问题约束条件
分类号: TP18
类　型: 硕士论文
年　份: 2010年
下　载: 94次
引　用: 0次
阅　读: 论文下载

内容摘要

排课是学校教学管理中十分重要且又相当复杂的管理工作之一,随着高等教育事业的发展,高校在校学生人数的不断增加,在教室资源、教师资源等教学资源有限的前提下编排课表显得更加繁重、复杂,同时课程表的编排也更成为教学管理工作的关键,在一定程度和深度上影响着学生培养与教学质量的提高。手工排课不仅占用大量的人力、花费太多的时间,而且排出的课表往往不尽人意。因此,如何利用计算机快速、高效、准确地编排出合理并且满意度较高的课表,是一项值得研究的工作。在实际研究中,由于排课受到各种条件的制约,开发出符合个体要求的排课系统是一件难事。排课问题是一个约束性强的、非线性的、多目标优化的NP—完全问题(NP-COMPLETE),而且还是一个组合优化问题,已经被证明属于NP难题。而遗传算法(genetic algorithms,简称GA)借鉴生物界自然选择和遗传机制发展起来的高度并行、自适应的随机搜索算法,使用群体搜索技术,尤其适用于处理传统搜索方法难以解决的复杂的非线性的问题,是一种非常有效的解决NP完全的组合问题的方法。由于本人在昆明理工大学教务处负责排课工作,在几年的工作中已经体会到排课的复杂性,要想在短期内排出一张令所有教师和同学都满意的课表难度很大。鉴于上述原因,根据昆明理工大学教务信息化建设的需求,结合本校多校区、规模大、各类教学资源相对紧缺的具体实际情况,为了能最大地提高排课效率和准确性,针对排课问题设计了一个适合我校的排课系统算法。本文将对遗传算法进行了初步研究,并针对我校多校区的排课问题,根据相关遗传算法和多目标优化理论的基础之上,提出了基于遗传算法的课表编排算法。该算法根据课表编排的三种约束条件：硬性约束、中性约束和软性约束,确定了课表编排过程中的一些关键因素,并给出了排课过程中产生冲突的解决方案,这种课表编排方案的随机生成和优化算法,能够较大程度地反映实际排课情况和尽量达到多个目标最优,实现一个适合我校实际情况的排课系统。

全文目录

摘要  3-4
Abstract  4-9
第一章绪言  9-14
  1.1 研究背景  9
  1.2 研究意义及目标  9-11
  1.3 排课问题国内外历史及现状  11-13
  1.4 论文的组织结构  13
  1.5 本章小结  13-14
第二章相关技术  14-26
  2.1 遗传算法简介  14-17
    2.1.1 基本遗传算法的构成要素  14-15
    2.1.2 基本遗传算法的形式化定义  15
    2.1.3 基本遗传算法描述  15-16
    2.1.4 基本遗传算法的基本流程  16-17
  2.2 遗传算法的基本操作  17-19
  2.3 基本遗传算法的运算过程与构造过程  19-21
    2.3.1 遗传算法的运算过程示意图  19-20
    2.3.2 遗传算法的应用步骤  20
    2.3.3 遗传算法的主要构造过程示意图  20-21
  2.4 遗传算法的特点  21-22
  2.5 XML技术  22-23
  2.6 DHTML技术  23
  2.7 模式定理  23-25
  2.8 本章小结  25-26
第三章基于遗传算法排课系统需求分析  26-41
  3.1 排课问题概述  26-27
  3.2 排课问题的要素  27-30
    3.2.1 排课问题所涉及因素  27-29
    3.2.2 课程、教师的关联问题  29-30
  3.3 排课过程的约束条件和排课规则  30-32
    3.3.1 排课的约束条件  30-31
    3.3.2 排课规则  31-32
  3.4 排课问题是NP—完全类问题  32-33
  3.5 昆明理工大学排课模型  33-40
    3.5.1 多阶段排课  33-34
    3.5.2 一级排课与二级排课  34-35
    3.5.3 排课冲突检测模型  35-37
    3.5.4 排课数据  37-40
  3.6 本章小结  40-41
第四章基于遗传算法的排课系统设计  41-61
  4.1 系统设计目标和技术架构  41-42
    4.1.1 系统设计目标  41-42
    4.1.2 系统技术架构  42
  4.2 系统总体功能结构  42-44
  4.3 课表编排流程图及框架  44-45
    4.3.1 课表编排流程图  44-45
    4.3.2 排课遗传算法流程图  45
  4.4 排课问题的数学描述  45-49
    4.4.1 排课问题的优化求解模型  45-46
    4.4.2 排课问题的约束满足模型  46-49
  4.5 排课安排的难度量化  49-51
    4.5.1 班级课表安排难度量化及影响因素  49-51
    4.5.2 课程安排难排度量化及影响因素  51
  4.6 遗传算法与排课的对应关系  51-52
  4.7 排课遗传算法算法设计及课表编排  52-60
    4.7.1 基因编码及染色体表示  52-54
    4.7.2 初始种群  54-55
    4.7.3 构造适应度函数  55-58
    4.7.4 选择算子  58-59
    4.7.5 交叉算子  59
    4.7.6 变异算子  59-60
  4.8 本章小结  60-61
第五章基于遗传算法的排课系统实现  61-75
  5.1 排课参数管理  61-63
    5.1.1 自动排课权重设置  61
    5.1.2 排课限制规则设置  61-62
    5.1.3 时间节次参数设置  62-63
  5.2 排课资源管理  63-64
    5.2.1 屏蔽资源设置  63
    5.2.2 时间资源管理  63-64
  5.3 排课数据管理  64-66
    5.3.1 排课任务优先级计算  64-65
    5.3.2 排课批次管理  65-66
  5.4 智能排课  66-68
    5.4.1 自动排课参数维护  66
    5.4.2 数据预处理  66-67
    5.4.3 自动排课  67-68
  5.5 手动调课  68-69
  5.6 排课结果分析及课表输出  69-71
    5.6.1 教室学时分析  69
    5.6.2 教室学时分析  69-70
    5.6.3 班级上课学时分析  70-71
    5.6.4 排课结果分析  71
  5.7 统计报表  71-74
    5.7.1 教室课表输出  71-72
    5.7.2 教师课表输出  72-73
    5.7.3 班级课表输出  73
    5.7.4 教室使用情况统计  73-74
  5.8 本章小结  74-75
第六章总结与展望  75-77
  6.1 研究工作总结  75
  6.2 展望  75-77
致谢  77-78
参考文献  78-81
附录A:攻读学位期间发表的论文情况  81-82
附录B:攻读学位期间参与完成的科研成果  82

基于遗传算法的学分制下多校区排课系统的研究与实现

内容摘要

全文目录

相似论文