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