A Controlled Stability Genetic Algorithm With the New BLF2G Guillotine Placement Heuristic for the Orthogonal Cutting-Stock Problem

摘要

The orthogonal cutting-stock problem tries to place a given set of items in a minimum number of identically sized bins. Combining the new BLF2G heuristic with an advanced genetic algorithm can help solve this problem with the guillotine constraint. According to the item order, the BLF2G heuristic creates a direct placement of items in bins to give a cutting format. The genetic algorithm exploits the search space to find the supposed optimal item order. Other methods try to guide the evolutionary process. A new enhancement guides the evolutionary process, enriching the population via qualified individuals, without disturbing the genetic phase. The evolution of the GA process is controlled, and when no improvements after some number of iterations are observed, a qualified individual is injected to the population to avoid premature convergence to a local optimum. A generated set of order-based individuals enriches the evolutionary process with qualified chromosomes. The proposed method is compared with other heuristics and metaheuristics found in the literature on existing data sets.