OPTIMAL SEQUENCES IN STOCHASTIC SINGLE-MACHINE SHOPS

This article addresses the problem of sequencing a given set of jobs w ith random processing times for uninterrupted processing on a single m achine. The objective is to identify the ''optimal'' sequence which mi nimizes the expected value of a ''scheduler's'' disutility (or cost) f unction with respect to a performance measure. The general problem is difficult to solve; however, special cases can be modeled and solved e xactly when (1) processing times are statistically independent, (2) di sutility functions for sequence evaluation are linear, exponential, or quadratic, and (3) performance measures are mean flow time, mean wait ing time, or mean lateness. Illustrative examples demonstrate that the proposed models create sequences which are (a) influenced by both sch edulers' risk taking behavior and the stochasticity of processing time s, and (b) more ''realistic'' than those provided by the classical sin gle machine models. This paper also extends the developed models to in clude multi-dimensional deterministic single machine problems. Copyrig ht (C) 1996 Elsevier Science Ltd