[Scheduling Seminar] Laurent Houssin (ENAC, UT) Flow-shop and job-shop robust scheduling problems

Keywords: Discrete optimisation, Robust scheduling, Uncertainty budget, Constraint programming , Mixed integer linear programming We study different solution methods for two two-stage robust, multi-machine scheduling problems under uncertainty budget. Compact formulations of the problems are proposed and two decomposition approaches are presented: a logic 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. Organized by Zdenek Hanzalek (CTU in Prague), Michael Pinedo (New York University), and Guohua Wan (Shanghai Jiao Tong). Seminar's webpage: https://schedulingseminar.com/