An Enhanced Genetic Algorithm of the BLF2G Guillotine Placement Heuristic for the Orthogonal Cutting-Stock Problem

ABSTRACT. The orthogonal cutting-stock problem tries to place a given set of items in a minimum number of identically-sized bins. As part of solving this problem with guillotine constraint, we propose to combine the new BLF2G, Bottom Left Fill 2 direction Guillotine, placement heuristic with an advanced genetic algorithm. According to the items order, the BLF2G routine makes a direct placement of items on bins to give a cutting format. The genetic algorithm exploits the search space to find the supposed optimal items order. Other methods tires to guide the evolutionary process by introducing a greedy heuristics to the initial population to enhance the results. We propose to enrich the population by qualified individuals, without disturbing the genetic phase, by introducing a new enhancement to guide the evolutionary process. We control the evolution and when we observe that there are no improvements, after some iterations, we inject a qualified individual to the population to avoid premature convergence to a local optimum. We generate a set of order-based individuals, to enrich the evolutionary process. Our method is compared with other heuristics and metaheuristics found in literature on existing data sets.