基于遗传算法的再制造产品拆卸批量计划问题研究

摘要

拆卸是再制造过程中非常重要的一个环节，拆卸批量计划更是在对拆卸进行计划与控制时需要优先考虑的问题。拆卸批量计划问题是指在一定计划期内规划回收废旧产品在各时刻的拆卸数量，使其在满足各时刻的外部需求的同时，符合系统的正常拆卸能力。以往的研究并未考虑到很多现实的因素，如拆卸能力约束的形式并不单单是时间，也可以包括人力、资金等方面。同时，拆卸能力约束能否通过加班进行消除也值得考虑。在模型求解方面，以往的研究主要集中于精确算法，如动态规划算法、分枝定界算法、拉格郎日松弛法等。由于问题本身所固有的计算复杂性，其求解的计算时间往往随问题规模的增大而呈指数型增长。这些因素非常不利于现有的研究在实际拆卸中的应用。针对以上不足，本文针对单级产品结构、不存在通用性零部件的拆卸批量计划问题从模型的构建和求解算法两个方面进行了扩展，分别研究了启发式遗传算法在无拆卸能力约束的情况下、多种拆卸能力约束不允许加班和允许加班情况下的拆卸批量计划问题。 针对无拆卸能力约束的拆卸批量计划问题，研究了该问题最优解的一些性质，并得出了两个一般性的结论来降低搜索空间。根据该问题的特点，创新性的应用拆卸决策变量表示染色体编码，并对适应度函数进行了线性变化，设计了具有自适应性的交叉概率和变异概率的改进遗传算法，仿真实验证明了算法性能的优越性。 针对多种拆卸能力约束、不允许加班情况下的拆卸批量计划问题，设计了一种两阶段的启发式遗传算法进行求解。首先在不考虑拆卸能力约束情况下求解出初始的拆卸批量计划，然后根据拆卸能力的约束应用转移算法对初始得到的批量计划进行修改，使其符合拆卸能力的约束。大量随机算例的仿真实验证明了本算法不论是在寻找最优解方面还是在求解速度和稳定性上面，都要大大的优于精确算法，能够较好的解决实际生产中面临的多种拆卸能力约束、不允许加班情况下拆卸批量计划问题。 针对多种拆卸能力约束、允许加班情况下拆卸批量计划问题，对不考虑加班的拆卸批量计划问题模型进行了进一步的扩展。提出了一种两阶段的启发式遗传算法进行求解。首先求解得到不考虑拆卸约束的初始批量计划，然后应用转移算法从最后一个时刻到第一个时刻进行逆推检查，如果现有的拆卸需求的能力超过了系统正常的能力，首先通过允许加班消除能力约束的限制，如果通过加班现有拆卸需求的能力仍然超过了系统在允许加班情况下最大的能力，则应用转移算法将当前时刻超过系统正常能力的部分转移到前一个时刻去。大量的随机仿真算例证明了本算法具有良好的搜索最优解的能力，而且求解中等规模的问题仅需要很短的时间，具有良好的求解速度和稳定性。

目录

文摘

英文文摘

声明

第一章 绪论

1.1 论文的研究背景和意义

1.2 拆卸批量计划问题的概述

1.2.1 拆卸批量计划问题的定义及内容

1.2.2 拆卸批量计划问题的分类

1.3 国内外研究综述

1.4 论文研究内容和创新点

1.4.1 论文研究内容

1.4.2 论文的创新点

1.5 本文的框架结构

第二章 优化算法概述

2.1 精确算法

2.2 启发式算法

2.3 遗传算法简述

2.4 遗传算法基本流程

2.5 算法关键参数和操作的设计

2.5.1 编码

2.5.2 适配值函数

2.5.3 算法参数

2.5.4 遗传算子

2.5.5 算法的终止条件

2.6 本章小结

第三章 基于遗传算法的无拆卸能力约束的拆卸批量计划问题研究

3.1 引言

3.2 SAUDSP问题

3.2.1 问题描述

3.2.2 产品结构

3.2.3 相关费用

3.2.4 SAUDSP问题的整数规划模型

3.3 SAUDSP问题最优解性质分析

3.4 SAUDSP问题遗传算法设计

3.4.1 染色体的构造

3.4.2 初始种群的构造

3.4.3 适应度函数及其转换

3.4.4 选择操作

3.4.5 交叉操作和交叉概率的自适应性

3.4.6 变异概率的自适应性

3.4.7 算法终止条件

3.5 仿真实验

3.6 本章小结

第四章 基于遗传算法的有拆卸能力约束、不允许加班的拆卸批量计划问题研究

4.1 引言

4.2 不允许加班的SACDSP问题

4.2.1 问题描述

4.2.2 不允许加班的SACDSP问题的整数规划模型

4.3 不允许加班的SACDSP问题的遗传算法设计

4.3.1 染色体的构造

4.3.2 遗传算子和参数设置

4.4 仿真实验

4.5 本章小结

第五章 基于遗传算法的有拆卸能力约束、允许加班的拆卸批量计划问题研究

5.1 引言

5.2 允许加班的SACDSP问题

5.2.1 问题描述

5.2.2 允许加班的SACDSP问题的整数规划模型

5.3 允许加班的SACDSP问题的遗传算法设计

5.3.1 染色体的构造

5.3.2 遗传算子和参数设置

5.4. 仿真实验

5.5 本章小结

第六章 结论和展望

6.1 本文结论

6.2 对未来研究的展望

致 谢

参考文献

硕士在读期间发表的论文与参与的课题研究