Optimal assignment of due-dates for preemptive single-machine scheduling

Edwin Tai Chiu Cheng, V. S. Gordon

Research output: Journal article publicationJournal articleAcademic researchpeer-review

13 Citations (Scopus)


This paper considers due-date assignment and preemptive scheduling of n jobs in a single-machine shop under precedence constraints. Along with a release date, the job i has processing time piand a due-date diis assigned depending on pi. If di=k1pi+k2, the due-date assignment method is known as PPW: processing-time-plus-wait. If di=k1pk2i, it is known as TWK-power (total-work-content-power) due-date determination. The problem is to minimize an objective function depending on the assigned due-date parameters k1and k2, together with maximum tardiness penalty. It is shown that an O(n2) algorithm yields an optimal schedule. A simple analytical solution method is presented to find the optimal due-dates for a special case of the objective function and PPW due-date assignment method.
Original languageEnglish
Pages (from-to)33-40
Number of pages8
JournalMathematical and Computer Modelling
Issue number2
Publication statusPublished - 1 Jan 1994


  • Due-date assignment
  • Scheduling

ASJC Scopus subject areas

  • Modelling and Simulation
  • Computer Science Applications


Dive into the research topics of 'Optimal assignment of due-dates for preemptive single-machine scheduling'. Together they form a unique fingerprint.

Cite this