Abstract : Local Search metaheuristics are a recognized means of solving hard combinatorial
problems. Over the last couple of decades, significant advances have been
made in terms of the formalization, applicability and performance of these methods.
Key to the performance aspect is the increased availability of parallel hardware,
which turns out to be largely exploitable by this class of procedures. As the
real-life cases of combinatorial optimisation easily degrade into intractable territory
for exact or approximation algorithms, local search metaheuristics hold undeniable
interest. This situation is further compounded by the good adequacy exhibited by
this class of search procedures for large-scale parallel operation. In this chapter we
explore and discuss ways which lead to parallelization in Local Search.