基于混合遗传算法的可重入混合流水车间调度优化研究

摘要

进入二十一世纪以来，制造型企业在提高生产效率、增加生产灵活性的内在需求推动下，一种新型的制造车间—可重入混合流水车间（reentrant HFS，RHFS）—引起了国内外学者的关注。RHFS的基本特征是一个工件可以多次访问某些工站，它是以半导体制造、钢铁生产、客车制造等为代表的一类生产调度问题。RHFS问题比传统混合流水车间（HFS）更为复杂，其建模、优化理论与方法研究更是一个具有挑战意义的课题。 本文主要探讨了一类考虑工件动态到达和在相邻两阶段间运输时间等多组约束的多阶段RHFS调度问题。以往很多学者对HFS的探讨多针对最大完工时间（makespan）最小化问题，该目标是指企业按照要求把全部工件加工完成所需要的时间，工件最大完工时间越短，说明企业的效率越高，反之，企业加工缓慢，影响之后的调度决策，最大完成时间的大小是决定企业生产调度是否良好的重要指标。因此，本文首先在 RHFS 环境下研究了最大完工时间最小化问题。考虑到总加权完工时间近年来也越来越受到众多学者的关注，它与如今的动态生产环境密切相关，因为在订购产品时有许多客户希望以最快的速度交付产品，理想情况下是所有订单都能按时交付，但在现实中很难实现，因此如何科学有效的确定不同客户的产品交付顺序，受到制造型企业的关注。基于客户的要求，对各个客户的工件完成时间赋予不同的权重因子，求解最小的总加权完成时间以得到更好的调度决策。故本文在makespan问题的研究基础上，继而探讨了以总加权完成时间为目标函数的RHFS调度优化。 首先，分别以上述与完工时间相关的费用函数为目标，从生产实际提炼出机器能力约束、优先级约束等工艺与资源约束条件，进而建立数学规划模型。其次，分析模型的特点，将遗传算法与构造型启发式算法进行融合，提出一种针对 RHFS 问题的混合遗传算法。在算法中，为生成高质量的初始调度解群，设计了基于初始层-重入层加工系统的二维矩阵编码方式，并采用NEH启发式算法来进行工件初始加工顺序安排；然后，为防止算法提前收敛，引入了基于交叉和变异概率的自适应动态调整策略，最终形成HGA算法。最后，利用所提出的算法对不同规模问题进行仿真测试，结果表明所提算法能在较短的计算时间内获得较好的近优解，具有良好的性能，可以为制造型企业的调度决策提供参考。

目录

第一个书签之前