Robust parallel machine selection and scheduling with uncertain release times

This paper studies a parallel machine selection and scheduling (PMSS) problem with uncertain release times. To handle uncertain release times, we propose a two-stage robust PMSS model where the release time deviation (RTD) is characterized by a budget uncertainty set. In the first stage, machine selection and job assignment decisions are made to minimize startup costs before the uncertainties are revealed. In the second stage, once release times are known, job sequences are optimized to minimize the makespan on each machine. Robust constraints are introduced to ensure that the worst-case minimum makespan on each machine does not exceed a pre-specified due date. The proposed model is a tri-level min–max–min optimization problem with mixed-integer recourse decisions, which cannot be solved efficiently by existing algorithms. To this end, we propose a novel logic-based Benders decomposition (LBBD) algorithm with strengthened Benders cuts and speedup techniques. Specifically, we first provide an equivalent mixed-integer linear programming reformulation for the max–min subproblem by analyzing an optimality condition of the worst-case RTD. Second, we design novel combinatorial and analytical Benders cuts, which dominate cuts found in the literature, and we further strengthen them by lifting procedures. Third, we design a relaxation-and-correction procedure and a warm-start procedure to speed up the LBBD algorithm. Numerical experiments show the proposed robust model greatly reduces job tardiness compared with the deterministic model. The proposed cuts efficiently reduce the runtime, and the LBBD algorithm is at least three orders of magnitude faster than the state-of-the-art column-and-constraint-generation algorithm.