Robust Optimization of Schedules Affected by Uncertain Events

R. Vujanic, P. J. Goulart and M. Morari

@article{VGM:2016a,
  author = {R. Vujanic and P. J. Goulart and M. Morari},
  title = {Robust Optimization of Schedules Affected by Uncertain Events},
  journal = {Journal of Optimization Theory and Applications},
  year = {2016},
  url = {http://link.springer.com/article/10.1007/s10957-016-0920-3},
  doi = {10.1007/s10957-016-0920-3}
}

In this paper we present a new method for finding robust solutions to mixed integer linear programs (MILPs) subject to uncertain events. We present a new modelling framework for such events, which results in uncertainty sets that depend parametrically on the decision taken. We also develop results that can be used to compute corresponding robust solutions. The usefulness of our proposed approach is illustrated by applying it in the context of a scheduling problem. For instance, we consider uncertainty on the decided start times of the tasks, or on which unit they are to be executed. Delays and unit outages are possible causes for such events, and they can be very common in practice. Through our approach, we can accommodate them without altering the remainder of the schedule. Furthermore, we include the optional possibility of recourse on the continuous part of the problem, that is we allow for the revision of some of the decisions once uncertainty is observed. This allows one to increase the performance of the robust solutions. The proposed scheme is also computationally favourable, since the optimization problem to be solved to obtain the robust solution is still an MILP (linearity is preserved) and the number of integer variables is not increased with respect to the nominal formulation. We finally apply the method to a concrete batch scheduling problem and discuss the effects of robustification in this case.