Speaker: Prof. Roel Leus，KU Leuven
Inviter: 王长军副研究员
Title: A Flow-Based Formulation for Parallel Machine Scheduling Using Decision Diagrams
Language: English
Time & Venue: 2024.4.19 14:00-15:00 数学院南楼N620
Abstract: We present a new flow-based formulation for identical parallel machine scheduling with a regular objective function and without idle time. The formulation is constructed with the help of a decision diagram that represents all job sequences that respect specific ordering rules. These rules rely on a partition of the planning horizon into, generally non-uniform, periods and do not exclude all optimal solutions, but they constrain solutions to adhere to a canonical form. The new formulation has numerous variables and constraints, and hence we apply a Dantzig-Wolfe decomposition in order to compute the linear programming relaxation in reasonable time; the resulting lower bound is stronger than the bound from the classical time-indexed formulation. We develop a branch-and-price framework that solves several instances from the literature for the first time. We compare the new formulation with the time-indexed and arc-time-indexed formulation by means of a series of computational experiments.