A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families

We consider the problem of minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals. We propose a family of iterative improvement heuristics based on previous work by Potts and Uzsoy and combine them with a genetic algorithm (GA) based on the random keys encoding of Bean. Extensive computational experiments show that one of the proposed GAs runs significantly faster than the other, providing a good tradeoff between solution time and quality. The combination of iterative heuristics with GAs consistently outperforms the iterative heuristics on their own.