Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms

This paper aims at minimizing the makespan for a batch-processing machine. The processing times and the sizes of the jobs are known. The machine can process a batch as long as its capacity is not exceeded. The processing time of a batch is the longest processing time of all the jobs in that batch. This problem is NP-hard and hence a genetic algorithm (GA) approach is proposed. Random instances were used to test the effectiveness of the proposed approach. The results obtained from GA were compared with a simulated annealing approach and a commercial solver. The results indicate that the GA was able to arrive at better makespan with shorter run times. (c) 2006 Elsevier B.V. All rights reserved.