Minimizing the number of late jobs in a stochastic setting using a chance constraint

We consider the single-machine scheduling problem of minimizing the number of late jobs. We omit here one of the standard assumptions in scheduling theory, which is that the processing times are deterministic. In this scheduling environment, the completion times will be stochastic variables as well. Instead of looking at the expected number of on time jobs, we present a new model to deal with the stochastic completion times, which is based on using a chance constraint to define whether a job is on time or late: a job is 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 have studied this problem for four classes of stochastic processing times. The jobs in the first three classes have processing times that follow: (i) A gamma distribution with shape parameter pj and scale parameter β, where β is common to all jobs; (ii) A negative binomial distribution with parameters pj and r, where r is the same for each job; (iii) A normal distribution with parameters pj and σj². The jobs in the fourth class have equally disturbed processing times, that is, the processing times consist of a deterministic part and a random component that is independently, identically distributed for each job.