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

Abdelghani Bekrar (1) , Imed Kacem (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

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.

Keywords: Strips; Heuristic algorithms; Filling; Approximation algorithms; Algorithm design and analysis; Approximation methods; Optimized production technology; Strip packing; guillotine cuts; heuristic

Domains: Computer Science [cs]; Operations Research [cs.RO]; Computer Science [cs]; Data Structures and Algorithms [cs.DS]

Abdelghani Bekrar, Imed Kacem. A comparison study of heuristics for solving the 2D guillotine strip and bin packing problems. 2008 International Conference on Service Systems and Service Management (ICSSSM 2008), Jun 2008, Melbourne, France. pp.1-6, ⟨10.1109/ICSSSM.2008.4598479⟩. ⟨hal-02476043⟩