Study of the grid size impact on a raster based strip packing problem solution

摘要

Abstract: Cutting and packing (C&P) is an important area of operational research and its problems arise in various industries such as: textile, wood, glass and shipbuilding. The main objective is to maximize the efficiency of a layout by rearranging and/or reassigning items inside containers in order to reduce costs and environmental impact. In this work, a raster solution to the bidimensional irregular strip packing problem, which consists of placing irregular shapes items inside a single rectangular container with variable length, is studied. In raster methods, the selection of the grid size is very important to the outcome of the algorithm. It influences the size of the search space, the overlap algorithm efficiency, as well as the memory requirements of the packing algorithm. An analysis of the impact of the choice of grid size is performed using 15 benchmark cases from the literature and, through careful observation of such test results, a simple rule to define the grid size is suggested.