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

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.