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

基于改进遗传算法的车间调度问题的研究

作　者: 彭雄凤
导　师: 刘美红
学　校: 昆明理工大学
专　业: 机械设计及理论
关键词: 车间调度遗传算法交叉算子邻域反转变异算子自适应
分类号: TP18
类　型: 硕士论文
年　份: 2009年
下　载: 100次
引　用: 0次
阅　读: 论文下载

内容摘要

随着科学技术的发展,现代生产规模越来越大,复杂性越来越高,市场竞争也越来越激烈,这就对企业的管理提出了更高的要求。车间调度是企业管理的核心,有效的调度技术不仅能对生产运行状况进行干预和调整,而且能合理化资源配置提高生产效益,因此,车间调度问题的研究和应用一直是学术界和企业界关注的热点。但是,车间调度问题通常是多约束、多目标、随机不确定的组合优化问题,已被证明是求解极为复杂的NP-难问题,因而优质高效的调度算法是研究车间调度问题的关键技术。遗传算法是模拟生物在自然界的遗传和进化过程的概率搜索算法,因其思想简单、隐含并行性及表现出来的鲁棒性和通用性等特点,而被广泛应用于车间调度问题的优化,是目前求解效果最好的调度算法之一,但它也存在遗传操作设计复杂、收敛速度慢等缺点。本文在研究最复杂的车间调度问题——作业车间调度问题的数学模型的基础上,从遗传操作设计和自适应参数两方面进行若干改进,以弥补遗传算法的上述缺点：首先,在遗传操作的设计上,本文深入遗传算法的基本理论,讨论了针对车间调度问题一般遗传算法的各种实现技术,在此基础上设计了一套合理的遗传操作,并提出了保存某些工序顺序的交叉算子和邻域反转变异算子。新的交叉算子能保存父代染色体的某些优良基因片段,使得遗传搜索的指导性和寻优能力更强；而邻域反转变异算子是在反转变异的基础上增加对变异染色体的邻域搜索,使变异操作的搜索区域增大从而降低变异后染色体所对应的目标函数值,加快群体进化过程。其次,自适应性是遗传算法的重要特性,本文研究了个体层次下交叉概率和变异概率的自适应性,并在线性自适应遗传算法的基础上提出两种改进的非线性自适应遗传算法。这两种改进的算法分别将双曲余弦函数chx和双曲正切函数thx应用到自适应遗传算法中而被分别命名为Ch-自适应和Th-自适应,它们能实现交叉概率和变异概率随着个体适应度值的变化而进行非线性自适应调整,从而改善传统线性自适应遗传算法收敛慢的缺点、提高遗传算法的性能。改进的Ch-自适应和Th-自适应被应用于车间调度问题的求解,文章通过几个经典的Benchmark实例验证了改进算法的有效性。最后,本文以改进遗传算法为核心算法,在Visual Studio.NET 2005上设计了作业车间调度问题的测试平台,并采用VB.NET语言编写了遗传算法的实现程序。该测试系统能实现调度数据的存取、遗传算法的运行和调度结果的分析等功能,为以后算法的扩展和相关问题的研究提供一个初步的通用的平台。

全文目录

摘要  3-5
Abstract  5-10
第1章绪论  10-18
  1.1 课题背景及研究意义  10
  1.2 车间调度问题的国内外发展概述  10-15
    1.2.1 车间调度问题的研究概述  10-11
    1.2.2 车间调度问题的算法研究  11-14
    1.2.3 车间调度研究存在的问题及发展趋势  14-15
  1.3 遗传算法的发展概述  15-17
    1.3.1 遗传算法的理论发展  15
    1.3.2 遗传算法研究存在的问题及发展趋势  15-16
    1.3.3 遗传算法在车间调度问题的研究及改进  16-17
  1.4 论文研究的主要内容  17-18
第2章车间调度问题和遗传算法  18-32
  2.1 车间调度问题  18-21
    2.1.1 车间调度问题的概念  18
    2.1.2 车间调度问题的影响因素及性能指标  18
    2.1.3 车间调度问题的分类  18-19
    2.1.4 车间调度问题的特点  19
    2.1.5 经典作业车间调度问题的数学描述  19-21
    2.1.6 经典作业车间调度实例  21
  2.2 遗传算法  21-29
    2.2.1 遗传算法的生物学基础  21
    2.2.2 遗传算法的基本要素  21-27
    2.2.3 基本遗传算法的操作流程  27-28
    2.2.4 基本遗传算法的收敛性及最优保存策略  28-29
    2.2.5 遗传算法的应用  29
  2.3 本章小结  29-32
第3章一般遗传算法求解车间调度问题  32-42
  3.1 染色体编码  32
  3.2 基于工序的编码及其解码  32-34
    3.2.1 基于工序的编码  32-33
    3.2.2 基于工序编码的解码  33-34
  3.3 种群初始化方法  34-35
  3.4 适应度函数  35
  3.5 遗传算子  35-40
    3.5.1 选择算子  35-36
    3.5.2 交叉算子  36-38
    3.5.3 变异算子  38-40
  3.6 本章小结  40-42
第4章改进的自适应遗传算法  42-52
  4.1 自适应遗传算法的基本思想  42-43
  4.2 线性自适应遗传算法  43-44
  4.3 改进的自适应遗传算法  44-46
  4.4 自适应遗传算法求解作业车间调度问题  46-47
  4.5 实例验证  47-50
  4.6 本章小结  50-52
第5章算法测试系统开发  52-62
  5.1 系统简介  52
  5.2 系统开发工具及整体结构  52-54
  5.3 窗体界面  54-56
    5.3.1 调度信息  54-55
    5.3.2 算法选择  55
    5.3.3 结果分析  55-56
  5.4 程序设计  56-60
    5.4.1 数据变量设计  56-58
    5.4.2 通用过程/函数设计  58-60
  5.5 本章小结  60-62
第6章总结与展望  62-64
  6.1 总结  62-63
  6.2 展望  63-64
致谢  64-66
参考文献  66-70
附录A  70-72
附录B  72-77

基于改进遗传算法的车间调度问题的研究

内容摘要

全文目录

相似论文