A Hybrid Imperialist Competitive Algorithm for the Flexible Job Shop Problem

摘要

Flexible job shop scheduling problem (FJSP) is one of the hardest combinatorial optimization problems known to be NP-hard. This paper proposes a novel hybrid imperialist competitive algorithm with simulated annealing (HICASA) for solving the FJSP. HICASA explores the search space by using imperial competitive algorithm (ICA) and use a simulated annealing (SA) algorithm for exploitation in the search space. In order to obtain reliable results from HICASA algorithm, a robust parameter design is applied. HICASA is compared with the widely-used genetic algorithm (GA) and the relatively new imperialist competitive algorithm (ICA). Experimental results suggest that HICASA algorithm is superior to GA and ICA on the FJSP.