基于混合遗传算法的流水线车间回收调度问题研究

论文摘要

在过去近七十年的时间里,车间调度问题已经被较为深入,透彻地研究,但随着社会经济的发展、人类环保意识的增强,回收再制造逐渐成为学者及相关领域技术人员关注的焦点,而如何将逆向物流中的回收组件融入现有生产线,实现关于组件再制造与制造的混合多组件批量调度却鲜有文献涉及。基于此,本文将研究的重点放在回收组件再制造的开始时间的设计与各组件各道工序总调度的安排上,实现在柔性流水线车间(flexible flow line)有限计划期内关于再制造与制造的混合批量调度以及完工组件递送问题。本文研究的内容是：组件供应商在柔性流水生产线上加工多种组件,并将最终将加工出来的组件递送到组装车间(AF),力求在单位时间内平均投入总成本(传送成本、组件启动成本和库存持有成本)最低问题。由于此生产线还涉及到对回收组件处理,因而其过程分为制造与再制造。尤其关注的是组件加工的每阶段在多台平行机中的指派问题、在每台机器中各组件的加工顺序以及回收组件再造开始时间的选择。回收的组件质量不确定直接导致其再制造阶段的不同,本文经分析将其分为两种情况进行讨论：组件回收再制造是用最后阶段某台机器进行加工还是用中间某一阶段某台机器进行加工这两种情况,并针对上述情况逐一建立非线性整数规划模型,结合枚举方法OEM以将此问题化为线性问题,并运用ILOG CPLEX软件进行求解。考虑到问题规模以及运算的复杂性,为了在合理时间内求得最优或近似最优解而提出混合遗传算法,并为了在子空间得到更优的解,将邻域搜索运用其中。特别需强调的是：在混合遗传算法中,初始种群选择的好坏很大程度影响着算法的效率,因此本文针对不同情况,提出不同算法以形成初始种群。在初始种群的形成以及组件在各阶段每台机器的加工指派的确定中,由于涉及回收组件的再制造,因而在研究时分为两种情况：(1)若组件回收再制造是用最后阶段某台机器进行加工,初始种群中各染色体的形成分别则运用CDS、Palmer、RA、Gupta等启发式算法,组件各阶段在机器的加工的指派则由FAM、MFAM规则；(2)若回收再制造中间某一阶段某台机器进行加工,则运用Flowmult算法,同时结合FAM思想,以确定组件各阶段在机器加工的指派问题。至于回收组件再制造开始时间的设计则是本着减少机器空闲等待时间以及降低库存持有成本的原则。本文最后将混合遗传算法所得解与ILOG CPLEX所得值、目标函数的最低边界值LB(Lower bound for total cost)分别通过算例进行比较,指出混合遗传算法能够在合理时间内对中等和大规模这类问题求得有效解。

论文目录

• 摘要
• Abstract
• 目录
• 第1章 绪论
• 1.1 研究背景
• 1.1.1 车间调度问题的发展
• 1.1.2 基于再制造的闭环供应链的发展
• 1.2 问题提出
• 1.3 研究目的和研究意义
• 1.3.1 研究目的
• 1.3.2 研究意义
• 1.4 研究内容与方法
• 1.4.1 研究内容
• 1.4.2 研究方法
• 1.5 论文框架与结构安排
• 第2章 文献综述与相关理论
• 2.1 国内外研究现状及发展动态
• 2.1.1 流水车间调度问题研究综述
• 2.1.2 作业车间调度问题调度研究状况
• 2.1.3 国内外有关产品回收再制造经济批量调度问题研究现状
• 2.2 启发式算法相关理论
• 2.2.1 Johnson启发式算法
• 2.2.2 CDS启发式算法
• 2.2.3 Palmer启发式算法
• 2.2.4 RA启发式算法
• 2.2.5 Gupta启发式算法
• 2.3 智能优化算法之遗传算法相关理论
• 2.3.1 遗传算法概述
• 2.3.2 遗传算法步骤及特点
• 第3章 制造与再制造组件库存水平分析
• 3.1 完工组件库存水平分析
• 3.1.1 全部由原材料加工而来的完工组件的库存水平分析
• 3.1.2 部分源于再制造的完工组件的库存水平分析
• 3.2 在制组件库存水平分析
• 3.2.1 全部由原材料加工的在制组件的库存水平分析
• 3.2.2 部分源于再制造的在制组件的库存水平分析
• 3.3 回收组件尚未开始再制造时的库存水平分析
• 3.4 组装中心的库存水平分析
• 第4章 组件制造与再制造调度分析及模型构建
• 4.1 关于组件制造与组件部分回收再造调度问题约束分析
• 4.1.1 组件依次进入各阶段调度问题分析
• 4.1.2 各阶段组件开始时间调度问题分析
• 4.1.3 机器特定顺序某位置上只能有一种组件进行生产问题分析
• 4.1.4 组件在某台机器特定顺序相应位置上加工的调度分析
• 4.1.5 组件在机器依先后顺序进行加工的位置分析
• 4.1.6 组件加工开始时刻一定后于其准备开始时刻的调度分析
• 4.2 关于组件制造与组件部分回收再造调度问题模型构建
• 4.2.1 回收组件再造用最后阶段某机器加工的各组件总调度模型构建
• 4.2.2 回收组件再造用中间某阶段机器加工的各组件总调度模型构建
• 4.2.3 最优求解方法设计
• 第5章 基于启发式算法设计组件初始加工顺序
• 5.1 回收再造发生在最后阶段的调度顺序设计
• 5.1.1 最后阶段回收组件再造开始时刻分析
• 5.1.2 回收再造利用最后阶段的各组件总调度顺序设计
• 5.2 回收再造发生在中间某一阶段的调度顺序设计
• 5.2.1 各组件总加工时间下界分析
• 5.2.2 回收再造发生在中间某一阶段的各组件总调度顺序设计
• 第6章 基于混合遗传算法优化组件总调度
• 6.1 混合遗传算法调度设计
• 6.1.1 创建染色体
• 6.1.2 初始种群的形成
• 6.1.3 适值函数的确定
• 6.1.4 交叉、变异
• 6.1.5 领域搜索与终止准则
• 6.2 算例分析
• 6.2.1 回收组件的再制造用最后阶段某台机器进行加工的算例分析
• 6.2.2 回收组件的再制造用中间阶段某一机器加工的算例分析
• 第7章 总结与展望
• 7.1 论文的主要工作
• 7.2 论文的创新点
• 7.3 研究不足及展望
• 参考文献
• 致谢