## Abstract

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 _{0})} for some sufficiently large A _{0}. Some related results are also discussed.

Original language | English |
---|---|

Pages (from-to) | 293-301 |

Number of pages | 9 |

Journal | Journal of Scheduling |

Volume | 10 |

Issue number | 4-5 |

DOIs | |

Publication status | Published - Oct 2007 |

Externally published | Yes |

## Keywords

- Deterministic or stochastic processing times
- Maximum weighted lateness
- Random due dates
- Stochastic order
- Stochastic scheduling