Minimizing makespan on a single batch processing machine with non-identical job sizes using ant colony optimization

In this paper,two ant colony optimization(ACO) algorithms are proposed to minimize makespan for scheduling jobs with non-identical sizes on a single batch processing machine.Compared with the traditional ACO algorithm,we design new heuristic information based on utilization ratio and load balance ratio of a batch for this problem.In the first algorithm named JACO(ant colony optimization based a job sequence),the solution is coded as a job sequence which is corresponding to a solution of the problem based on BBF(Batch Best Fit) heuristic,and whose pheromone trail is associated with the sequence of jobs.In the second algorithm named BACO(ant colony optimization based a batch sequence),the solution is coded as a batch sequence which represents a solution of the problem.Its pheromone trail is associated with the extent that jobs are scheduled into the same batch.Computational results show that JACO and BACO significantly outperform other four algorithms addressed in literatures,which are SA(simulated annealing),GA(genetic algorithm),FFLPT(first-fit longest processing time) and BFLPT(best-fit longest processing time).Furthermore,BACO is better than JACO.These results show that BACO is an effective and efficient method for solving scheduling problems to minimize makespan on a single batch processing machine with non-identical job sizes.