A new ant colony algorithm for makespan minimization in permutation flow shops

The problem of scheduling in permutation flow shop with the objective of minimizing the maximum completion time, or makespan, is considered. A new ant colony optimization algorithm is developed for solving the problem. A novel mechanism is employed in initializing the pheromone trails based on an initial sequence. Moreover, the pheromone trail intensities are limited between lower and upper bounds which change dynamically. When a complete sequence of jobs is constructed by an artificial ant, a local search is performed to improve the performance quality of the solution. The proposed ant colony algorithm is applied to Taillard’s benchmark problems. Computational experiments suggest that the algorithm yields better results than well-known ant colony optimization algorithms available in the literature.

► A new ACO-based algorithm is developed for the permutation flow shop scheduling problem with the makespan criterion.
► A novel mechanism is employed to initialize the pheromone trails.
► The pheromone trails are limited between lower and upper bounds dynamically modified.
► A local search is performed to improve the performance quality of each ant-sequence.
► In the proposed algorithm, the goal is always to guide the search towards the neighborhood around the best solution found.