Complexity of parallel machine scheduling with processing-plus-wait due dates to minimize maximum absolute lateness

Edwin Tai Chiu Cheng, Mikhail Y. Kovalyov

Research output: Journal article publicationJournal articleAcademic researchpeer-review

11 Citations (Scopus)


We study the problem of scheduling n jobs on several parallel identical machines. An optimal combination of a job schedule and processing-plus-wait (PPW) due dates is to be determined so as to minimize the maximum absolute lateness. The problem is shown to be strongly NP-hard if the number of machines is variable and ordinary NP-hard if it is a constant greater than one. For the single machine case, the problem is shown to be solvable by a graphical approach in O(nlogn) time.
Original languageEnglish
Pages (from-to)403-410
Number of pages8
JournalEuropean Journal of Operational Research
Issue number2
Publication statusPublished - 16 Apr 1999


  • Due date assignment
  • Parallel machine scheduling

ASJC Scopus subject areas

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

Cite this