A Chaotic Ant Colony Optimization Method for Scheduling a Single Batch-processing Machine with Non-identical Job Sizes

摘要

The problem of minimizing makespan on a single batch-processing machine with non-identical job sizes is strongly NP-hard. This paper proposes an Ant Colony Optimization (ACO) algorithm with chaotic control to solve the problem. The Metropolis criterion is adopted to select the paths of ants to escape immature convergence. In order to improve the solutions of ACO, a chaotic optimizer is designed and integrated into ACO to reinforce the capacity of global optimization. Batch First Fit is introduced to decode the paths into feasible solutions of the problem. In the experiment, the instances of 24 levels are simulated and the results show that the proposed CACO outperforms Genetic Algorithm and Simulated Annealing on all the instances.