This report focuses on the challenging issue of designing exponential algorithms for scheduling problems. Despite a growing literature dealing with such algorithms for other combinatorial optimization problems, it is still a recent research area in scheduling theory and few results are known. An exponential algorithm solves optimaly an NP-hard optimization problem with a worst-case time, or space, complexity that can be established and, which is lower than the one of a brute-force search. By the way, an exponential algorithm provides information about the complexity in the worst-case of solving a given NP-hard problem. In this report, we provide a survey of the few results known on schduling problems as well as some techniques for deriving exponential algorithms. In a second part we focus on some basic scheduling problems for which we propose exponential algorithms.
