Evolutionary algorithms (EAs) offer a robust approach to problem solving. EAs are extremely flexible and can be extended by incorporating alternative approaches to favour he search process. One way is to hybridize an evolutionary algorithm with standard local search procedures [10,11], such as hill climbing [12], simulated annealing [15] and tabu search [4]. Individual solutions can be improved using local techniques and then placed back in competition with other members of the population. The hybrid approach complements the properties of evolutionary algorithm and local search heuristic methods. An evolutionary algorithm is used to perform global search to escape from local optima, while local search is used to conduct fine-tuning.