Stochastic scheduling to minimize expected maximum lateness

Xianyi Wu, Xian Zhou*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

38 Citations (Scopus)

Abstract

This paper is concerned with the problems in scheduling a set of jobs associated with random due dates on a single machine so as to minimize the expected maximum lateness in stochastic environment. This is a difficult problem and few efforts have been reported on its solution in the literature. In this paper, we first derive a deterministic equivalent to the expected maximum lateness and then propose a dynamic programming algorithm to obtain the optimal solutions. The procedures to compute optimal solutions are initially developed in the case of deterministic processing times, and then extended to stochastic processing times following arbitrary probability distributions. Moreover, several heuristic rules are suggested to compute near-optimal solutions, which are shown to be highly efficient and accurate by computer-based experiments.

Original languageEnglish
Pages (from-to)103-115
Number of pages13
JournalEuropean Journal of Operational Research
Volume190
Issue number1
DOIs
Publication statusPublished - 1 Oct 2008
Externally publishedYes

Keywords

  • Due dates
  • Dynamic programming algorithms
  • Expected maximum lateness
  • Stochastic scheduling

Fingerprint

Dive into the research topics of 'Stochastic scheduling to minimize expected maximum lateness'. Together they form a unique fingerprint.

Cite this