自动化制造系统实时反馈式调度方法研究

摘要

自动化制造系统，作为一类先进智能制造系统，已被广泛应用于半导体制造、印刷电路板电镀处理以及钢铁生产等行业。在这类制造系统中，一个或者多个由计算机控制的机器人负责物料在自动化加工设备（工作站）之间的搬运作业。相对于工件加工时间，工件在工作站之间的搬运时间不能忽略，并且工件的加工工序和搬运作业需要相互协调。因此，合理的规划和调度机器人的搬运作业对提高自动化制造系统生产效率和产品质量具有重要作用。然而实际生产环境中充满了不确定性，各类干扰事件的发生，例如客户订单随机到达、加工设备故障等，往往影响自动化制造系统的稳定运作，甚至造成当前调度方案不可行。当干扰事件发生时，为了保持自动化制造系统的高效稳定运作，实际生产管理者需要动态调整调度方案甚至生成新的方案。然而，频繁地动态调整或者完全重新生成新调度方案，往往使已进入系统工件的加工作业和搬运作业严重偏离原调度方案，由此给自动化制造系统的稳定运作带来了扰动，甚至导致系统崩溃。
　　通过文献回顾发现，已经有大量文献对确定性环境下的静态周期调度问题进行了深入研究，并提出了各种周期调度模型和算法。目前有关自动化制造系统反馈式调度问题的研究，主要集中在当干扰事件发生后如何快速的调整或者完全生成新的调度方案，以保持制造系统的生产效率，而忽略了新的调度方案对系统运作带来的扰动影响。
　　本文针对不确定性环境下多个新工件任意时刻到达自动化制造系统的情况，研究提出了考虑调度稳定性的实时反馈式调度模型和算法。当多个新工件到达系统时，保持已进入系统工件的加工作业和搬运作业的原调度方案不变，利用工作站和物料搬运机器人的空闲区间内完成新工件的加工工序和搬运作业。本文主要研究内容为：
　　（1）首先构建了以最小化系统makespan为目标的反馈式调度混合整数规划模型，并利用商业优化软件CPLEX求解问题的最优调度方案；
　　（2）由于该问题属于NP-hard问题，本文将文献中针对单个新工件反馈式调度的多项式算法拓展为在按给定工件插入排序下的多工件反馈式调度算法，并分析证明该算法具有多项式时间计算复杂度；
　　（3）为了获得问题的近似最优调度方案，本文进一步提出混合离散差分进化算法以搜索一组“最好”的工件插入排序。在进化算法中，以新工件的插入排序（即工件编号的排列组合）作为种群个体的染色体信息，利用拓展的反馈式调度算法评价个体的质量（即makespan值），并通过离散交叉变异算子和一对一贪婪选择算子推动种群向“最好”的工件插入排序进化。
　　（4）最后，随机测试计算结果检验了本文提出混合离散差分进化算法能快速的获得该问题近似最优调度方案。

目录

声明

第一章 绪 论

1.1 研究背景

1.2 研究内容和思路

1.3论文结构安排

1.4 本章小结

第二章 国内外研究现状综述

2.1 自动化制造系统周期调度研究

2.2 自动化制造系统反馈式调度研究

2.3 离散差分进化算法求解生产系统调度问题研究

2.4 本章小结

第三章 本文研究问题描述与分析

3.1 问题描述与符号定义

3.2 新旧调度切换时刻的计算

3.3 可利用空闲区间的构建

3.4 算例演示

3.5 本章小结

第四章 混合整数规划模型构建及求解

4.1 混合整数规划模型构建

4.2 基于CPLEX求全局最优解

4.3 本章小结

第五章 混合离散差分进化算法求近似最优解

5.1 HDDE算法设计与实现

5.2 基于HDDE搜索求近似最优解

5.3 变异交叉算子实例演示

5.4 本章小结

第六章 算例验证与数值分析

6.1 测试算例产生

6.2 实验结果分析

6.3 本章小结

第七章 总结与展望

7.1 本文研究工作总结

7.2 论文不足之处及展望

致谢

参考文献

攻读硕士学位期间取得的成果