Anchor-robust single machine scheduling

This talk is about a two-stage robust scheduling problem. A set of non-preemptive jobs subject to precedence constraints and a common deadline are to be scheduled on a single machine. Job processing times are subject to budgeted uncertainty. The objective is to maximize the number of so-called anchored jobs whose starting time is guaranteed against any uncertainty realization. Several MIP formulations are proposed, some of which make use of problem-specific dominance properties. A Danzig-Wolfe reformulation is derived based on the same dominance properties. It is solved with column generation and branch-and-price using a specialized algorithm for the pricing subproblem. Numerical experiments compare the computing times and the quality of the dual bounds obtained.