Robust Predictive-Reactive Scheduling: An Information-Based Decision Tree Model

In this paper we introduce a proactive-reactive approach to deal with uncertain scheduling problems. The method constructs a robust decision tree for a decision maker that is reusable as long as the problem parameters remain in the uncertainty set. At each node of the tree we assume that the scheduler has access to some knowledge about the ongoing scenario, reducing the level of uncertainty and allowing the computation of less conservative solutions with robustness guarantees. However, obtaining information on the uncertain parameters can be costly and frequent rescheduling can be disturbing. We first formally define the robust decision tree and the information refining concepts in the context of uncertainty scenarios. Then we propose algorithms to build such a tree. Finally, focusing on a simple single machine scheduling problem, we provide experimental comparisons highlighting the potential of the decision tree approach compared with reactive algorithms for obtaining more robust solutions with fewer information updates and schedule changes.