2005/01/01 by Han Hoogeveen, Hoogeveen, Han, Marjan van den Akker +1
Engineering · Computer Science · #Scheduling and Optimization Algorithms #Optimization and Search Problems #Distributed and Parallel Computing Systems
paper · doi:10.4230/dagsemproc.05031.12
We consider the single-machine scheduling problem of minimizing the number of late jobs. This problem is well-studied and well-understood in case of deterministic processing times. We consider the problem with stochastic processing times, and we show that for a number of probability distributions the problem can be reformulated as a deterministic problem (and solved by the corresponding algorithm) when we use the concept of minimum success probabilities, which is, that we require that the probability that a job complete on time is `big enough'. We further show that we can extend our approach to the case of machines with stochastic output.