Makespan-related criteria for comparing schedules in stochastic environments

The ultimate goal of stochastic modelling in shop scheduling is to select the sequence with the best statistical distribution and use it to book capacity and quote delivery dates. For tractability reasons, stochastic models usually employ the expected value of the makespan as the criterion (instead of really looking at the whole distribution). In practice, this criterion is much harder to satisfy than solving for the (already strongly NP-hard) deterministic makespan. Therefore, other criteria have been proposed, and it is important to ask which one is best for long-term expected benefits. This paper analyses and compares several existing criteria for that purpose. We also suggest adding a variance minimisation objective, so that the quoted lead time required to satisfy a given service level will be minimised.