A comparison study of heuristics for solving the 2D guillotine strip and bin packing problems

Abstract : In this paper we consider the two dimensional strip and bin packing problem with guillotine cuts. The problem consists in packing a set of rectangular items on one strip of width W and infinite height or in bins of width W and height H. The items packed without overlapping, must be extracted by a series of cuts that go from one edge to the opposite edge (guillotine constraint). To solve this problem, we proposed tow heuristics, BSHF (best shelf heuristic filling) and NSHF (non-shelf heuristic filling). We compare the two heuristics with other heuristics from the literature. Computational results show that the two algorithms are complementary and they outperform the other algorithms in most of the instances.