Minimizing total tardiness on one machine is NP-Hard. Du, J. & Leung, J. Y. Mathematics of Operations Research, 15:483--495, 1990.
Minimizing total tardiness on one machine is NP-Hard [link]Paper  doi  bibtex   
@article{du_minimizing_1990,
	title = {Minimizing total tardiness on one machine is {NP}-{Hard}},
	volume = {15},
	issn = {0364-765X, 1526-5471},
	url = {http://mor.journal.informs.org/content/15/3/483},
	doi = {10.1287/moor.15.3.483},
	language = {en},
	urldate = {2012-10-02TZ},
	journal = {Mathematics of Operations Research},
	author = {Du, J. and Leung, J. Y.-T.},
	year = {1990},
	keywords = {NP-hard, due data, independent job, one machine, total tardiness},
	pages = {483--495}
}

Downloads: 0