Article ID: | iaor1991247 |
Country: | United States |
Volume: | 15 |
Start Page Number: | 483 |
End Page Number: | 495 |
Publication Date: | Nov 1990 |
Journal: | Mathematics of Operations Research |
Authors: | Leung Joseph Y.-T., Du Jianzhong |
Keywords: | scheduling |
The problem of minimizing the total tardiness for a set of independent jobs on one machine is considered. Lawler has given a pseudo-polynomial-time algorithm to solve this problem. In spite of extensive research efforts for more than a decade, the question of whether it can be solved in polynomial time or it is NP-hard (in the ordinary sense) remained open. In this paper the problem is shown to be NP-hard (in the ordinary sense).