基于改进遗传算法离散制造企业车间调度优化研究

论文摘要

众所周知,作为MES的重要组成部分,车间调度问题是实现制造系统运筹技术、管理技术与优化技术发展的核心之一。有效实用的计划调度方法与优化技术的研究和应用,已成为先进制造技术实践的基础和关键。现代产品市场的激烈竞争和千变万化对制造车间的生产计划调度的快速反应能力和精确性提出了更高的要求。作业车间调度问题（Job-shop）是离散制造企业中共同存在的问题,它是实际生产调度问题的高度简化。同时它又是一个NP完备问题,迄今为止,经过国内外学者几十年的研究,已经取得很多成果,但是要彻底解决这一难题,还需作大量工作。本文以遗传算法为线索,以离散制造企业中Job-shop调度问题为出发点,阐述了遗传算法（Genetic Algorithms）。针对Job-shop调度问题及其相关问题,建立问题模型,探索和改进更适合于离散制造企业车间调度的遗传算法。具体来说,本文主要就以下几个方面进行了研究：1、分析了离散制造企业生产车间Job-shop调度问题特点和意义,研究求解车间作业调度问题的主要历程及其方法,探讨了Job-shop调度问题的可计算性和计算复杂度。2、对二进制编码遗传算法运用模式定理从选择操作算子、交叉操作算子和变异操作算子三个方面单独作用时的遗传机制进行了深入的分析和论证；通过积木块假设、随机过程理论和马尔科夫链理论从多个层面论证了遗传算法的全局收敛性。3、针对Job-shop调度问题,从多方面比较分析9种编码方案,结合基于工序的编码方案,提出了求解车间调度遗传算法,并对标准数据进行了参数测试,获得较好的参数数目。这种遗传操作设计、编码方案、参数设计使得遗传操作大大简化,遗传算法搜索效率大大提高。使用标准实例对算法的有效性,收敛效果进行了验证。4、分析了遗传算法收敛中存在的早熟收敛问题,本文提出了一个概念清楚、灵敏度高评价种群早熟收敛的指标。结合自适应调整遗传算法控制参数Pc,Pm的思想,提出一种改进的自适应遗传算法。做了两方面改进,一是使用新的评价早熟收敛指标进行划分进化阶段,构造阶段性运算；二是提出更适用的自适应算子Pc,Pm。通过理论分析和标准数据测试,该方法不仅能及时反映群体在进化过程的早熟收敛现象,而且增强全局收敛性。5、通过研究并设计Job-shop多机并行调度系统,和经典Job-shop比较,得出比原来最优解更小解,即更短时间的调度安排。从两个角度拓展新算法性能,一是研究对象拓展,二是新算法与其他调度规则结合能力。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 引言
• 1.1 离散制造企业车间调度问题的提出
• 1.1.1 离散制造企业的定义
• 1.1.2 离散制造业的特点
• 1.1.3 离散制造企业生产车间调度优化的意义
• 1.2 车间调度问题的分类
• 1.3 Job-shop问题的描述
• 1.3.1 Job-shop问题定义
• 1.3.2 Job-shop问题的数学表达及其目标函数
• 1.3.3 约束假设
• 1.3.4 Job-shop调度问题的计算复杂度
• 1.4 Job-shop调度问题的发展现状
• 1.4.1 运筹学方法
• 1.4.2 基于规则的方法
• 1.4.3 系统仿真的方法
• 1.4.4 基于DEDS的解析模型方法
• 1.4.5 基于排序的方法
• 1.4.6 基于智能的调度方法
• 1.5 本论文研究的主要内容
• 第二章 遗传算法的理论
• 2.1 遗传算法简介
• 2.1.1 遗传算法的基本思想
• 2.1.2 遗传算法的描述
• 2.1.3 遗传算法的特点
• 2.2 遗传算法的理论基础
• 2.2.1 模式定理
• 2.2.2 隐含并行性
• 2.2.3 积木块假设
• 2.3 遗传算法的收敛性
• 2.4 遗传算法的关键问题
• 2.5 本章小结
• 第三章 遗传算法求解Job-shop调度设计
• 3.1 编码与解码
• 3.1.1 编码原理
• 3.1.2 车间调度编码方式
• 3.1.3 编码性能分析
• 3.1.4 基于工序的表达法
• 3.1.5 解码
• 3.2 适应函数
• 3.2.1 适应函数定义
• 3.2.2 尺度变换
• 3.3 初始种群的产生
• 3.4 遗传操作设计
• 3.4.1 选择设计
• 3.4.2 交叉设计
• 3.4.3 变异设计
• 3.5 终止准则
• 3.6 控制参数
• 3.6.1 控制参数分析
• 3.6.2 控制参数试验
• 3.6.3 数据分析
• 3.7 仿真比较
• 3.7.1 均匀种群策略与随机种群收敛比较
• 3.7.2 采取和不采取最优保存策略收敛比较
• 3.8 本章总结
• 第四章 改进自适应遗传算法设计
• 4.1 遗传算法早熟收敛现象
• 4.1.1 遗传算法早熟收敛原因
• 4.1.2 欺骗问题
• 4.1.3 早熟收敛防止策略
• 4.2 自适应遗传算法
• 4.2.1 自适应遗传算法的思想
• 4.2.2 自适应遗传算法的步骤
• 4.3 改进自适应遗传算法
• 4.3.1 遗传算法早熟分析新指标
• 4.3.2 改进自适应遗传算子
• 4.3.3 解决早熟收敛的设计
• 4.3.4 改进自适应遗传算法的流程
• 4.4 仿真与分析
• 4.4.1 仿真结果
• 4.4.2 性能分析
• 4.5 本章小结
• 第五章 Job-shop多机并行调度的设计
• 5.1 Job-shop多机并行问题的模型
• 5.1.1 Job-shop多机并行的表述
• 5.1.2 Job-shop多机并行模型的复杂度
• 5.1.3 Job-shop多机并行问题数学模型
• 5.2 Job-shop多机并行问题的分析
• 5.2.1 Job-shop多机并行问题的关键
• 5.2.2 Job-shop多机并行的遗传算法分析
• 5.3 资源选择规则
• 5.4 基于RSR Job-shop多机并行调度设计
• 5.5 Job-shop多机与经典Job-shop比较
• 5.5.1 仿真比较
• 5.5.2 数据分析
• 5.6 本章小结
• 第六章 结论与展望
• 6.1 结论
• 6.2 展望
• 参考文献
• 致谢
• 附录A
• 附录B