基于OCTPN和混合遗传算法的JSP多目标优化调度

论文摘要

本文以面向对象着色赋时Petri网和混合遗传算法为工具,对具有多工艺加工路径的生产车间调度问题进行了研究。本文的研究结果和内容可概括为以下的几个主要方面：将Petri网的“着色”这一抽象机制与面向对象的类、继承等概念相融合,提出一种面向对象的着色赋时Petri网OCTPN （Object-oriented Colored Timed Petri Net）.以OCTPN为建模工具分别研究了单资源、双资源和多资源作业车间调度优化问题。OCTPN模型基于“面向对象”而不是基于“面向过程”,把描述系统本质和能力部分抽象为不同的对象,而把描述系统动态行为的进程抽象为对象的实例,并赋予不同的颜色,较大地改善了制造系统调度模型规模庞大和可重用性差的问题。将一种Pareto排序策略嵌入到Pareto竞争方法中,提出了一种新的解决多目标优化调度的混合遗传算法。该方法在执行选择操作时,使用小生境技术来选取进入下一代的个体,使得搜索尽可能在整个解空间进行,避免算法收敛到局部最优。采用多种交叉方法和变异方法提高了算法的收敛速度。为了避免进化过程中最优解的遗失,采用Pareto解集过滤器保存进化过程中出现的最优解。通过仿真实验证明了算法的正确性和优越性。在该算法的基础上研究了双资源作业车间的双目标、多目标调度问题。在双资源双目标调度问题中,首先研究了生产周期和生产费用的双目标调度优化问题,并对工人/机床的比率和工人任务量的分配对该种车间的调度结果产生的影响进行了研究。在双资源双目标静态调度问题的基础上,研究了动态调度问题；对机床故障、工人离岗、订单取消等基于时间和任务进行分类,决定是否执行再调度;针对不同的情况进行不同的处理,选用合理有效的调度策略,最大限度地维持作业车间的生产能力。在双资源多目标调度问题中,从企业不同部门的利益出发,兼顾各个部门的期望目标,实现了对生产周期、生产费用、机床最大负载、机床总负载和客户满意度等多个目标进行优化,最后利用层次分析方法从得到的最优解集中选出符合决策者偏好的解作为调度的最优解。最后,用Delphi和Flexsim软件联合开发了实用的生产车间调度软件。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 车间调度问题概述
• 1.2.1 车间调度问题的含义与分类
• 1.2.2 车间调度问题的特点及评价指标
• 1.3 车间调度问题的研究现状与发展趋势
• 1.3.1 车间调度问题的研究现状
• 1.3.2 车间调度研究存在问题及发展趋势
• 1.4 遗传算法和Petri网在车间调度中的应用
• 1.4.1 遗传算法在车间调度中的应用
• 1.4.2 Petri网在车间调度中的应用
• 1.5 本文的研究意义和主要内容
• 1.5.1 本文的研究意义
• 1.5.2 本文的主要内容
• 第二章 Petri网基本理论
• 2.1 引言
• 2.2 Petri网的定义及图形表示
• 2.3 Petri网的主要行为特征
• 2.4 不变量分析
• 2.5 Petri网模型的变形及扩充
• 2.6 小结
• 第三章 面向对象着色赋时Petri网模型
• 3.1 引言
• 3.2 面向对象方法学的基本理论
• 3.3 面向对象着色赋时Petri网
• 3.3.1 对象子网
• 3.3.2 OCTPN建模步骤
• 3.3.3 OCTPN建模实例
• 3.4 小结
• 第四章 多目标优化的混合遗传算法研究
• 4.1 多目标优化问题
• 4.1.1 多目标优化的基本概念
• 4.1.2 问题的结构和特性
• 4.2 遗传算法
• 4.2.1 遗传算法的基本概念
• 4.2.2 遗传算法的基本流程
• 4.2.3 遗传算法关键参数和操作的设计
• 4.3 遗传多目标优化
• 4.3.1 遗传搜索的特征
• 4.3.2 适应值分配机制
• 4.3.3 适应值共享和种群多样性
• 4.3.4 Pareto解的概念
• 4.4 混合遗传算法的设计
• 4.4.1 编码设计
• 4.4.2 活动化解码方法
• 4.4.3 排序策略
• 4.4.4 选择操作和小生境技术
• 4.4.5 交叉操作设计
• 4.4.6 变异操作设计
• 4.4.7 Pareto解集过滤器的设计
• 4.4.8 算法终止条件的设计
• 4.5 算法验证
• 4.5.1 调度模型
• 4.5.2 Petri网模型
• 4.5.3 调度结果与分析
• 4.6 小结
• 第五章 双资源作业车间双目标调度优化
• 5.1 引言
• 5.2 双资源作业车间调度的数学模型
• 5.3 生产周期-生产费用双目标调度优化
• 5.3.1 生产费用的计算公式
• 5.3.2 仿真及结果分析
• 5.3.3 工人与机床设备比率对调度的影响
• 5.3.4 工人任务分派对调度的影响
• 5.4 双资源双目标动态调度
• 5.4.1 机器故障
• 5.4.2 工人离岗
• 5.4.3 订单取消
• 5.4.4 紧急工件
• 5.5 小结
• 第六章 双资源作业车间多目标调度优化
• 6.1 引言
• 6.2 问题描述
• 6.3 多目标决策理论简介
• 6.3.1 劣解、非劣解和最优解
• 6.3.2 选好解
• 6.4 层次分析方法
• 6.5 多目标仿真实验与分析
• 6.6 与其他学者的研究结果比较
• 6.7 小结
• 第七章 调度软件的设计与实现
• 7.1 引言
• 7.2 系统主要设计结构
• 7.3 系统的特点及其主要技术要点
• 7.4 车间调度软件的使用方法
• 7.4.1 调度数据输入、浏览、修改和删除
• 7.4.2 调度任务的设置和调度计算
• 7.4.3 调度结果的再处理、信息整合
• 7.4.4 调度结果的输出
• 7.4.5 计算偏好解
• 7.4.6 Flexsim上的三维动态仿真
• 7.5 小结
• 第八章 总结与展望
• 8.1 结论
• 8.2 展望
• 创新点摘要
• 参考文献
• 致谢
• 攻读博士学位期间发表的论文
• 作者简历