考虑必经工序的混合流水车间调度的迭代贪婪算法研究

摘要

针对混合流水车间调度问题(Hybrid Flow Shop Scheduling Problem, HFSP)展开深入研究，建立了以最小化最大完工时间为优化目标的数学模型，提出了基于必经工序的迭代贪婪算法(Mandatory Operations-based IG Algorithm, MOAIG)。首先，给出了与必经工序相关的4个引理；其次，设计了调度序列的图空间表示方式，并针对HFSP多阶段的特点，将图空间中关键路径上的必经工序进行局部搜索，提高了局部搜索效率，拓展了搜索空间；然后，为了增加破坏操作的灵活性和多样性，提出了保守跳跃破坏策略；最后，通过对576个典型测试算例的数值仿真以及与3种代表算法的统计比较，验证了所提基于必经工序的加速迭代贪婪算法的有效性和优越性。

关键词

混合流水车间调度 / 最大完工时间 / 图空间 / 保守跳跃破坏 / 必经工序 / 迭代贪婪算法