Incorporating tabu search for local search into evolutionary algorithms to solve the job shop scheduling problem

Abstract

A new issue for combinatorial optimization problems is to incorporate local search into the framework of evolutionary algorithms, leading to hybrid evolutionary algorithms. With the hybrid approach, evolutionary algorithms are used to perform global exploration among population while other heuristic methods are used to perform local exploitation around chromosomes. Due to the complementary properties of evolutionary algorithms and conventional heuristics, the hybrid approach often outperforms either method operating alone. When designing hybrid evolutionary algorithm (HEA), a fundamental principle is to hybridize where possible. This paper aims at developing powerful HEA to find high quality sub-optimal solutions for the job shop scheduling problem through tabu search (TS), an advanced local search meta-heuristic. Experiments of such a hybrid algorithm are carried out on different benchmark. Analysis of the behavior of the algorithm sheds light on ways to further improvement and are discussed here.