Ant colony optimization algorithm to parallel machine scheduling problem with setups

Abstract

This paper addresses the non-preemptive unrelated parallel machine scheduling problem with machine-dependent and job sequence-dependent setup times. All jobs are available at time zero, all times are deterministic, and the objective is to minimize the makespan. This is a NP-hard problem and in this paper, a two-stage ant colony optimization (ACO) algorithm is introduced and its performance is evaluated by comparing its solutions to the solutions of Tabu Search and an existing heuristic for the same problem. The results show that ACO outperformed the other algorithms.