FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
An Enhanced Genetic Algorithm with the BLF2G Guillotine Placement Heuristic for the Orthogonal Cutting-Stock Problem

Authors: Slimane Abou-Msabah, Ahmed Riadh Baba Ali and Basma SAGER

Paper Information

Title:An Enhanced Genetic Algorithm with the BLF2G Guillotine Placement Heuristic for the Orthogonal Cutting-Stock Problem
Authors:Slimane Abou-Msabah, Ahmed Riadh Baba Ali and Basma SAGER
Proceedings:RCRA Full papers
Editor: Marco Maratea
Keywords:Cutting and Packing, Guillotine Constraint, Genetic algorithms, Heuristics, premature convergence
Abstract:

ABSTRACT. The orthogonal cutting-stock problem tries to place a given set of items into a minimum number of identically sized bins. As a part of solving this problem with the guillotine constraint, the authors propose combining the new BLF2G, Bottom Left Fill 2 direction Guillotine, placement heuristic with an advanced genetic algorithm. According to the item order, the BLF2G routine 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 by introducing a greedy heuristic to the initial population to enhance the results. The authors propose enriching the population via qualified individuals, without disturbing the genetic phase, by introducing a new enhancement to guide the evolutionary process. 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. To enrich the evolutionary process with qualified chromosomes a set of order-based individuals are generated. Our method is compared with other heuristics and metaheuristics found in the literature on existing data sets.

Pages:1
Talk:Jul 13 12:06 (Session 86J: Logic)
Paper: