A new guillotine placement heuristic combined with an improved genetic algorithm for the orthogonal cutting-stock problem

The orthogonal cutting-stock problem consists in finding an optimal arrangement of n items on identical dimension bins. Several placement heuristics are used to perform this task. In our article, we are interested in the orthogonal cutting problem, taking into account the guillotine and the orientation constraints. We propose a new placement heuristic inspired by the BLF routine, which tries to place the items in levels, to check the guillotine constraint, while exploiting intra-levels residues, in two directions, vertically, then horizontally. Our heuristic named BLF2G, will be combined with an improved genetic algorithm, to be compared with other heuristics and metaheuristics found in literature, on made and existing data sets.