On the minimization of the weighted number of tardy jobs with random processing times and deadline

The authors consider a stochastic scheduling problem where a set of jobs with random processing times are sequenced on a single machine in order to minimize the total weighted number of jobs which finish after an exponentially distributed common deadline. A simple sequencing rule is identified which minimizes the expected weighted number of tardy jobs. Sufficient conditions are determined for the existence of a sequence which stochastically minimizes the total weighted number of tardy jobs, and a sequencing rule is derived which stochastically minimizes the total number of tardy jobs. The equivalence of static and dynamic sequencing policies is shown for a large class of processing time distributions.