New challenges in scheduling theory

Excerpt

Machine scheduling traditionally is the study of the sequencing of tasks on a single or several parallel or dedicated machines, with possibly different characteristics, subject to a set of constraints. Constraints commonly capture the limited availability of resources, reflect precedence relations between tasks or generally express some restrictions of processing tasks over time. Beyond satisfaction of the constraints, there is generally the goal to optimize an objective as a criterion of the quality of the solution delivered by some search method. There is a vast literature on this area of study, and it has led to numerous sophisticated heuristics, approximate and exact algorithms. Many of these problems are computationally intractable, and problems have been classified by their varying degrees of complexity. …