*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
