Minimizing the expected weighted number of tardy jobs in stochastic flow shops (Q1096531)

Two stochastic scheduling models are considered: one with just a single machine, the other a flow shop consisting of an arbitrary number of machines. In both problem types, all jobs to be processed have due dates, and the objective is to find a job sequence that minimizes the expected weighted number of tardy jobs. For the single-machine case, sufficient optimality conditions for job sequences are derived for various choices of due date and processing time distributions. For the much harder case of a flow shop with an arbitrary number of machines and identically distributed due dates for all jobs, the following intuitively appealing results are proved: (i) when all jobs have the same processing time distributions, the expected weighted number of tardy jobs is minimized by sequencing the jobs in decreasing order of the weights, (ii) when all weights are equal, the jobs should be sequenced according to an increasing stochastic ordering of the processing time distributions. Extensive use is made of arguments based on pairwise interchanges.