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

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

Slimane Abou-Msabah (University of Science and Technology Houari Boumedienne, Bab Ezzouar, Algeria), Ahmed-Riadh Baba-Ali (University of Science and Technology Houari Boumedienne, Bab Ezzouar, Algeria) and Basma Sager (University of Sciences and Technologies Houari Boumediene, Bab Ezzouar, Algeria)
DOI: 10.4018/IJCINI.2019100105

Abstract

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.
Article Preview
Top

Guillotine Placement Heuristics

A number of placement heuristics methods found in the literature informed the heuristic proposed to fit the case studied in this paper. This survey focuses on guillotinable heuristics.

The Floor-Ceiling (FC) approach introduced by Lodi, Martello, and Vigo (1999) separates items into two levels, starting from left to right at the bottom of the floor level . When no more items fit there, the approach places items from right to left at the top of the ceiling level. This new variant of the FC approach performs the cuttings from edge to edge, to check the guillotine constraint, as shown by the bold lines in Figure 1.

Ben Messaoud, Chu, and Espinouse (2004) modified the guillotine variant of the FC approach and proposed the Shelf Heuristic Filling approach (SHF) by injecting items placed in the ceiling, from right to left, on the top of the items below, as shown in Figure 2.

Msabah and Baba-Ali (2011) proposed a new guillotine placement approach based on levels and proposed exploiting intra-level residues while checking the guillotine constraint. In it, a item can be laid on the strip in three possible ways, as shown in Figure 3.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 14: 4 Issues (2020): 1 Released, 3 Forthcoming
Volume 13: 4 Issues (2019)
Volume 12: 4 Issues (2018)
Volume 11: 4 Issues (2017)
Volume 10: 4 Issues (2016)
Volume 9: 4 Issues (2015)
Volume 8: 4 Issues (2014)
Volume 7: 4 Issues (2013)
Volume 6: 4 Issues (2012)
Volume 5: 4 Issues (2011)
Volume 4: 4 Issues (2010)
Volume 3: 4 Issues (2009)
Volume 2: 4 Issues (2008)
Volume 1: 4 Issues (2007)
View Complete Journal Contents Listing