We study the cutting and packing (C&P) problems in two dimensions by using phi-functions. Our phi-functions describe the layout of given objects; they allow us to construct a mathematical model in which C&P problems become constrained optimization problems. Here we define (for the first time) a complete class of basic phi-functions which allow us to derive phi-functions for all 2D objects that are formed by linear segments and circular arcs. Our phi-functions support translations and rotations of objects. In order to deal with restrictions on minimal or maximal distances between objects, we also propose adjusted phi-functions. Our phi-functions are expressed by simple linear and quadratic formulas without radicals. The use of radical-free phi-functions allows us to increase efficiency of optimization algorithms. We include several model examples. 1. Introduction We study the cutting and packing (C&P) problems. Its basic goal is to place given objects into a container in an optimal manner. For example, in garment industry one cuts figures of specified shapes from a strip of textile, and one naturally wants to minimize waste. Similar tasks arise in metal cutting, furniture making, glass industry, shoe manufacturing, and so forth. In shipping works one commonly needs to place given objects into a container of a smallest size or volume to reduce the space used or increase the number of objects transported. The C&P problem can be formally stated as follows: place a set of given objects into a container so that a certain objective function (measuring the “quality” of placement) will reach its extreme value. In some applications (as in garment industry) objects must be specifically oriented respecting the structure of the textile, that is, they can only be translated without turnings (or only slightly rotated within given limits). In other applications objects can be freely rotated. Some applications involve additional restrictions on the minimal or maximal distances between certain objects or from objects to the walls of the container (one example is packing of radioactive waste). While most researchers use heuristics for solving C&P problems, some develop systematic approaches based on mathematical modeling and general optimization procedures; see, for example, [1–3]. We refer the reader to recent tutorials [4, 5] presenting the history of the C&P problem and basic techniques for its solution. Standard existing algorithms are restricted to 2D objects of polygonal shapes; other shapes are simply approximated by polygons (a notable exception is [6] which also
References
[1]
E. G. Birgin, J. M. Martínez, F. H. Nishihara, and D. P. Ronconi, “Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization,” Computers & Operations Research, vol. 33, no. 12, pp. 3535–3548, 2006.
[2]
A. M. Gomes and J. F. Oliveira, “Solving irregular strip packing problems by hybridising simulated annealing and linear programming,” European Journal of Operational Research, vol. 171, pp. 811–829, 2006.
[3]
V. J. Milenkovic and K. Daniels, “Translational polygon containment and minimal enclosure using mathematical programming,” International Transactions in Operational Research, vol. 6, no. 5, pp. 525–554, 1999.
[4]
J. A. Bennell and J. F. Oliveira, “The geometry of nesting problems: a tutorial,” European Journal of Operational Research, vol. 184, no. 2, pp. 397–415, 2008.
[5]
G. W？scher, H. Hau？ner, and H. Schumann, “An improved typology of cutting and packing problems,” European Journal of Operational Research, vol. 183, pp. 1109–1130, 2007.
[6]
E. Burke, R. Hellier, G. Kendall, and G. Whitwell, “A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem,” Operations Research, vol. 54, no. 3, pp. 587–601, 2006.
[7]
V. Milenkovic and E. Sacks, “Two approximate Minkowski sum algorithms,” International Journal of Computational Geometry & Applications, vol. 20, no. 4, pp. 485–509, 2010.
[8]
V. J. Milenkovic, “Rotational polygon overlap minimization and compaction,” Computational Geometry, vol. 10, no. 4, pp. 305–318, 1998.
[9]
V. J. Milenkovic, “Rotational polygon containment and minimum enclosure using only robust 2D constructions,” Computational Geometry, vol. 13, no. 1, pp. 3–19, 1999.
[10]
E. Burke, R. Hellier, G. Kendall, and G. Whitwell, “Irregular packing using the line and arc no-fit polygon,” Operations Research, vol. 58, pp. 948–970, 2010.
[11]
J. Bennell, G. Scheithauer, Y. Stoyan, and T. Romanova, “Tools of mathematical modeling of arbitrary object packing problems,” Annals of Operations Research, vol. 179, pp. 343–368, 2010.
[12]
Y. Stoyan, G. Scheithauer, N. Gil, and T. Romanova, “Φ-functions for complex 2D-objects,” 4OR. Quarterly Journal of the Belgian, French and Italian Operations Research Societies, vol. 2, no. 1, pp. 69–84, 2004.
[13]
Yu. Stoyan, J. Terno, G. Scheithauer, N. Gil, and T. Romanova, “Phi-functions for primary 2D-objects,” Studia Informatica Universalis, vol. 2, pp. 1–32.
[14]
N. Chernov, Yu. Stoyan, and T. Romanova, “Mathematical model and efficient algorithms for object packing problem,” Computational Geometry, vol. 43, no. 5, pp. 535–553, 2010.
[15]
Y. G. Stoyan and A. Chugay, “Packing cylinders and rectangular parallelepipeds with distances between them,” European Journal of Operational Research, vol. 197, pp. 446–455, 2008.
[16]
T. Romanova, G. Scheithauer, and A. Krivulya, “Covering a polygonal region by rectangles,” Computational Optimization and Applications, vol. 48, no. 3, pp. 675–695, 2011.
[17]
http://www.math.uab.edu/~chernov/CP/.
[18]
A. W？chter and L. T. Biegler, “On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming,” Mathematical Programming, vol. 106, no. 1, pp. 25–57, 2006.
[19]
H. Minkovski, “Dichteste gitterf？rmige Lagerung kongruenter K？rper,” Nachrichten von der Gesellschaft der Wissenschaften zu G？ttingen, pp. 311–355, 1904.
