A survey on the cutting and packing problems
- PDF / 233,156 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 53 Downloads / 234 Views
A survey on the cutting and packing problems Loris Faina1 Received: 24 June 2020 / Accepted: 25 July 2020 © The Author(s) 2020
Abstract This paper presents a unified approach, based on a geometrical method (see Faina in Eur J Oper Res 114:542–556, 1999; Eur J Oper Res 126:340–354, 2000), which reduces the general two and three dimensional cutting and packing type problems to a finite enumeration scheme.
1 Introduction The cutting and packing problems (in short C & P problems) have a common logical structure that can be synthetized as follows. There are two groups of basic data, whose elements define geometric bodies in one or more dimensions: the stock of the so-called large objects, and the list of the so-called small items; the C & P processes realize patterns being geometric combinations of small items assigned to large objects. The residual pieces, that means figures occurring in patterns not belonging to small items, are usually treated as trim loss. The objective of most solution techniques is to minimize the wasted material. The strong relationship between the C & P problems results from the duality of a material body and the space occupied by it. Indeed, packing a list of boxes into a container is the same as cutting the space of the container, producing pieces of space where it is possible to place the boxes. On the other side, cutting a sheet of material in order to obtain smaller items is the same as packing the items into the sheet. The primordial study of the C & P problems seems to go back to Kantorovich [5] and Brook et al. [1]; but an extensive scientific work started only from the sixties. Since then, a great number of problems essentially of the same logical structure of the C & P problems have been appeared under different names in literature (see Dyckhoff [2] for an unified approach to the C & P type problems and Faina [3,4] for a wide discussion about the state of the research). The motivations for this wide shared interest is that the C & P type problems are present in various industries; the cutting problems arise, for example, with the production of steel bars
Al Prof. Domenico Candeloro, un matematico nel quale l’umilta, ` la competenza e la disponibilita` sono state coniugate in modo insolitamente armonioso.
B 1
Loris Faina [email protected] Dipartimento di Matematica ed Informatica, Via L. Vanvitelli 1, 06123 Perugia, Italy
123
L. Faina
and plates, paper, adhesive tape, glass, pipes, textile, etc. In all these cases, it is usually more economic to produce large objects in only a few stardard sizes at first and later cut them into the sizes requested by the customers, than produce the required sizes directly. The packing problems arise, for example, in the manufacturing and distribution industries. Indeed, all kind of goods are packaged in cartons for easy handling; cartons are then packed into a container for transportation and warehouse storage. The vast majority of the problems considered in literature are concerned with regular forms, expecially rectangular or block forms. Ir
Data Loading...
