A Performance Study for the Multi-objective Ant Colony Optimization Algorithms on the Job Shop Scheduling Problem

Abstract

Most of the research on job shop scheduling problem are conceerned with minimization of a single objective. However, the real world applications of job shop scheduling problems are involved in optimizing multiple objectives. Therefore, in recent years ant colony optimization algorithms have been proposed to solve job shop scheduling problems with multiple objectives. In this paper, some recent multi-objective ant colony optimization algorithms are reviewed and are applied to the job shop scheduling problem by considering two, three and four objectives. Also in this study, four criteria: makespan, mean flow time, mean tardiness and mean machine idle time are considered for simultaneous optimization. Two types of models are used by changing the number of ants in a colony and each multi-objective ant colony optimization algorithm is applied to sixteen benchmark problem instances of up to 20 jobs x 5 machines, for evaluating the performances of these algorithms. A detailed analysis is performed using the performance indicators, and the experimental results have shown that the performance of some multi-objective ant colony optimization algorithms depend on the number of objectives and the number of ants.