ALCOMFT-TR-02-83

Marjan van den Akker and Han Hoogeveen
Minimizing the number of late jobs in case of stochastic processing times
Utrecht. Work package 3. May 2002.

Abstract: We consider the single-machine scheduling problem of minimizing the number of late jobs. We first review and reinterpret the famous algorithm by Moore and Hodgson for the case of deterministic processing times as a dynamic programming algorithm. We then look at four problem classes with stochastic processing times. The first one has processing times that consist of a deterministic part and a random component that is independently, identically distributed for each job. The jobs in the other three classes have processing times that follow: (i) A gamma distribution with parameters alpha_j and beta, where beta is common to all jobs; (ii) A negative binomial distribution with parameters s_j and p, where p is the same for each job; (iii) A normal distribution with parameters mu_j and \sigma²_j. In this scheduling environment, the completion times will be stochastic variables as well; under these circumstances, we qualify a job as being on time if the probability that it is completed by the deterministic due date is at least equal to a certain given minimum success probability. We show that for the first, second, and third class of instances the problem can be solved in O(n log n) time, where we need the additional assumption of equal minimum success probabilities in the first case. For the case with normally distributed processing times we present a pseudo-polynomial time algorithm, and we prove that this is the best we can hope for by establishing weak NP-hardness. We also show that the problem of minimizing the weighted number of late jobs can be solved by an extension of the dynamic programming algorithm in all four cases; this takes pseudo-polynomial time. We further indicate how the problem of maximizing the expected number of on time jobs (with respect to the standard definition) can be tackled if we add the constraint that the on time jobs are sequenced in order of nondecreasing due dates.

\medskip\noindent Keywords. Scheduling, sequencing, single machine, number of late jobs, stochastic processing times, minimum success probability, dynamic programming, \cal NP-hardness.

Postscript file: ALCOMFT-TR-02-83.ps.gz (110 kb).