In two-stage robust optimization, anchoring consists of fixing some part of the second-stage solution before observing the realization of the uncertain parameters. In the first stage, in addition to the classical first-stage decisions, one must decide the set of second-stage decisions that are anchored, together with a value assigned to those decisions that guarantees feasibility in any uncertainty realization. In this talk, we study an anchor-robust scheduling problem, where 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 anchored jobs whose starting time is guaranteed against any uncertainty realization. We show that the problem can be reduced to a static robust problem by making use of problem-specific dominance properties. Several MIP formulations are proposed, including a Dantzig-Wolfe reformulation and a bilinear formulation inspired by the work of [Büsing, Gersing and Koster, 2023]. We modify the spatial branch-and-bound algorithm proposed therein to obtain an efficient exact solution method. Numerical experiments compare the solution times and the quality of the dual bounds obtained.

This is a joint work with L. Brunod and P. Bendotti (EDF), and Ph. Chrétienne and B. Escoffier (LIP6)

Boris Detienne is an associate professor of operations research at the Institut de Mathématiques de Bordeaux (IMB), University of Bordeaux, France. He is also a member of the Inria project-team Edge. He received his PhD in information technology from the Université de Technologie de Compiègne. His research focuses on decomposition methods for integer programming and on optimization under uncertainty, including robust and stochastic optimization, with applications to planning and energy.