基于进化计算的多目标流水车间批组调度问题研究

论文摘要

流水车间批组调度(Flowshop Scheduling with Batching, FSB)问题在实际制造系统中有着广泛的应用背景,比传统的流水车间调度问题更复杂,有效的调度算法可以提高资源的利用率和生产效益。因此,FSB问题的研究具有重要的理论和实用价值。相对于传统的优化方法,进化算法在解决多目标优化问题时具有一定的优势,因此本文采用进化算法解决多目标FSB问题,针对FSB问题的三个分支(带有成组工件的FSB问题、批交付FSB问题以及具有批加工设备的FSB问题)展开研究,取得了较好的结果。主要内容如下：研究带有成组工件的FSB问题,建立了同组工件可拆分条件下的多目标优化模型,设计了多目标混合遗传算法(MOHGA).算法中引入基于累计排序策略和自适应密度评估的适应度计算方式更好地保持群体多样性,并根据问题的特征定义了两种邻域结构进行局部搜索提高算法的收敛速度。基准问题和实际问题的求解结果,验证了所提算法的有效性。应用有限Markov链的有关理论分析了MOHGA的收敛性。构建了批交付FSB问题的多目标优化模型,首先对提前／拖期最小化问题,分析了优化调度的性质,给出了工件排序一定时确定开工时间的最优算法,实验分析了成组技术约束对提前／拖期目标的影响。其次对包含提前／拖期在内的多个目标的高维优化问题,提出了利用权重向量控制进化方向的可控权重进化算法(CWEA)。仿真算例和调度实例的计算结果表明,CWEA能有效克服单纯Pareto排序比较在解决高维优化问题时的困难,对于双目标和目标数目较多的优化问题均能获得较多的分布更均匀的解。针对有不可用时间段约束的FSB问题,提出采用工件的非置换排序以减少机器额外的空闲时间,并研究了机器有固定的不可用时间段和机器不可用时刻基于运转时间两种情况下的调度优化。提出启发式算法生成工件在各机器上的调度,基于改进的可控权重进化算法(ICWEA)优化工件调度的优先级顺序。通过对不同规模的调度实例进行计算,结果表明,ICWEA在求解该类问题时有较好的优化效果。研究具有批加工设备的FSB问题。首先针对混合两工序批调度问题提出顺序分批方法对工件进行分批,采用改进的可控权重进化算法(ICWEA)优化工件调度优先排序。其次对工件有不同尺寸,批加工时间可变的两机批调度问题,设计了多目标混合粒子群优化算法(MOHPSO)进行优化,利用整批对换式邻域进行局部搜索。仿真实验表明,在求解两机批调度问题时,MOHPSO算法性能优于其他几种多目标粒子群优化算法。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景和研究意义
• 1.1.1 研究背景
• 1.1.2 研究意义
• 1.2 相关研究概述
• 1.2.1 批组调度问题
• 1.2.2 批组调度问题的研究方法
• 1.2.3 多目标调度问题
• 1.2.4 多目标调度问题的求解方法
• 1.2.5 进化计算在多目标调度中的研究现状
• 1.3 课题的提出
• 1.4 研究思路和方法
• 1.5 论文主要内容和结构安排
• 2 多目标优化与多目标进化算法
• 2.1 多目标优化的基本概念
• 2.1.1 多目标优化问题的数学描述
• 2.1.2 多目标优化问题的解
• 2.2 多目标进化算法
• 2.2.1 进化算法的原理和方法
• 2.2.2 多目标进化算法设计的关键技术
• 2.2.3 代表性多目标进化算法
• 2.2.4 现有算法研究的不足
• 2.3 多目标进化算法的性能评估
• 2.4 本章小结
• 3 带有成组工件的FSB问题研究
• 3.1 引言
• 3.2 问题描述及优化模型
• 3.2.1 问题描述
• 3.2.2 优化模型
• 3.3 多目标混合遗传算法
• 3.3.1 多目标混合遗传算法的设计策略
• 3.3.2 MOHGA的实现
• 3.3.3 MOHGA算法步骤
• 3.4 MOHGA收敛性分析
• 3.4.1 预备定义
• 3.4.2 有限Markov链基本定义和定理
• 3.4.3 MOEA收敛性定义
• 3.4.4 算法收敛性分析
• 3.5 仿真实验
• 3.5.1 测试问题
• 3.5.2 计算结果和比较
• 3.6 应用实例
• 3.7 本章小结
• 4 批交付FSB问题的多目标优化
• 4.1 引言
• 4.2 多目标优化模型
• 4.2.1 问题描述
• 4.2.2 Pareto最优前沿
• 4.3 提前/拖期最小的优化算法
• 4.3.1 优化调度的性质
• 4.3.2 基于延迟调整算法的最优开工时间确定
• 4.3.3 基于遗传算法与延迟调整算法的优化
• 4.3.4 实验结果和分析
• 4.4 可控权重进化算法
• 4.4.1 可控权重进化算法的设计策略
• 4.4.2 CWEA的关键技术
• 4.4.3 基于CWEA的多目标优化
• 4.4.4 仿真实验
• 4.5 实例计算
• 4.6 本章小结
• 5 有不可用时间段约束的FSB问题研究
• 5.1 引言
• 5.2 问题描述及分析
• 5.2.1 问题描述
• 5.2.2 数学模型
• 5.2.3 问题分析
• 5.3 固定不可用时间段下的调度优化
• 5.3.1 调度生成算法
• 5.3.2 基于CWEA的优化方法
• 5.3.3 仿真实验
• 5.4 不可用时刻基于运转时间的调度优化
• 5.4.1 调度策略与算法
• 5.4.2 改进的可控权重进化算法
• 5.4.3 基于ICWEA的优化
• 5.4.4 仿真实验
• 5.5 实例优化与分析
• 5.6 本章小结
• 6 具有批加工设备的FSB问题研究
• 6.1 引言
• 6.2 混合两工序流水车间批调度问题
• 6.2.1 数学模型
• 6.2.2 基于ICWEA的优化
• 6.2.3 仿真实验
• 6.3 两机流水车间批调度问题
• 6.3.1 数学模型
• 6.3.2 特殊情况下解的性质
• 6.3.3 粒子群优化算法
• 6.3.4 基于MOHPSO的优化
• 6.3.5 仿真实验
• 6.4 应用实例
• 6.5 本章小结
• 7 总结与展望
• 创新点摘要
• 参考文献
• 附录A 缩略语
• 攻读博士学位期间发表学术论文情况
• 致谢