¹National Chiao Tung University, Hsinchu, Taiwan

Correspondence: BMT Lin, Department of Information and Finance Management, Institute of Information Management, National Chiao Tung Univerisity, Hsinchu, Taiwan 300. E-mail: bmtlin@mail.nctu.edu.tw

Received 4 October 2005; Revised 8 March 2006; Accepted 15 March 2006; Published online 5 July 2006.

Abstract

This note presents complexity results for a single-machine scheduling problem of minimizing the number of late jobs. In the studied problem, the processing times of the jobs are defined by positional learning effects. A recent paper proposed a polynomial time algorithm for the case with a common due date and conjectured the general problem to be -hard. We confirm that the general problem is strongly -hard and show that the studied problem remains -hard even if there are only two different due-date values.