Expectation-variance analysis of job sequences under processing time uncertainty

Uncertainty about job processing times in quite common in scheduling practice. However, uncertainty is totally assumed away in deterministic scheduling models, which constitute the bulk of the scheduling literature. In stochastic scheduling models, while uncertainty receives explicit consideration, the focus is almost exclusively on the optimization of a performance measure in expectation alone. Such a focus, unfortunately, does not reflect a scheduler’s risk attitude; to properly account for risk, the focus should shift towards the maximization of the scheduler’s expected utility. This calls for the identification of job sequences that are optimal or efficient with respect to the entire probatility distribution of the performance measure or a specific set of parameters of that distribution. In this paper, the authors discuss the issue of optimality and efficiency of job sequences in the context of the well studied flow-time problem. They focus on the identification of expectation-variance efficient sequences; the notion of expectation-variance efficiency incorporates risk and is widely used in other areas such as financial analysis. The authors present solution algorithms for the single machine flow-time problem and show how these algorithms apply as well to extensions involving job weights, precedence relations, and multiple machines.