A typology of cutting and packing problems. (English) Zbl 0684.90076

Summary: Cutting and packing problems appear under various names in literature, e.g. cutting stock or trim loss problem, bin or strip packing problem, vehicle, pallet or container loading problem, nesting problem, knapsack problem etc. The paper develops a consistent and systematic approach for a comprehensive typology integrating the various kinds of problems. The typology is founded on the basic logical structure of cutting and packing problems. The purpose is to unify the different use of notions in the literature and to concentrate further research on special types of problems.


90C27 Combinatorial optimization
90C10 Integer programming
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C90 Applications of mathematical programming
Full Text: DOI


[1] Berkey, J. O.; Wang, P. Y., Two-dimensional finite bin-packing algorithms, Journal of the Operational Society, 38, 423-429 (1985) · Zbl 0611.90079
[2] Brooks, R. L.; Smith, C. A.B.; Stone, A. H.; Tutte, W. T., The dissection of rectangles into squares, Duke Mathematical Journal, 7, 312-340 (1940) · Zbl 0024.16501
[3] Brown, A. R., Optimum Packing and Depletion: The Computer in Space- and Resource-Usage Problems (1971), New York, London · Zbl 0268.90034
[4] Coffman, E. G.; Garey, M. R.; Johnson, D. S., An application of bin-packing to multiprocessor scheduling, SIAM Computing, 7, 1-17 (1978) · Zbl 0374.68032
[5] Coffman, E. G.; Garey, M. R.; Johnson, D. S., Approximation algorithms for bin-packing—An updated survey, (Ausiello, G.; etal., Approximation Algorithms for Computer System Design (1984), Wien), 49-106 · Zbl 0558.68062
[6] Dantzig, G. B., Discrete-variable extremum problems, Operations Research, 5, 266-277 (1957) · Zbl 1414.90353
[7] Dowsland, W. B., Two and three dimensional packing problems and solution methods, New Zealand Journal of Operational Research, 13, 1-18 (1985) · Zbl 0588.90061
[8] Dudzinski, K.; Walukiewicz, S., Exact methods for the knapsack problem and its generalizations, European Journal of Operational Research, 28, 3-21 (1987) · Zbl 0603.90097
[9] Dyckhoff, H., Production theoretic foundation of cutting and related processes, (Fandel, G.; etal., Essays on Production Theory and Planning (1988)), 151-180, Berlin
[10] Dyckhoff, H., Bridges between two principal model formulations for cutting stock processes, (Paper for the Workshop on Production Management in Pecs. Paper for the Workshop on Production Management in Pecs, (Hungary), September 6-9, 1988 (1989)), 40-51
[11] Dyckhoff, H.; Kruse, H.-J.; Abel, D.; Gal, T., Trim loss and related problems, Omega, 13, 59-72 (1985)
[12] Dyckhoff, H.; Finke, U.; Kruse, H.-J., Standard software for cutting stock management, (Fandel, G.; etal., Essays on Production Theory and Planning (1988)), 209-221, Berlin
[13] Eilon, S.; Christofides, N., The loading problem, Management Science, 17, 259-268 (1971) · Zbl 0208.45701
[14] Farley, A. A., Practical adaptations of the Gilmore-Gomory approach to cutting stock problems, Operations Research-Spektrum, 10, 113-123 (1988) · Zbl 0642.90050
[15] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), San Francisco, CA · Zbl 0411.68039
[16] Garey, M. R.; Johnson, D. S., Approximation algorithms for bin packing problems: A survey, (Ausiello, D.; Lucertini, M., Analysis and Design of Algorithms in Combinatorial Optimization, CISM Coursses and Lectures 266 (1981)), 147-172, Wien
[17] Gehring, H.; Menschner, M.; Meyer, M., A computer-based heuristic for packing pooled shipment containers (1990), EJOR—This issue · Zbl 0684.90084
[18] Gilmore, P. C., Cutting stock, linear programming, knapsacking, dynamic programming and integer programming: Some interconnections, Annals of Discrete Mathematics, 4, 217-235 (1979) · Zbl 0409.90062
[19] Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting-stock problem, Operations Research, 9, 849-859 (1961) · Zbl 0096.35501
[20] Golden, B. L., AIIE Transactions, 8, 265-274 (1976)
[21] Haessler, R. W., A heuristic programming solution to a nonlinear cutting stock problem, Management Science, 17B, 793-802 (1971) · Zbl 0219.90021
[22] Haessler, R. W.; Talbot, F. B., Load planning for shipments of low density products (1990), EJOR—This issue · Zbl 0684.90085
[23] Heicken, K.; König, W., Integration eines heuristisch-optimierenden Verfahrens zu Lösung eines eindimensionalen Verschnittproblems in einem EDV-gestützten Produktionsplanungs- und -steuerungssystem, Operations Research-Spektrum, 1, 251-259 (1980)
[24] Hinxman, A. I., The trim loss and assortment problems: A survey, European Journal of Operational Research, 5, 8-18 (1980) · Zbl 0442.90072
[25] Israni, S.; Sanders, J. L., Two-dimensional cutting stock problem research: A review and a new rectangular layout algorithm, Journal of Manufacturing Systems, 1, 169-182 (1982)
[26] Israni, S.; Sanders, J. L., Performance testing of rectangular parts-nesting heuristics, International Journal of Production Research, 23, 437-456 (1985) · Zbl 0571.90029
[27] Kantorovich, L. V., Mathematical methods of organizing and planning production, Management Science, 6, 366-422 (1939), 1960 · Zbl 0995.90532
[28] Lorie, J.; Savage, L. J., Three problems in capital rationing, Journal of Business, 28, 229-239 (1955)
[29] Martello, S.; Toth, P., Optimal and canonical solutions of the change making problem, European Journal of Operational Research, 4, 322-329 (1980) · Zbl 0436.90075
[30] Martello, S.; Toth, P., Algorithms for knapsack problems, Annals of Discrete Mathematics, 31, 213-258 (1987)
[31] Pierce, J. F., Some Large-Scale Production Scheduling Problems in the Paper Industry (1964), Englewood Cliffs
[32] Rayward-Smith, V. J.; Shing, M.-T., Bin packing, Bulletin of the IMA, 19, 142-146 (1983) · Zbl 0512.68049
[33] Rode, M.; Rosenberg, O., An analysis of heuristic trim loss algorithms, Engineering Cost and Production Economics, 12, 71-78 (1987)
[34] Salkin, H. M.; de Kluyver, C. A., The knapsack problem: A survey, Naval Research Logistics Quarterly, 22, 127-144 (1975) · Zbl 0305.90038
[35] Stadtler, H., A comparison of two optimization procedures for 1- and 1.5-dimensional cutting stock problems, Operations Research-Spektrum, 10, 97-111 (1988) · Zbl 0642.90051
[36] Stehling, F., Der Bedarf an Münzen in verschiedenen Münzsystemen, Methods of Operations Research, 46, 509-521 (1983)
[37] Terno, J.; Lindemann, R.; Scheithauer, G., Zuschnittprobleme und ihre praktische Lösung (1987), Thun: Thun Frankfurt · Zbl 0657.65089
[38] Wäscher, G., An LP-based approach to cutting stock problems with multiple objectives, EJOR (1990), This issue · Zbl 0684.90081
[39] Wäscher, G.; Carow, P.; Müller, H., Entwicklung eines flexiblen Verfahrens für Zuschneideprobleme in einem Kaltwalzwerk, Zeitschrift für Operations Research, 29B, 209-230 (1985)
[40] Wee, T. S.; Magazine, M. J., Assembly line balancing as generalized bin-packing, Operations Research Letters, 1, 56-58 (1982) · Zbl 0491.90049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.