Optimizing parallel machine location and scheduling with sequence-dependent setup times via logic-based benders decomposition

Yun Wang (), Peng Wu, Zhe Yuan, Yeming Gong () and Ajay Kumar ()
Additional contact information
Yun Wang: Fuzhou University [Fuzhou]
Peng Wu: Fuzhou University [Fuzhou]
Zhe Yuan: PULV - Pôle Universitaire Léonard de Vinci
Yeming Gong: EM - EMLyon Business School
Ajay Kumar: EM - EMLyon Business School

Post-Print from HAL

Abstract: This study introduces a novel problem in parallel machine location and scheduling that considers one key practical factor: sequence-dependent setup times. Its objective is to minimize the makespan by optimally selecting machine locations, assigning jobs to these machines, and determining the operation sequences, while accounting for the challenging sequence-dependent setup time constraints. We first construct a new compact mixed-integer linear programming (MILP) model with a stronger linear relaxation lower bound, which is then strengthened with a set of valid inequalities derived from its structural properties. To solve practical-sized instances more efficiently, we propose an exact, customized full-feature logic-based Benders decomposition algorithm (FLBBD). The FLBBD incorporates three advanced features: (i) we propose new valid lower and upper bounds to further shrink the search space of the FLBBD; (ii) we propose a tailored constraint programming approach to efficiently solve NP-hard subproblems; (iii) we propose specialized combinatorial and analytical cuts to further accelerate the solution process. Detailed experimental results show that (i) The proposed FLBBD algorithm can solve a significantly greater number of instances to optimality compared with the off-the-shelf MILP solver CPLEX and BD incorporated within CPLEX; (ii) The FLBBD algorithm finds feasible solutions for 100% instances whereas CPLEX and BD solve only 81.17% and 57.65% instances; (iii) The FLBBD algorithm attains a smaller average optimality gap of 4.89%, in contrast to the 59.10% and 26.09% average optimality gap observed for CPLEX and BD; and (iv) The derived valid inequalities reduces 6.67% computational time and 62.37% optimality gap compared with CPLEX.

Keywords: Combinatorial optimization; Constraint programming; Logic-based benders decomposition; Parallel machine location and scheduling; Sequence-dependent setup times (search for similar items in EconPapers)
Date: 2026-06-27
References: Add references at CitEc
Citations:

Published in European Journal of Operational Research, inPress, ⟨10.1016/j.ejor.2026.06.027⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-05704514

DOI: 10.1016/j.ejor.2026.06.027

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().