Minimizing total tardiness on one machine is NP-hard

Minimizing total tardiness on one machine is NP-hard

0.00 Avg rating0 Votes
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: ,
Keywords: scheduling
Abstract:

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).

Reviews

Required fields are marked *. Your email address will not be published.