An ant colony system for permutation flow-shop sequencing

Ant colony system (ACS) is a novel meta-heuristic inspired by the foraging behavior of real ant. This paper is the first to apply ACS for the n/m/P/Cmax problem, an NP-hard sequencing problem which is used to find a processing order of n different jobs to be processed on m machines in the same sequence with minimizing the makespan. To verify the developed ACS algorithm, computational experiments are conducted on the well-known benchmark problem set of Taillard. The ACS algorithm is compared with the meta-heuristics such as genetic algorithms, simulated annealing, and neighborhood search from the literature. Computational results demonstrate that ACS is a more effective meta-heuristic for the n/m/P/Cmax problem.