%0 Journal Article
%T Phi-Functions for 2D Objects Formed by Line Segments and Circular Arcs
%A N. Chernov
%A Yu. Stoyan
%A T. Romanova
%A A. Pankratov
%J Advances in Operations Research
%D 2012
%I Hindawi Publishing Corporation
%R 10.1155/2012/346358
%X 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¨C3]. 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
%U http://www.hindawi.com/journals/aor/2012/346358/