MAKESPAN-RELATED CRITERIA FOR COMPARING SCHEDULES IN STOCHASTIC ENVIRONMENTS

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