Abstract: A Multi Construction Ant Colony Optimization Algorithm for Permutation Flow Shop Scheduling was proposed. In this algorithm, solutions are constructed through two modes, which are based on Nawaz-Enscore-Ham heuristics and Rajendran heuristics respectively. Then the proportion of construction modes is adjusted adaptively according to quality of solution constructed. Simulation results and comparisons based on benchmarks demonstrate the effectiveness of the algorithm.

Key words: Permutation flow shop scheduling, Multi construction ant colony optimization, NEH heuristics, Rajendran heuristics