A Parallel Genetic Algorithm for the Multilevel Unconstrained Lot-Sizing Problem

A coarse–grained parallel genetic algorithm (PGA) for the multilevel unconstrained lot–sizing problem (MLULSP) is described and evaluated using 176 benchmark problems from the literature, with problem sizes varying from 5 to 500 products and with simulations ranging from 12 to 52 periods. The parallelization approach consists of concurrently executing several subpopulations (demes) of a genetic algorithm with the occasional migration of individuals between them. The migration is controlled by the migration model of Cantú–Paz (2001). The genetic algorithm used is based on a new binary coding for the MLULSP. The PGA, which is the first application of a parallel metaheuristic to the MLULSP, is competitive with the best known solution methods. It was possible with the new method to calculate new best solutions for 34 of the benchmark problems. Furthermore, the migration enables a super–linear speedup. The results indicate that parallel genetic algorithms are suitable for solving large–problem instances of the MLULSP with acceptable computing times.