An improved ant colony optimization for scheduling identical parallel batching machines with arbitrary job sizes

In this paper we consider the problem of scheduling parallel batching machines with jobs of arbitrary sizes. The machines have identical capacity of size and processing velocity. The jobs are processed in batches given that the total size of jobs in a batch cannot exceed the machine capacity. Once a batch starts processing, no interruption is allowed until all the jobs are completed. First we present a mixed integer programming model of the problem. We show the computational complexity of the problem and optimality properties. Then we propose a novel ant colony optimization method where the Metropolis Criterion is used to select the paths of ants to overcome the immature convergence. Finally, we generate different scales of instances to test the performance. The computational results show the effectiveness of the algorithm, especially for large-scale instances.

Figure optionsDownload as PowerPoint slideHighlight
► We introduce the problem of scheduling parallel batching machines with arbitrary job sizes, which is motivated by industrial applications.
► We show properties of optimal solutions and feasible solutions.
► A modified ant colony optimization integrated with heuristic rules is proposed for minimizing makespan.
► We conduct extensive experiments and compare the performance of the proposed algorithm with other algorithms in current literature.