Abstract
In real-life problems of cutting and packing very often placement constraints are present. For instance, defective regions of the raw material (wooden boards, steel plates, etc.) shall not become part of the desired products. More generally, due to different quality demands, some products may contain parts of lower quality which are not allowed for other goods. Within this work we consider one- and two-dimensional rectangular cutting and packing problems where items of given types have to be cut from (or packed on) raw material such that an objective function attains its maximum. In the one-dimensional (1D) case, we assume for each item type that allocation intervals (regions of the raw material) are given so that any item of the same type must be completely contained in one of the corresponding allocation intervals. In addition, we deal with problems where the lengths of the 1D items of a given type may vary within known tolerances. In the two-dimensional (2D) case, where rectangular items of different types have to be cut from a large rectangle, we investigate guillotine cutting under the condition that defective rectangular regions are not allowed to be part of the manufactured products (even not partially). For these scenarios we present solution strategies which rely on the branch and bound principle or on dynamic programming. Based on properties of the corresponding objective functions we discuss possibilities to reduce the computational complexity. This includes the definition of appropriate sets of potential allocation (cut) points which have to be inspected to obtain an optimal solution. By dominance considerations the set of allocation points is kept small. In particular, the computational complexity becomes independent of the unit of measure of the input data. Possible generalizations will be discussed as well.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Astrand, E., Rönnqvist, M.: Crosscut optimization of boards given complete defect information. For. Prod. J. 44, 15–24 (1994)
Beasley, J.E.: An exact two-dimensional non-guillotine cutting tree search procedure. Oper. Res. 33, 49–65 (1985)
Cintra, G.F., Miyazawa, F.K., Wakabayashi, Y., Xavier, E.C.: Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. Eur. J. Oper. Res. 191, 61–85 (2008)
Dowsland, K.A.: The three-dimensional pallet chart: An analysis of the factors affecting the set of feasible layouts for a class of two-dimensional packing problems. J. Oper. Res. Soc. 35, 895–905 (1984)
Gilmore, P.C., Gomory, R.E.: Multistage cutting stock problems of two and more dimensions. Oper. Res. 13, 94–120 (1965)
Hahn, S.G.: On the optimal cutting of defective sheets. Oper. Res. 16, 1100–1114 (1968)
Herz, J.C.: Recursive computational procedure for two-dimensional stock cutting. IBM J. Res. Dev. 16, 462–469 (1972)
Nicholson, T.A.J.: Finding the shortest route between two points in a network. Comp. J. 9, 275–280 (1966)
Rönnqvist, M.: A method for the cutting stock problem with different qualities. Eur. J. Oper. Res. 83, 57–68 (1995)
Rönnqvist, M., Astrand, E.: Integrated defect detection and optimization for cross cutting of wooden boards. Eur. J. Oper. Res. 108, 490–508 (1998)
Scheithauer, G.: The solution of packing problems with pieces of variable length and additional allocation constraints. Optimization 34, 81–96 (1995)
Scheithauer, G.: Zuschnitt- und Packungsoptimierung. Vieweg + Teubner, Wiesbaden (2008)
Scheithauer, G., Terno, J.: Guillotine cutting of defective boards. Optimization 19, 111–121 (1988)
Sweeney, P.E., Haessler, R.W.: One-dimensional cutting stock decisions for rolls with multiple quality grades. Eur. J. Oper. Res. 44, 224–231 (1990)
Sweeney, P.E., Paternoster, E.R.: Cutting and packing problems: A categorized application-oriented research bibliography. J. Oper. Res. Soc. 43, 691–706 (1992)
Terno, J., Lindemann, R., Scheithauer, G.: Zuschnittprobleme und ihre praktische Lösung. Harri Deutsch, Thun and Frankfurt/Main (1987)
Wäscher, G., Haußner, H., Schumann, H.: An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183, 1109–1130 (2007)
Acknowledgements
This work is supported in a part by the German Research Foundation (DFG) in the Collaborative Research Center 912 “Highly Adaptive Energy-Efficient Computing.”
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Fischer, A., Scheithauer, G. (2015). Cutting and Packing Problems with Placement Constraints. In: Fasano, G., Pintér, J. (eds) Optimized Packings with Applications. Springer Optimization and Its Applications, vol 105. Springer, Cham. https://doi.org/10.1007/978-3-319-18899-7_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-18899-7_6
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18898-0
Online ISBN: 978-3-319-18899-7
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)