大规模复杂生产调度问题瓶颈分解方法研究

摘要

生产调度问题是在时间上优化分配机器资源给相互竞争的工件，由于其强大的工程应用背景和优化求解的难处理性(NP-hard)，长期受到制造领域和学术界的高度重视。随着制造规模和复杂程度的不断提高，大规模复杂生产调度问题已成为当前制造业面临的难题，存在建模和优化求解的困难。分解方法是处理大规模复杂生产调度问题的一种常用方法，但传统的分解方法收敛速度慢，容易陷入局部最优。目前已有一些瓶颈调度方法试图从全局优化的角度处理大规模问题，但非常有限，在算法设计、理论分析和应用方面都存在很大的研究空间。本文利用瓶颈思想，结合分解方法，提出了一种瓶颈分解方法，并对大规模复杂生产调度问题进行了深入的研究。主要工作包括以下几个方面： ⑴在大系统分解思想的指导下，给出了车间调度问题机器层分解方法的一般描述，并指出传统分解方法在求解大规模调度问题时可能存在的不足。利用能力不均衡生产线存在瓶颈的特性，剖析瓶颈思想的内在机理，结合大系统分解思想提出了瓶颈分解方法的一般框架，并指出该方法的关键技术。 ⑵在分析单瓶颈Flowshop生产线特点的基础上，提出了一种单瓶颈分解算法。该方法将Flowshop上的机器分为瓶颈机、上游非瓶颈机和下游非瓶颈机。松弛非瓶颈机加工能力约束，原Flowshop问题简化为一个单机调度问题。瓶颈机的调度可以通过优化求解该简化问题获得。根据瓶颈机的调度结果，上游非瓶颈机采用有效的分派规则从后往前依次调度，而下游非瓶颈机则采用规则从前往后依次调度。随后我们给出了非瓶颈机冗余能力的条件，证明满足此条件下的Flowshop问题的最优调度为排列调度，即非瓶颈机上工件的加工安排与瓶颈机的调度安排一致。大量的仿真结果显示单瓶颈分解算法可以在较快的时间内获得较好的解。 ⑶针对单瓶颈Jobshop调度问题，提出了一种单瓶颈分解算法。该方法利用生产线主导瓶颈的特点将Jobshop中的机器分为瓶颈机和非瓶颈机。假设非瓶颈机加工能力无限大，将非瓶颈机上的工序集结成一个时间迟延环节，原问题则简化为一个带到达时间和传递时间约束的单机调度问题。瓶颈机上工件的加工安排可以通过优化求解此单机问题获得，而非瓶颈机则采用有效的启发式算法调度。通过调整瓶颈机上工序的到达时间和传递时间协调瓶颈机与非瓶颈机之间的关联。仿真结果显示该算法求解瓶颈程度较高的Jobshop问题非常有效。 ⑷针对能力较不均衡的Jobshop生产线，提出了一种约束调度算法。该算法给出了一种迭代辨识约束机(包括长期瓶颈和暂时瓶颈)的方法。每次迭代，采用有效的规则调度非约束机，并根据调度结果从中辨识约束机，该过程迭代进行直至不存在新的约束机。约束机模型可描述为一个带时间迟延的多机调度问题，该问题的最优解是原问题最优解的一个下界。随着约束机不断辨识，相应的约束机模型也迭代更新，我们证明约束机子问题的最优解在迭代过程中不断提高，朝着原问题最优解的方向逐步逼近。与传统的移动瓶颈方法相比，约束调度算法在提高计算效率的同时保证了调度的优化性能。大量的仿真比较研究显示，该算法可以在调度质量和计算时间之间获得一个好的均衡。 ⑸针对约束调度算法无法求解的更大规模Jobshop调度问题，提出了一种滚动瓶颈分解策略。该方法在瓶颈分解方法的基础上，结合滚动时域分解的思想，将整个调度时域分解为若干决策子窗口，每个时间窗口对应的子问题采用瓶颈分解方法求解。该方法从空间层和时间层对大规模问题进行分解，它为求解超大规模Jobshop调度问题提供了一种新的解决思路。仿真结果验证了滚动瓶颈分解方法的有效性。 ⑹将滚动瓶颈分解方法应用至一个更复杂的Jobshop调度问题，即半导体生产线，针对半导体生产线的机器加工类型不一，对分解后不同类型的子问题给出了相应的求解算法，并对经典模型MINIFAB进行详细的仿真测试研究。

目录

文摘

英文文摘

声明

第一章绪论

1.1引言

1.2生产调度问题的特点及研究进展

1.3大规模静态车间调度问题分解方法研究

1.4瓶颈调度方法的研究现状和存在的问题

1.5论文主要内容及章节安排

第二章大规模车间调度问题瓶颈分解方法一般描述

2.1引言

2.2车间调度问题机器层分解方法描述

2.3车间调度问题瓶颈分解方法一般框架

2.4本章小结

第三章单瓶颈Flow shop调度问题瓶颈分解方法研究

3.1引言

3.2 Flow shop调度问题描述和分析

3.3单瓶颈Flow shop调度问题瓶颈分解方法

3.4仿真测试与分析

3.5本章小结

第四章单瓶颈Job shop调度问题瓶颈分解方法研究

4.1引言

4.2 Job shop调度问题描述和分析

4.3单瓶颈Job shop调度问题瓶颈分解方法

4.4仿真测试与分析

4.5本章小结

第五章多约束机Job shop调度问题瓶颈分解方法研究

5.1 引言

5.2 Job shop调度问题描述与模型简化

5.3多约束机Job shop调度问题约束调度算法

5.4仿真测试与分析

5.5本章小结

第六章滚动瓶颈分解方法研究及其在半导体生产中的应用

6.1 引言

6.2大规模Job shop问题滚动瓶颈分解方法研究

6.3半导体生产线滚动瓶颈分解方法研究

6.4 本章小结

第七章总结与展望

参考文献

附录

致谢

攻读博士学位期间发表的浨论文(第一作者)及承担的研究项目