A two-stage Ant Colony Optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times

This paper addresses the non-preemptive unrelated parallel machine scheduling problem with machine-dependent and sequence-dependent setup times. All jobs are available at time zero, all times are deterministic, and the objective is to minimize the makespan. An Ant Colony Optimization (ACO) algorithm is introduced in this paper and is applied to this NP-hard problem; in particular, the proposed ACO tackles a special structure of the problem, where the ratio of the number of jobs to the number of machines is large (i.e., for a highly utilized set of machines). Its performance is evaluated by comparing its solutions to solutions obtained using Tabu Search and other existing heuristics for the same problem, namely the Partitioning Heuristic and Meta-RaPS. The results show that ACO outperformed the other algorithms.