What question did this study set out to answer?

The aim is to review the complexity, algorithms, and properties of single machine scheduling problems.

January 6, 2026Algorithms0 citationsOpen Access

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

NVNodari VakhaniaUniversidad Autónoma del Estado de Morelos FWFrank WernerUniversity of Tehran KRKevin Johedan Ramírez-FuentesUniversidad Autónoma del Estado de Morelos

Key Points

The aim is to review the complexity, algorithms, and properties of single machine scheduling problems.
Analysed standard settings of single machine problems
Evaluated complexity and approximability
Reviewed existing heuristics and algorithms for scheduling
Identified polynomially solvable cases
Highlighted complexity issues in scheduling problems
Suggested areas for future research in single machine scheduling

Abstract

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.

问 AI

Bookmark

View Full Paper