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

车间混合作业调度问题计算复杂性及算法收敛效率研究

作　者: 郭子庆
导　师: 胡燕海
学　校: 宁波大学
专　业: 机械制造及自动化
关键词: 混合作业调度问题计算复杂性遗传算法算法收敛性
分类号: TH186
类　型: 硕士论文
年　份: 2010年
下　载: 52次
引　用: 0次
阅　读: 论文下载

内容摘要

本文在国内外相关研究的基础上,针对车间混合作业调度(MSP)问题进行了相关研究,涉及到模型建立、计算复杂性分析、算法实现、算法性能分析及验证等多方面的问题。首先,由于MSP问题规模庞大、系统复杂,为了表达MSP问题内部的多层阶结构网络关系,本文利用网络理论对MSP问题建立了多级赋权图模型,对其进行了清晰的描述。进而,对制造系统MSP问题的计算复杂性进行了分析,本文对其中包含的各种作业方式的计算复杂性分别进行了研究,并利用复杂性理论中归约和转换的思想,引入背包问题着重研究了其中两种作业方式的计算复杂性,最后表明MSP问题属于NP-hard问题,计算复杂度为指数级或阶乘级,不可能找到可以精确求得最优解的多项式时间算法。然后,研究了遗传算法在解决MSP问题中的应用过程,并对遗传算法的收敛性能进行了讨论分析。本文提出了一种十进制整数和实数相结合的编码方案,并针对这种编码方式实施了具体的遗传操作,使得交叉操作不失继承性,变异操作能够实现种群的多样性;利用马尔科夫链(Markov)理论相关知识证明了所设计遗传算法以概率1收敛到全局最优,并对算法的收敛速度进行了分析,指出各参数取值不同时对算法收敛速度产生的影响。最后,利用Matlab 7.0进行程序实现,通过与启发式算法结果的比较验证了该算法设计的可行性和有效性,并且验证了算法参数对收敛速度的影响结果,表明研究对算法收敛速度的分析是正确的。

全文目录

摘要  4-5
Abstract  5-9
1 绪论  9-16
  1.1 论文研究的背景、目的和意义  9-10
  1.2 国内外研究现状  10-14
    1.2.1 作业调度类型及建模方法  10-11
    1.2.2 优化算法  11-13
    1.2.3 算法收敛性能  13-14
  1.3 论文的主要研究内容及结构  14-16
    1.3.1 主要研究内容  14
    1.3.2 论文结构  14-16
2 基本车间作业调度问题介绍及MSP 模型建立  16-24
  2.1 生产调度简介及其特点  16-17
  2.2 生产调度的主要优化指标  17-18
  2.3 离散型制造系统的生产调度问题分析  18-22
  2.4 车间混合作业调度系统建模  22-23
  2.5 本章小结  23-24
3 车间混合作业调度问题计算复杂性分析  24-35
  3.1 调度问题计算复杂性简介  24-26
  3.2 混合作业调度问题计算复杂性分析  26-34
    3.2.1 HFSP 问题的计算复杂性  27-30
    3.2.2 JSP 和HFSP 组合调度问题的计算复杂性  30-33
    3.2.3 其他基本作业方式组合调度问题的计算复杂性  33-34
  3.3 本章小结  34-35
4 遗传算法应用及收敛性分析  35-60
  4.1 遗传算法基本知识  35-42
    4.1.1 标准遗传算法基本流程  36
    4.1.2 遗传算法参数与操作的设计  36-42
  4.2 遗传算法在混合作业调度问题中的应用  42-47
    4.2.1 编码  43-45
    4.2.2 选择操作  45
    4.2.3 交叉操作  45-46
    4.2.4 变异操作  46-47
    4.2.5 适配值函数  47
  4.3 算法收敛性和收敛速度研究  47-59
    4.3.1 遗传算子分析  48-50
    4.3.2 算法收敛性分析  50-54
    4.3.3 算法收敛速度估计  54-59
  4.4 本章小结  59-60
5 算法效率及算例研究  60-67
  5.1 构造规则  60-61
  5.2 实例说明  61-62
  5.3 算例结果对比  62-66
  5.4 本章小结  66-67
6 总结与展望  67-69
  6.1 总结  67
  6.2 展望  67-69
参考文献  69-73
在学研究成果  73-74
致谢  74

车间混合作业调度问题计算复杂性及算法收敛效率研究

内容摘要

全文目录

相似论文