×

zbMATH — the first resource for mathematics

Recent advances on two-dimensional bin packing problems. (English) Zbl 1022.90020
The paper is the survey of recent advances obtained for the two-dimensional bin packing problem with special emphasis on exact algorithms and effective heuristic and metaheuristic approaches. The authors consider only off-line heuristic algorithms, for which it is assumed that the algorithm has full knowledge of the whole input. In particular it is presented some estimations of the optimal solution value. It is given the extensive list of the literature on this theme.

MSC:
90C27 Combinatorial optimization
90B80 Discrete location and assignment
Software:
Tabu search
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aarts, E.; Lenstra, J.K., Local search in combinatorial optimization, (1997), John Wiley & Sons Chichester · Zbl 0869.00019
[2] Baker, B.S.; Brown, D.J.; Katseff, H.P., A 5/4 algorithm for two-dimensional packing, J. algorithms, 2, 348-368, (1981) · Zbl 0472.68032
[3] Baker, B.S.; Coffman, E.G.; Rivest, R.L., Orthogonal packing in two dimensions, SIAM J. comput., 9, 846-855, (1980) · Zbl 0447.68080
[4] Baker, B.S.; Schwarz, J.S., Shelf algorithms for two-dimensional packing problems, SIAM J. comput., 12, 508-525, (1983) · Zbl 0521.68084
[5] Beasley, J.E., An exact two-dimensional non-guillotine cutting tree search procedure, Oper. res., 33, 49-64, (1985) · Zbl 0569.90038
[6] Bengtsson, B.E., Packing rectangular pieces—a heuristic approach, Comput. J., 25, 353-357, (1982)
[7] Berkey, J.O.; Wang, P.Y., Two dimensional finite bin packing algorithms, J. oper. res. soc., 38, 423-429, (1987) · Zbl 0611.90079
[8] Brown, D.J., An improved BL lower bound, Inform. process. lett., 11, 37-39, (1980) · Zbl 0444.68062
[9] Chazelle, B., The bottom-left bin packing heuristic: an efficient implementation, IEEE trans. on comput., 32, 697-707, (1983) · Zbl 0526.68065
[10] Christofides, N.; Whitlock, C., An algorithm for two-dimensional cutting problems, Oper. res., 25, 30-44, (1977) · Zbl 0369.90059
[11] Chung, F.K.R.; Garey, M.R.; Johnson, D.S., On packing two-dimensional bins, SIAM J. algebraic discrete meth., 3, 66-76, (1982) · Zbl 0495.05016
[12] Coffman, E.G.; Garey, M.R.; Johnson, D.S.; Tarjan, R.E., Performance bounds for level-oriented two-dimensional packing algorithms, SIAM J. comput., 9, 801-826, (1980) · Zbl 0447.68079
[13] Coffman, E.G.; Lueker, G.S., Probabilistic analysis of packing and partitioning algorithms, (1992), John Wiley & Sons Chichester · Zbl 0770.90031
[14] Coffman, E.G.; Shor, P.W., Packings in two dimensions: asymptotic average-case analysis of algorithms, Algorithmica, 9, 253-277, (1993) · Zbl 0787.68046
[15] J. Csirik, G. Woeginger, On-line packing and covering problems, in: Online algorithms, Lecture Notes in Computer Science, eds. F. Amos and G. Woeginger, Vol. 144, Springer, Berlin, 1998, pp. 147-177.
[16] M. Dell’Amico, S. Martello, D. Vigo, A lower bound for the non-oriented two-dimensional bin packing problem, Discrete Appl. Math. 2002, to appear.
[17] Dell’Amico, M.; Martello, S., Optimal scheduling of tasks on identical parallel processors, ORSA J. comput., 7, 191-200, (1995) · Zbl 0859.90081
[18] El-Bouri, A.; Popplewell, N.; Balakrishnan, S.; Alfa, A., A search based heuristic for the two-dimensional bin-packing problem, Infor, 32, 265-274, (1994) · Zbl 0824.90116
[19] S.P. Fekete, J. Schepers, On more-dimensional packing I: Modeling, Technical Report ZPR97-288, Mathematisches Institut, Universität zu Köln, 1997.
[20] S.P. Fekete, J. Schepers, On more-dimensional packing II: Bounds, Technical Report ZPR97-289, Mathematisches Institut, Universität zu Köln, 1997.
[21] S.P. Fekete, J. Schepers, On more-dimensional packing III: Exact algorithms, Technical Report ZPR97-290, Mathematisches Institut, Universität zu Köln, 1997.
[22] S.P. Fekete, J. Schepers, New classes of lower bounds for bin packing problems, in: Integer Programming and Combinatorial Optimization (IPCO 98), Lecture Notes in Computer Science, eds. R.E. Bixby, E.A. Boyd and R.Z. Rı́os-Mercado, Vol. 1412, Springer, Berlin, 1998, pp. 257-270. · Zbl 0910.90222
[23] 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
[24] Gilmore, P.C.; Gomory, R.E., A linear programming approach to the cutting stock problem, Oper. res., 9, 849-859, (1961) · Zbl 0096.35501
[25] Gilmore, P.C.; Gomory, R.E., A linear programming approach to the cutting stock problem—part II, Oper. res., 11, 863-888, (1963) · Zbl 0124.36307
[26] Gilmore, P.C.; Gomory, R.E., Multistage cutting problems of two and more dimensions, Oper. res., 13, 94-119, (1965) · Zbl 0128.39601
[27] Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Academic Publishers Boston · Zbl 0930.90083
[28] Golan, I., Performance bounds for orthogonal oriented two-dimensional packing algorithms, SIAM J. comput., 10, 571-582, (1981) · Zbl 0461.68076
[29] Hadjiconstantinou, E.; Christofides, N., An exact algorithm for general, orthogonal, two-dimensional knapsack problems, Eur. J. oper. res., 83, 39-56, (1995) · Zbl 0903.90124
[30] Hadjiconstantinou, E.; Christofides, N., An exact algorithm for the orthogonal, 2-D cutting problems using guillotine cuts, Eur. J. oper. res., 83, 21-38, (1995) · Zbl 0903.90134
[31] M. Hifi, Exact algorithms for large-scale unconstrained two and three staged cutting problems, In Contribution à la Résolution de Quelques Problèmes Difficiles de l’Optimisation Combinatoire, Thèse d’Habilitation à Diriger des Recherches en Informatique, Université de Versailles-Saint Quentin en Yvelines, 1998.
[32] S. Høyland, Bin-packing in 1.5 dimension, In Proceedings of the Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol. 318, Springer, Berlin, 1988, pp. 129-137.
[33] D.S. Johnson, Near-optimal bin packing algorithms, PhD Thesis, MIT, Cambridge, MA, 1973.
[34] Johnson, D.S.; Demers, A.; Ullman, J.D.; Garey, M.R.; Graham, R.L., Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM J. comput., 3, 299-325, (1974) · Zbl 0297.68028
[35] Kenyon, C.; Rémila, E., A near-optimal solution to a two-dimensional cutting stock problem, Math. oper. res., 25, 645-656, (2000) · Zbl 0977.90043
[36] K. Lagus, I. Karanta, J. Ylä-Jääski, Paginating the generalized newspaper: A comparison of simulated annealing and a heuristic method. Proceedings of the Fifth International Conference on Parallel Problem Solving from Nature, Berlin, 1996, pp. 549-603.
[37] Lodi, A.; Martello, S.; Vigo, D., Neighborhood search algorithm for the guillotine non-oriented two-dimensional bin packing problem, (), 125-139 · Zbl 0970.90079
[38] Lodi, A.; Martello, S.; Vigo, D., Approximation algorithms for the oriented two-dimensional bin packing problem, Eur. J. oper. res., 112, 158-166, (1999) · Zbl 0937.90121
[39] Lodi, A.; Martello, S.; Vigo, D., Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS J. comput., 11, 345-357, (1999) · Zbl 1034.90500
[40] A. Lodi, S. Martello, D. Vigo, Heuristic algorithms for the three-dimensional bin packing problem, Eur. J. Oper. Res. 2002, to appear. · Zbl 1081.90612
[41] A. Lodi, M. Monaci, Integer linear programming models for two-staged cutting stock problems, Technical Report OR/00/12, DEIS-Università di Bologna, 2000, to appear in Mathematical Programming. · Zbl 1030.90064
[42] Martello, S.; Toth, P., Knapsack problems: algorithms and computer implementations, (1990), John Wiley & Sons Chichester · Zbl 0708.68002
[43] Martello, S.; Vigo, D., Exact solution of the two-dimensional finite bin packing problem, Manage. sci., 44, 388-399, (1998) · Zbl 0989.90114
[44] Schneider, W., Trim-loss minimization in a crepe-rubber mill; optimal solution versus heuristic in the 2 (3)-dimensional case, Eur. J. oper. res., 34, 273-281, (1988)
[45] Sleator, D., A 2.5 times optimal algorithm for packing in two dimensions, Inform. process. lett., 10, 37-40, (1980) · Zbl 0426.05023
[46] Steinberg, A., A strip-packing algorithm with absolute performance bound 2, SIAM J. comput., 26, 401-409, (1980) · Zbl 0874.68140
[47] Vasko, F.J.; Wolf, F.E.; Stott, K.L., A practical solution to a fuzzy two-dimensional cutting stock problem, Fuzzy sets and systems, 29, 259-275, (1989)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.