A two-stage iterated greedy algorithm for distributed blocking flowshop scheduling problem

Sen Zhang

doi:10.1016/j.eswa.2025.130422

A two-stage iterated greedy algorithm for distributed blocking flowshop scheduling problem

2025-11-17

0

PRE

AI

DOI：10.1016/j.eswa.2025.130422

原文链接

原文求助

摘要

En 中文

本文研究了分布式阻塞流水车间调度问题（DBFSP），该问题是现代制造系统中涉及多个工厂的关键挑战。每个工厂作为一个阻塞流水车间运行，且相邻机器之间无中间缓冲区。DBFSP的目标是所有工厂中的完工时间最小化。首先，基于工件的位置提出了一种混合整数线性规划模型（MILP）。其次，通过分析问题特定性质，证明了两个定理：（1）从工厂中移除一个工件会减少该工厂的完工时间，（2）向工厂中插入一个新工件会增加该工厂的完工时间。然后，提出了一种有效的两阶段迭代贪婪算法（TIG）。TIG包括一个构造性启发式方法、一个根据上述两个定理设计的具有多邻域结构的局部搜索过程，以及一种结合每个工件的总阻塞时间和空闲时间的创新性破坏与构建策略。最后，对720个基准实例的实验结果表明，所提出的TIG算法优于当前最优的DBFSP方法。此外，在720个实例中有320个实现了新的已知最优解，且优势显著。

A two-stage iterated greedy algorithm for distributed blocking flowshop scheduling problem

摘要

期刊

机构

引用论文