Robust optimization of schedules affected by uncertain events

Journal article

In this paper, we present a new method for finding robust solutions to mixed-integer linear programs subject to uncertain events. We present a new modeling framework for such events that result 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 address uncertainty on the start times chosen for the tasks or on which unit they are to be executed. Delays and unit outages are possible causes for such events and can be very common in practice. Through our approach, we can accommodate them without altering the remainder of the schedule. We also allow for the inclusion 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 favorable since the robust optimization problem to be solved remains a mixed-integer linear program, 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.

Authors: Vujanic, R; Goulart, P; Morari, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer Verlag
• Journal: Journal of Optimization Theory and Applications
• Volume: 171
• Issue: 3
• Pages: 1033–1054
• Publication date: 2016-03-28
• Acceptance date: 2016-03-04
• DOI: 10.1007/s10957-016-0920-3
• EISSN: 1573-2878
• ISSN: 0022-3239
• Keywords: scheduling; robust optimization; mixed-integer optimization; uncertain events