双机流水车间问题基于冲突窗口的滚动调度算法

摘要

生产调度问题存在于大量实际制造业中，构成了各种先进制造模式共同关注的核心内容和重要组成部分，对于车辆调度、铁路调度、航空调度、企业多项目管理的等资源调度问题，也大多可以利用生产调度的基本原理，可以说，生产调度这一基本原型应用领域是非常广泛的。同时，生产调度问题也是一类非常典型的组合优化问题，在求解方面具备相当的难度，其计算量通常随调度问题规模呈指数增长，绝大多数调度问题都属于NP完备问题。因此，无论在实际工业生产方面，还是在理论学术研究方面，对生产调度问题的研究都有着非常重要的意义。
　　生产调度的算法可简单概括为精确算法、启发式算法和人工智能算法。精确算法能获得最优解，但是计算效率低，遇到大规模的复杂问题，这种算法有时甚至难以获得解。由此而发展起来的启发式算法则是利用启发式规则，在较短的时间内便能获得相对不错的解，目前已扩展了相当多的启发式规则。随着科技进步，人工智能算法是目前研究较为集中的一种算法，它具有搜素效率高，适应性强和鲁棒性能好等特点，但是这类算法也不能保证获得最优解。由于流水车间的特点，本文主要着眼于启发式算法。
　　在启发式算法下，本文采用滚动调度策略，研究了流水车间双机调度问题。滚动调度策略下，将一个大规模问题分解为许多子问题，可使问题规模大大减小，有效缩短求解时间。滚动调度多用于单机情形，此次将其应用于流水车间双机情形，同时跳出传统的滚动调度策略框架，即基于时间的滚动调度和基于工件数的滚动调度，提出本文新的滚动调度算法——基于冲突窗口的滚动调度算法。该算法充分利用了流水车间双机问题的特点，结合了经典的Johnson规则。
　　在本文中描述了冲突窗口的形成，子问题的最优调度，列述了算法的基本思路和步骤。另外，本文采用大规模仿真的方法，将本算法与另三种算法，即基于时间的滚动调度算法、基于工件数的滚动调度算法和贪婪Johnson算法进行了大量对比，这三类算法是流水车间比较传统的算法。仿真模拟了各算法在工件数为10到500个时的具体表现，并通过控制参数使得工件的到达呈现不同的紧密程度。最终实验结果显示，除了工件数为10时，基于时间的滚动调度算法比基于冲突窗口的滚动调度求解的质量更优，其余情况下，基于冲突窗口的滚动调度平均表现都是最好的，另外本论文提出的算法在计算量上相对另两种滚动调度算法具有绝对的优势，即使解决500个工件的大规模问题，效率也非常高，贪婪Johnson算法虽然在时间上也具有优势，但在四种算法中解的质量最差。
　　最后本文将基于冲突窗口的滚动调度应用于带有季节性需求特征的具体实例中，以探讨其实际应用价值。通过仿真的方法，基于冲突窗口的滚动调度相较于基于时间的滚动调度能更好地处理需求波动大的季节性产品，其求解速度更快，求解质量更好。

目录

封面

声明

中文摘要

英文摘要

目录

1. 绪论

1.1 研究背景

1.2 研究目的及意义

1.3 本文所做的主要工作

1.4 本文组织架构

2. 研究现状综述

2.1 流水车间调度问题概述

2.2 流水车间双机调度问题现状

2.3 调度策略研究现状

3. 双机流水车间调度模型与传统算法

3.1 双机流水车间模型建立

3.2 双机调度传统算法

4. 双机流水车间基于冲突窗口的滚动调度

4.1滚动算法概述

4.2冲突窗口的定义

4.3算法过程及步骤

5. 仿真及其结果分析

5.1仿真数据设置

5.2性能值确定

5.3用于比较的算法

5.4 仿真结果分析

5.5 算法小结

6. 季节性特性的行业应用分析

6.1 季节性特性的行业研究

6.2 仿真环境搭建

6.3 仿真比较结果

7. 总结及展望

参考文献

致谢