An adaptive robust optimization model for parallel machine scheduling

Real-life parallel machine scheduling problems can be characterized by: (i) limited information about the exact task duration at the scheduling time, and (ii) an opportunity to reschedule the remaining tasks each time a task processing is completed and a machine becomes idle. Robust optimization is the natural methodology to cope with the first characteristic of duration uncertainty, yet the existing literature on robust scheduling does not explicitly consider the second characteristic the possibility to adjust decisions as more information about the tasks duration becomes available, despite that re-optimizing the schedule every time new information emerges is standard practice. In this paper, we develop an adaptive robust optimization scheduling approach that takes into account, at the beginning of the planning horizon, the possibility that scheduling decisions can be adjusted. We demonstrate that the suggested approach can lead to better here-and-now decisions and better makespan guarantees. To that end, we develop the first mixed integer linear programming model for adaptive robust scheduling, and a two-stage approximation heuristic, where we minimize the worst-case makespan. Using this model, we show via a numerical study that adaptive scheduling leads to solutions with better and more stable makespan realizations compared to static approaches.(c) 2022 Elsevier B.V. All rights reserved.

Automated summary

Real-life parallel machine scheduling problems have limited information about task duration at scheduling time and allow rescheduling of tasks when a machine becomes idle. This paper proposes an adaptive robust optimization scheduling approach that considers the possibility of adjusting scheduling decisions based on new information. The approach leads to better immediate decisions and improved makespan guarantees. A mixed integer linear programming model and a two-stage approximation heuristic are developed to minimize the worst-case makespan. Numerical study results show that adaptive scheduling achieves solutions with better and more stable makespan realizations compared to static approaches.