Single-machine scheduling to stochastically minimize maximum lateness

Xiaoqiang Cai*, Liming Wang, Xian Zhou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


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 {ν iii )} has the same order as {ν iii +A 0)} for some sufficiently large A 0. Some related results are also discussed.

Original languageEnglish
Pages (from-to)293-301
Number of pages9
JournalJournal of Scheduling
Issue number4-5
Publication statusPublished - Oct 2007
Externally publishedYes


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


Dive into the research topics of 'Single-machine scheduling to stochastically minimize maximum lateness'. Together they form a unique fingerprint.

Cite this