Grids for cutting and packing problems: a study in the 2D knapsack problem
- PDF / 1,020,307 Bytes
- 47 Pages / 439.37 x 666.142 pts Page_size
- 2 Downloads / 189 Views
Grids for cutting and packing problems: a study in the 2D knapsack problem Jéssica Gabriela de Almeida Cunha1 · Vinícius Loti de Lima1 · Thiago Alves de Queiroz1 Received: 18 March 2019 / Revised: 27 July 2019 © Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract Different grids of points to solve cutting and packing problems with rectangular shaped items are discussed in this work. The grids are the canonical dissections (also known as normal patterns), useful numbers, reduced raster points, regular normal patterns, and meet-in-the-middle patterns. Theoretical results involving the size and subset relations among the grids are proposed, besides practical procedures to reduce the size. Computational experiments are performed in which the two-dimensional (2D) knapsack problem is solved with an integer linear programming model. The results show the impact on the grids before and after applying the reduction procedures, concluding that the reduced raster points and meet-in-the-middle patterns are generally the grids with the smallest number of points. Keywords Grid of points · Reduction procedures · Canonical dissections · Reduced raster points · Meet-in-the-middle patterns · Two-dimensional knapsack problem Mathematics Subject Classification 90C27 Combinatorial optimization · 52C17 Packing and covering in n dimensions · 97M40 Operations research, economics
1 Introduction Cutting and packing problems have broad applicability in industry, aiming to reduce the costs related to manufacturing, logistics, and supply chain. Some examples are
B
Thiago Alves de Queiroz [email protected] Jéssica Gabriela de Almeida Cunha [email protected] Vinícius Loti de Lima [email protected]
1
Institute of Mathematics and Technology, Federal University of Goiás - Campus Catalão, Catalão, GO 75704-020, Brazil
123
J. G. d. A. Cunha et al.
the pallet loading problem (Scheithauer and Terno 1996; Alvarez-Valdes et al. 2005); cutting of leather in the automotive industry (Alves et al. 2012); container and truck loading problems (Junqueira et al. 2012); cutting of cloth in the textile industry (Valle et al. 2012); integrated scheduling problems (Martinovic et al. 2018); among others. Cutting and packing problems aim at, respectively, cutting items from stocks and packing items into bins, observing an objective function and respecting some constraints. In general, the objective function aims at maximizing or minimizing some criterion and the basic constraints are related to the non-overlapping of items and respect the limits of the bin (Wäscher et al. 2007). Cutting and packing terms are synonyms in terms of a theoretical point of view. Furthermore, the majority of these problems belong to the NP-hard class (Garey and Johnson 1979). While seeking for an optimal solution of cutting and packing problems of bars, rectangles or parallelepipeds, a natural approach is to consider the discretization of the bin. In the literature there are some strategies for discretizing the bin, in particular, canonical dissections from
Data Loading...
