Flow-shop and job-shop robust scheduling problems with budgeted uncertainty

Carla Juvin, Laurent Houssin and Pierre Lopez

European Journal of Operational Research, 2025, vol. 326, issue 1, 54-68

Abstract: In this paper, we study different solution methods for two two-stage robust, multi-machine scheduling problems, namely permutation flow-shop and job-shop scheduling problems under uncertainty budget. Compact formulations of the problems are proposed and two decomposition approaches are presented: a Benders decomposition approach and a column and constraint generation approach. Computational experiments show that for small-sized instances, a compact formulation of the problem quickly yields optimal solutions. However, for larger instances, decomposition methods, particularly the column and constraint generation method with a master problem solved using constraint programming, provide better quality solutions. An acceleration method for the column and constraint generation algorithm is proposed. This method is generic and can be applied to any two-stage robust optimisation problem.

Keywords: Discrete optimisation; Robust scheduling; Uncertainty budget; Mixed integer linear programming; Constraint programming (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725002620
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:326:y:2025:i:1:p:54-68

DOI: 10.1016/j.ejor.2025.04.012

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 ().