Scheduling with uncertain durations: Modeling β-robust scheduling with constraints

Many real-world scheduling problems are subject to change, and scheduling solutions should be robust to those changes. We consider a single-machine scheduling problem where the processing time of each activity is characterized by a normally distributed random variable, with flowtime as the main solution criterion. The objective is to find the beta-robust schedule-the schedule that minimizes the risk of the flowtime exceeding a threshold. We show how to represent this problem as a constraint model, explicitly representing the uncertainty and robustness as input parameters and objectives, and enabling the uncertainty to propagate using constraint propagation. Specifically, we develop three models (primal, dual and hybrid), and we show the effect of dominance rules on the search space. (c) 2008 Published by Elsevier Ltd.