Scatter Search Algorithms for Identical Parallel Machine Scheduling Problems

We address the Identical Parallel Machine Scheduling Problem, one of the most important basic problems in scheduling theory, and some generalizations of it arising from real world situations. We survey the current state of the art for the most performing metaheuristic algorithms for this class of problems, with special emphasis on recent results obtained through Scatter Search. We present insights in the development of this heuristic technique, and discuss the combinatorial difficulties of the problems through the analysis of extensive computational results.