×

Two-dimensional packing problems: a survey. (English) Zbl 1081.90576

Summary: We consider problems requiring to allocate a set of rectangular items to larger rectangular standardized units by minimizing the waste. In two-dimensional bin packing problems these units are finite rectangles, and the objective is to pack all the items into the minimum number of units, while in two-dimensional strip packing problems there is a single standardized unit of given width, and the objective is to pack all the items within the minimum height. We discuss mathematical models, and survey lower bounds, classical approximation algorithms, recent heuristic and metaheuristic methods and exact enumerative approaches. The relevant special cases where the items have to be packed into rows forming levels are also discussed in detail.

MSC:

90B80 Discrete location and assignment
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C27 Combinatorial optimization

Software:

Tabu search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] (Aarts, E.; Lenstra, J. K., Local Search in Combinatorial Optimization (1997), Wiley: Wiley Chichester) · Zbl 0869.00019
[2] Baker, B. S.; Brown, D. J.; Katseff, H. P., A 5/4 algorithm for two-dimensional packing, Journal of Algorithms, 2, 348-368 (1981) · Zbl 0472.68032
[3] Baker, B. S.; Coffman, E. G.; Rivest, R. L., Orthogonal packing in two dimensions, SIAM Journal on Computing, 9, 846-855 (1980) · Zbl 0447.68080
[4] Beasley, J. E., An exact two-dimensional non-guillotine cutting tree search procedure, Operational Research, 33, 49-64 (1985) · Zbl 0569.90038
[5] Berkey, J. O.; Wang, P. Y., Two dimensional finite bin packing algorithms, Journal of the Operational Research Society, 38, 423-429 (1987) · Zbl 0611.90079
[6] Brown, D. J., An improved BL lower bound, Information Processing Letters, 11, 37-39 (1980) · Zbl 0444.68062
[7] Chazelle, B., The bottom-left bin packing heuristic: An efficient implementation, IEEE Transactions on Computers, 32, 697-707 (1983) · Zbl 0526.68065
[8] Chen, C. S.; Lee, S. M.; Shen, Q. S., A analytical model for the container loading problem, European Journal of Operational Research, 80, 68-76 (1995) · Zbl 0927.90087
[9] Chung, F. K.R.; Garey, M. R.; Johnson, D. S., On packing two-dimensional bins, SIAM Journal of Algebraic and Discrete Methods, 3, 66-76 (1982) · Zbl 0495.05016
[10] Coffman, E. G.; Garey, M. R.; Johnson, D. S.; Tarjan, R. E., Performance bounds for level-oriented two-dimensional packing algorithms, SIAM Journal on Computing, 9, 801-826 (1980) · Zbl 0447.68079
[11] Coffman, E. G.; Lueker, G. S., Probabilistic Analysis of Packing and Partitioning Algorithms (1992), Wiley: Wiley Chichester · Zbl 0770.90031
[12] Coffman, E. G.; Shor, P. W., Average-case analysis of cutting and packing in two dimensions, European Journal of Operational Research, 44, 134-144 (1990) · Zbl 0689.90059
[13] Csirik, J.; Woeginger, G., On-line packing and covering problems, (Online algorithms. Online algorithms, Springer Lecture Notes in Computer Science, vol. 1442 (1996)), 147-177
[14] Dell’Amico, M.; Martello, S., Optimal scheduling of tasks on identical parallel processors, ORSA Journal on Computing, 7, 191-200 (1995) · Zbl 0859.90081
[15] Dowsland, K., Some experiments with simulated annealing techniques for packing problems, European Journal of Operational Research, 68, 389-399 (1993) · Zbl 0800.90729
[16] Dowsland, K. A.; Dowsland, W. B., Packing problems, European Journal of Operational Research, 56, 2-14 (1992) · Zbl 0825.90355
[17] Dyckhoff, H.; Finke, U., Cutting and Packing in Production and Distribution (1992), Physica Verlag: Physica Verlag Heidelberg
[18] Dyckhoff, H.; Scheithauer, G.; Terno, J., Cutting and packing (C&P), (Dell’Amico, M.; Maffioli, F.; Martello, S., Annotated Bibliographies in Combinatorial Optimization (1997), Wiley: Wiley Chichester), 393-413 · Zbl 1068.90509
[19] O. Færø, D. Pisinger, M. Zachariasen, Guided local search for the three-dimensional bin packing problem, Technical paper, DIKU, University of Copenhagen, 1999; O. Færø, D. Pisinger, M. Zachariasen, Guided local search for the three-dimensional bin packing problem, Technical paper, DIKU, University of Copenhagen, 1999
[20] S.P. Fekete, J. Schepers, On more-dimensional packing I: Modeling, Technical paper ZPR97-288, Mathematisches Institut, Universität zu Köln, 1997; S.P. Fekete, J. Schepers, On more-dimensional packing I: Modeling, Technical paper ZPR97-288, Mathematisches Institut, Universität zu Köln, 1997
[21] S.P. Fekete, J. Schepers, On more-dimensional packing II: Bounds, Technical paper ZPR97-289, Mathematisches Institut, Universität zu Köln, 1997; S.P. Fekete, J. Schepers, On more-dimensional packing II: Bounds, Technical paper ZPR97-289, Mathematisches Institut, Universität zu Köln, 1997
[22] S.P. Fekete, J. Schepers, On more-dimensional packing III: Exact algorithms, Technical paper ZPR97-290, Mathematisches Institut, Universität zu Köln, 1997; S.P. Fekete, J. Schepers, On more-dimensional packing III: Exact algorithms, Technical paper ZPR97-290, Mathematisches Institut, Universität zu Köln, 1997
[23] Fekete, S. P.; Schepers, J., New classes of lower bounds for bin packing problems, (Integer Programming and Combinatorial Optimization (IPCO 98). Integer Programming and Combinatorial Optimization (IPCO 98), Springer Lecture Notes in Computer Science, vol. 1412 (1998)), 257-270 · Zbl 0910.90222
[24] Fernandez de la Vega, W.; Lueker, G. S., Bin packing can be solved within \(1+ϵ\) in linear time, Combinatorica, 1, 349-355 (1981) · Zbl 0485.68057
[25] W. Fernandez de la Vega, V. Zissimopoulos, An approximation scheme for strip-packing of rectangles with bounded dimensions, Technical paper, LRI, Université de Paris Sud, Orsay,1991; W. Fernandez de la Vega, V. Zissimopoulos, An approximation scheme for strip-packing of rectangles with bounded dimensions, Technical paper, LRI, Université de Paris Sud, Orsay,1991 · Zbl 0894.68114
[26] Frenk, J. B.; Galambos, G. G., Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem, Computing, 39, 201-217 (1987) · Zbl 0626.68037
[27] Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting stock problem, Operations Research, 9, 849-859 (1961) · Zbl 0096.35501
[28] Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting stock problem—part II, Operations Research, 11, 863-888 (1963) · Zbl 0124.36307
[29] Gilmore, P. C.; Gomory, R. E., Multistage cutting problems of two and more dimensions, Operations Research, 13, 94-119 (1965) · Zbl 0128.39601
[30] Glover, F.; Laguna, M., Tabu Search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0930.90083
[31] Golan, I., Performance bounds for orthogonal oriented two-dimensional packing algorithms, SIAM Journal on Computing, 10, 571-582 (1981) · Zbl 0461.68076
[32] Hadjiconstantinou, E.; Christofides, N., An exact algorithm for general, orthogonal, two-dimensional knapsack problems, European Journal of Operational Research, 83, 39-56 (1995) · Zbl 0903.90124
[33] Hadjiconstantinou, E.; Christofides, N., An exact algorithm for the orthogonal, 2-D cutting problems using guillotine cuts, European Journal of Operational Research, 83, 21-38 (1995) · Zbl 0903.90134
[34] Høyland, S., Bin-packing in 1.5 dimension, (Proceedings of the Scandinavian Workshop on Algorithm Theory. Proceedings of the Scandinavian Workshop on Algorithm Theory, Springer Lecture Notes in Computer Science, vol. 318 (1988)), 129-137 · Zbl 0651.68091
[35] Jacobs, S., On genetic algorithms for the packing of polygons, European Journal of Operational Research, 88, 165-181 (1996)
[36] D.S. Johnson, Near-optimal bin packing algorithms, Ph.D. Thesis, MIT, Cambridge, MA, 1973; D.S. Johnson, Near-optimal bin packing algorithms, Ph.D. Thesis, MIT, Cambridge, MA, 1973
[37] Karmarkar, N.; Karp, R. M., An efficient approximation scheme for the one-dimensional bin-packing problem, (Proceedings of the 23rd Annual IEEE Symposium on Found. Comput. Sci. (1982)), 312-320
[38] Kenyon, C.; Rémila, E., A near-optimal solution to a two-dimensional cutting stock problem, Mathematics of Operations Research, 25, 645-656 (2000) · Zbl 0977.90043
[39] Lodi, A.; Martello, S.; Vigo, D., Neighborhood search algorithm for the guillotine non-oriented two-dimensional bin packing problem, (Voss, S.; Martello, S.; Osman, I. H.; Roucairol, C., Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Boston), 125-139 · Zbl 0970.90079
[40] Lodi, A.; Martello, S.; Vigo, D., Approximation algorithms for the oriented two-dimensional bin packing problem, European Journal of Operational Research, 112, 158-166 (1999) · Zbl 0937.90121
[41] Lodi, A.; Martello, S.; Vigo, D., Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS Journal on Computing, 11, 345-357 (1999) · Zbl 1034.90500
[42] Lodi, A.; Martello, S.; Vigo, D., Recent advances on two-dimensional bin packing problems, Discrete Applied Mathematics, 123/124, 373-380 (2002)
[43] A. Lodi, S. Martello, D. Vigo, Heuristic algorithms for the three-dimensional bin packing problem, European Journal of Operational Research, this issue; A. Lodi, S. Martello, D. Vigo, Heuristic algorithms for the three-dimensional bin packing problem, European Journal of Operational Research, this issue · Zbl 1081.90612
[44] A. Lodi, S. Martello, D. Vigo, Models and bounds for two-dimensional level packing problems, Journal of Combinatorial Optimization, to appear; A. Lodi, S. Martello, D. Vigo, Models and bounds for two-dimensional level packing problems, Journal of Combinatorial Optimization, to appear · Zbl 1084.90031
[45] Lueker, G. S., Bin packing with items uniformly distributed over intervals [a,b], (Proceedings of the 24th Annual Symposium on Found. Comp. Sci. (1983)), 289-297
[46] S. Martello, M. Monaci, D. Vigo, An exact approach to the strip packing problem, Technical paper OR/00/18, Dipartimento di Elettronica, Informatica e Sistemistica, Università di Bologna, 2000; S. Martello, M. Monaci, D. Vigo, An exact approach to the strip packing problem, Technical paper OR/00/18, Dipartimento di Elettronica, Informatica e Sistemistica, Università di Bologna, 2000 · Zbl 1238.90116
[47] Martello, S.; Pisinger, D.; Vigo, D., The three-dimensional bin packing problem, Operations Research, 48, 256-267 (2000) · Zbl 1106.90371
[48] Martello, S.; Toth, P., Knapsack Problems: Algorithms and Computer Implementations (1990), Wiley: Wiley Chichester · Zbl 0708.68002
[49] Martello, S.; Vigo, D., Exact solution of the two-dimensional finite bin packing problem, Management Science, 44, 388-399 (1998) · Zbl 0989.90114
[50] Scheithauer, G., Equivalence and dominance for problems of optimal packing of rectangles, Ricerca Operativa, 83, 3-34 (1997)
[51] Schiermeyer, I., Reverse fit: A 2-optimal algorithm for packing rectangles, (Proceedings of the 2nd Eur. Symposium Algorithms (ESA) (1994)), 290-299
[52] Sleator, D., A 2.5 times optimal algorithm for packing in two dimensions, Information Processing Letters, 10, 37-40 (1980) · Zbl 0426.05023
[53] Steinberg, A., A strip-packing algorithm with absolute performance bound 2, SIAM Journal on Computing, 26, 401-409 (1997) · Zbl 0874.68140
[54] Voudouris, C.; Tsang, E., Guided local search and its application to the traveling salesman problem, European Journal of Operational Research, 113, 469-499 (1999) · Zbl 0937.90094
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.