Complexity results for single-machine scheduling with positional learning effects

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.

Keywords:

• single-machine scheduling
• learning effect
• late job
• 𝒩𝒫-hardness

Acknowledgements

I thank Professor Gur Mosheiov for introducing the studied problem and two anonymous referees for pinpointing some typos and unclarified points in an earlier version of this paper. The author is partially supported by a Taiwan-Russia joint project under grant NSC-94-2416-H-009-013 (Taiwan) and RP05H01 (05-06-90606-HHCa, Russia).