Robust parallel machine selection and scheduling with uncertain release times

Linyuan Hu, Yuli Zhang, Muyang Wen, Roel Leus and Ningwei Zhang

European Journal of Operational Research, 2025, vol. 327, issue 3, 838-856

Abstract: 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.

Keywords: Robust optimization; Parallel machine scheduling; Benders cuts; Logic-based benders decomposition (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725004163
Full text for ScienceDirect subscribers only

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:eee:ejores:v:327:y:2025:i:3:p:838-856

DOI: 10.1016/j.ejor.2025.05.032

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().