| Article ID: | iaor19931957 |
| Country: | Singapore |
| Volume: | 9 |
| Issue: | 2 |
| Start Page Number: | 235 |
| End Page Number: | 238 |
| Publication Date: | Nov 1992 |
| Journal: | Asia-Pacific Journal of Operational Research |
| Authors: | Cheng T.C.E., Kahlbacher H.G. |
| Keywords: | combinatorial analysis |
In a recent paper, Cheng studied the problem of assigning a common due-date to a set of simultaneously available jobs and scheduling them on several parallel and identical machines to minimize the costs of due-date assignment, job earliness and tardiness. In this note, the authors present a proof that the problem is NP-hard and thus the use of heuristic solution methods can be justified.