In this talk, we review some of the more important contributions to local search for scheduling problems that have appeared during the past few years. These contributions may be noteworthy either because of their theoretical interest, or because a local search algorithm performs competitively in computational tests.

The theoretical discussion covers the performance of descent algorithms in terms of worst-case analysis and the time complexity of searching for a local optimum. Also, we discuss some methods that allow neighborhoods of exponential size to be searched in polynomial time.

The last part of the talk focuses on some of the more recent types of local search methods. Specifically, the potential for ant colony optimization, variable neighborhood search, multi-level local search, and other methods to produce competitive local search algorithms for scheduling problems is discussed.