A Robust Scheduling Approach for a Single Machine to Optimize a Risk Measure

Robustness in scheduling addresses the capability of devising schedules which are not sensitive – to a certain extent – to the disruptive effects of unexpected events. The paper presents a novel approach for protecting the quality of a schedule by taking into account the rare occurrence of very unfavourable events causing heavy losses. This calls for assessing the risk associated to the different scheduling decisions. In this paper we consider a stochastic scheduling problem with a set of jobs to be sequenced on a single machine. The release dates and processing times of the jobs are generally distributed independent random variables, while the due dates are deterministic. We present a branch-and-bound approach to minimize the Value-at-Risk of the distribution of the maximum lateness and demonstrate the viability of the approach through a series of computational experiments.