影响因子：

6.0

DOI码：

10.1016/j.ejor.2025.08.039

发表刊物：

European Journal of Operational Research

摘要：

The PDF version of the paper can be downloaded via the link: https://authors.elsevier.com/a/1llfY1LnJ6wwkn. The Distributed Flexible Job Shop Scheduling Problem (DFJSP) is a well-known NP-hard optimization problem with widespread applications in production scheduling. It involves assigning jobs to factories, allocating operations to machines, and sequencing operations on each machine, which presents significant computational challenges. Although heuristic and metaheuristic approaches have been extensively studied, the exploration of exact algorithms for solving DFJSP remains limited. This paper addresses this gap by proposing three logic-based Benders decomposition (LBBD) frameworks specifically designed for the DFJSP, leveraging the problem’s decomposable structure to achieve optimal or near-optimal solutions with quantifiable quality guarantees within strict time limits. In each LBBD framework, the DFJSP is decomposed into a master problem and several subproblems based on specific decomposition schemes. The corresponding Mixed-Integer Linear Programming (MILP) models and Constraint programming (CP) models for these problems are formulated and solved alternately. Additionally, a hybrid optimization approach is developed by integrating LBBD with CP and heuristic search strategies. The proposed method includes an enhanced CP model with targeted improvements to boost its solving efficiency and incorporates a critical path-based local search strategy to further refine the solution quality. Moreover, several strong subproblem relaxation schemes are incorporated into the master problem under different LBBD frameworks. Comprehensive evaluations on an extended benchmark dataset containing 286 instances demonstrate that the hybrid algorithm achieves an average optimality gap of less than 1.2%. Compared to state-of-the-art MILP, CP, and heuristic methods, the proposed approach delivers superior solution quality and computational efficiency, establishing a new benchmark for solving the DFJSP.

合写作者：

刘恒冲

第一作者：

熊福力

论文类型：

期刊论文

学科门类：

管理学

一级学科：

管理科学与工程

文献类型：

J

是否译文：

否

发表时间：

2025-01-01

收录刊物：

SCI

发布期刊链接：

https://doi.org/10.1016/j.ejor.2025.08.039