Makespan minimization on single batch‐processing machine via ant colony optimization

Makespan minimization on single batch‐processing machine via ant colony optimization

0.00 Avg rating0 Votes
Article ID: iaor20117142
Volume: 39
Issue: 3
Start Page Number: 582
End Page Number: 593
Publication Date: Mar 2012
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics: ant systems, manufacturing industries
Abstract:

This paper investigates the problem of minimizing makespan on a single batch‐processing machine, and the machine can process multiple jobs simultaneously. Each job is characterized by release time, processing time, and job size. We established a mixed integer programming model and proposed a valid lower bound for this problem. By introducing a definition of waste and idle space ( WIS equ1), this problem is proven to be equivalent to minimizing the WIS equ2 for the schedule. Since the problem is NP‐hard, we proposed a heuristic and an ant colony optimization (ACO) algorithm based on the theorems presented. A candidate list strategy and a new method to construct heuristic information were introduced for the ACO approach to achieve a satisfactory solution in a reasonable computational time. Through extensive computational experiments, appropriate ACO parameter values were chosen and the effectiveness of the proposed algorithms was evaluated by solution quality and run time. The results showed that the ACO algorithm combined with the candidate list was more robust and consistently outperformed genetic algorithm (GA), CPLEX, and the other two heuristics, especially for large job instances.

Reviews

Required fields are marked *. Your email address will not be published.