Optimal sequences in stochastic single machine shops

This article addresses the problem of sequencing a given set of jobs with random processing times for uninterrupted processing on a single machine. The objective is to identify the ‘optimal’ sequence which minimizes the expected value of a ‘scheduler’s’ disutility (or cost) function with respect to a performance measure. The general problem is difficult to solve; however, special cases can be modeled and solved exactly when (1) processing times are statistically independent, (2) disutility functions for sequence evaluation are linear, exponential, or quadratic, and (3) performance measures are mean flow time, mean waiting time, or mean lateness. Illustrative examples demonstrate that the proposed models create sequences which are (a) influenced by both schedulers’ risk taking behavior and the stochasticity of processing times, and (b) more ‘realistic’ than those provided by the classical single machine models. This paper also extends the developed models to include multi-dimensional deterministic single machine problems.