Optimal assignment of slack due-dates and sequencing of jobs with random processing times on a single machine

Research output: Journal article publicationJournal articleAcademic researchpeer-review

29 Citations (Scopus)


This paper considers the problem of due-date assignment and sequencing of n stochastically independent jobs with random processing times on a single machine. The objective is to find the optimal due-dates, under the slack due-date assignment method, and the optimal job sequence that jointly minimize the expected total cost. This cost is a function of the length of the assigned due-dates and the deviations of job completion times from the due-dates. It is shown that the optimal due-dates can be analytically determined. An efficient algorithm of the order O(n log n) is developed to find the optimal job sequence under mild conditions. It is also shown that, with further suitable and reasonable assumptions, the job sequence in the shortest expected processing time order is optimal.
Original languageEnglish
Pages (from-to)348-353
Number of pages6
JournalEuropean Journal of Operational Research
Issue number3
Publication statusPublished - 15 Apr 1991
Externally publishedYes


  • due-date assignment
  • Scheduling
  • sequencing

ASJC Scopus subject areas

  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this