Single-machine scheduling to stochastically minimize maximum lateness

We study the problem of scheduling a set of jobs on a single machine, to minimize the maximum lateness ML or the maximum weighted lateness MWL under stochastic order. The processing time P _i , the due date D _i , and the weight W _i of each job i may all be random variables. We obtain the optimal sequences in the following situations: (i) For ML, the {P _i } can be likelihood-ratio ordered, the {D _i } can be hazard-rate ordered, and the orders are agreeable; (ii) For MWL, {D _i } are exponentially distributed, {P _i } and {W _i } can be likelihood-ratio ordered and the orders are agreeable with the rates of {D _i }; and (iii) For ML, P _i and D _i are exponentially distributed with rates μ _i and ν _i , respectively, and the sequence {ν _i (ν _i +μ _i )} has the same order as {ν _i (ν _i +μ _i +A ₀)} for some sufficiently large A ₀. Some related results are also discussed. This work was partially supported by the Research Grants Council of Hong Kong under Earmarked Grants No. PolyU 5146/02E, CUHK 4170/03E, and NSFC Research Funds No. 70329001, 70518002.