Semi-Markov models for single-machine stochastic scheduling problems

A single machine is available to process a collection of stochastic jobs. A class of semi-Markov decision processes is introduced with a view to modelling such phenomena as machine breakdowns, restrictions on switching between jobs, deadlines and batch processing. The paper looks at the structure of optimal processing strategies and develops procedures for evaluating suboptimal strategies. For those instances where there is a non-empty partial ordering on the job set delimiting the set of possible processing strategies, the problem becomes exceedingly complex. In such cases the paper studies only the performance of strategies which are a fixed permutation of the job set.