Single Machine Scheduling Problems: Standard Settings and Properties, Polynomially Solvable Cases, Complexity and Approximability

Since the publication of the first scheduling paper in 1954, a huge number of works dealing with different types of single machine problems have appeared. They addressed many heuristics and enumerative procedures, complexity results or structural properties of certain problems. Regarding surveys, often particular subjects like special objective functions were discussed or more general scheduling problems were surveyed, in which a substantial part was devoted to single machine problems. In this paper, we focus on standard settings, basic structural properties of these settings, polynomial algorithms and complexity and approximation issues, which have not been reviewed so far, and suggest some future work in this area.