Stochastic Scheduling with Release Dates and Due Dates

We consider stochastic scheduling problems in which the processing times of jobs are independent exponentially distributed random variables, the release dates are random variables with an arbitrary joint distribution, and the due dates are random variables with a joint distribution that satisfies certain conditions. Our development establishes simple policies that minimize such criteria as the expected weighted sum of completion times and the expected weighted number of late jobs. These results contrast markedly with the deterministic counterparts of these models for which no polynomial time algorithms are known.