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