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.
- Due date assignment
- Parallel machine scheduling
ASJC Scopus subject areas
- Modelling and Simulation
- Management Science and Operations Research
- Information Systems and Management