A Genetic Algorithm for the Problem of Scheduling on Batch Processing Machines

We consider the problem of minimizing the makespan on batch processing identical machines, subject to compatibility constraints, where two jobs are compatible if they can be processed simultaneously in a same batch. These constraints are modeled by an undirected graph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$G$</tex>, in which compatible jobs are represented by adjacent vertices. To solve the general case, we propose two heuristic approaches and genetic algorithm. Furthermore, computational experiments are carried out to measure the performance of the proposed methods.