New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems. (English) Zbl 1177.90349
Summary: We consider two types of orthogonal, oriented, rectangular, two-dimensional packing problems. The first is the strip packing problem, for which four new and improved level-packing algorithms are presented. Two of these algorithms guarantee a packing that may be disentangled by guillotine cuts. These are combined with a two-stage heuristic designed to find a solution to the variable-sized bin packing problem, where the aim is to pack all items into bins so as to minimise the packing area. This heuristic packs the levels of a solution to the strip packing problem into large bins and then attempts to repack the items in those bins into smaller bins in order to reduce wasted space. The results of the algorithms are compared to those of seven level-packing heuristics from the literature by means of a large number of strip-packing benchmark instances. It is found that the new algorithms are an improvement over known level-packing heuristics for the strip packing problem. The advancements made by the new and improved algorithms are limited in terms of utilised space when applied to the variable-sized bin packing problem. However, they do provide results faster than many existing algorithms.
MSC:
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Alvarez-Valdes, R.; Parajon, A.; Tamarit, J. M., A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems, OR Spectrum, 24, 2, 179-192 (2002) · Zbl 1012.90032 |
| [2] | Alvarez-Valdes, R.; Parajon, A.; Tamarit, J. M., A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems, Computers and Operations Research, 29, 7, 925-947 (2002) · Zbl 0995.90075 |
| [3] | Alvarez-Valdes, R.; Parreño, F.; Tamarit, J. M., A grasp algorithm for constrained two-dimensional non-guillotine cutting problems, Journal of the Operational Research Society, 56, 4, 414-425 (2005) · Zbl 1104.90040 |
| [4] | Alvarez-Valdes, R.; Parreño, F.; Tamarit, J. M., A tabu search algorithm for a two-dimensional non-guillotine cutting problem, European Journal of Operations Research, 183, 3, 1167-1182 (2007) · Zbl 1138.90430 |
| [5] | Alvarez-Valdes, R.; Parreño, F.; Tamarit, J. M., Reactive grasp for the strip-packing problem, Computers and Operations Research, 35, 4, 1065-1083 (2008) · Zbl 1179.90269 |
| [6] | Baker, B. S.; Brown, D. J.; Katseff, H. P., A 5/4 algorithm for two-dimensional packing, Journal of Algorithms, 2, 4, 348-368 (1981) · Zbl 0472.68032 |
| [7] | Baker, B. S.; Coffman, E. G.; Rivest, R. L., Orthogonal packings in two dimensions, SIAM Journal on Computing, 9, 4, 846-855 (1980) · Zbl 0447.68080 |
| [8] | Beisiegel, B.; Kallrath, J.; Kochetov, Y.; Rudnev, A., Simulated annealing based algorithm for the 2D bin packing problem with impurities, (Haasis, H. D.; Kopfer, H.; Schönberger, J., Operations Research Proceedings 2005 (2006), Springer: Springer Heidelberg), 309-314 |
| [9] | Belov, G.; Scheithauer, G.; Mukhacheva, E. A., One-dimensional heuristics adapted for two-dimensional rectangular strip packing, Journal of the Operational Research Society, 59, 6, 823-832 (2008) · Zbl 1153.90444 |
| [10] | Benati, S., An algorithm for a cutting stock problem on a strip, Journal of the Operational Research Society, 48, 3, 288-294 (1997) · Zbl 0890.90154 |
| [11] | Berkey, J. O.; Wang, P. Y., Two-dimensional finite bin-packing algorithms, Journal of the Operational Research Society, 38, 5, 423-429 (1987) · Zbl 0611.90079 |
| [12] | Bortfeldt, A., A genetic algorithm for the two-dimensional strip packing with rectangular pieces, European Journal of Operational Research, 172, 3, 814-837 (2006) · Zbl 1111.90094 |
| [13] | Burke, E. K.; Kendall, G.; Whitwell, G., A new placement heuristic for the orthogonal stock-cutting problem, Operations Research, 52, 4, 655-671 (2004) · Zbl 1165.90690 |
| [14] | E.K. Burke, G. Kendall, G. Whitwell, A new placement heuristic for the orthogonal stock-cutting problem, Technical Report, School of Computer Science and Information Technology, University of Nottingham, Nottingham, 2006.; E.K. Burke, G. Kendall, G. Whitwell, A new placement heuristic for the orthogonal stock-cutting problem, Technical Report, School of Computer Science and Information Technology, University of Nottingham, Nottingham, 2006. · Zbl 1165.90690 |
| [15] | Chazelle, B., The bottom-left bin packing heuristic: An efficient implementation, IEEE Transactions on Computers, 32, 8, 697-707 (1983) · Zbl 0526.68065 |
| [16] | Christofides, N.; Whitlock, C., An algorithm for two-dimensional cutting problems, Operations Research, 25, 1, 31-44 (1977) · Zbl 0369.90059 |
| [17] | Chung, F. R.K.; Garey, M. R.; Johnson, D. S., On packing two-dimensional bins, SIAM Journal on Algebraic and Discrete Methods, 3, 1, 66-76 (1982) · Zbl 0495.05016 |
| [18] | Clautiaux, F.; Carlier, J.; Moukrim, A., A new exact method for the two-dimensional bin-packing problem with fixed orientation, Operations Research Letters, 35, 3, 357-364 (2007) · Zbl 1169.90430 |
| [19] | Coffman, E. G.; Garey, M. R.; Johnson, D. S., Approximation algorithms for bin packing: A survey, (Hochbaum, D. S., Approximation Algorithms for NP-hard Problems (1996), PWS Publishing Company: PWS Publishing Company Boston, MA), 46-93 · Zbl 1368.68010 |
| [20] | 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, 4, 808-826 (1980) · Zbl 0447.68079 |
| [21] | Coffman, E. G.; Shor, P. W., Average-case analysis of cutting and packing in two dimensions, European Journal of Operational Research, 44, 2, 134-144 (1990) · Zbl 0689.90059 |
| [22] | Cui, Y., Heuristic and exact algorithms for generating homogenous constrained three-staged cutting patterns, Computers and Operations Research, 35, 1, 212-225 (2008) · Zbl 1149.90428 |
| [23] | Cui, Y.; Yang, Y.; Cheng, X.; Song, P., A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem, Computers and Operations Research, 35, 4, 1281-1291 (2008) · Zbl 1157.90558 |
| [24] | Dyckhoff, H., A typology of cutting and packing problems, European Journal of Operational Research, 44, 2, 145-159 (1990) · Zbl 0684.90076 |
| [25] | Eisemann, K., The trim problem, Management Science, 3, 3, 279-284 (1957) · Zbl 0995.92500 |
| [26] | ESICUP, Listing Gallery: Data Sets 2D - Rectangular, Cited: 2007-10-29, 2007. <http://paginas.fe.up.pt/ esicup/tiki-list_file_gallery.php?galleryId=3>; ESICUP, Listing Gallery: Data Sets 2D - Rectangular, Cited: 2007-10-29, 2007. <http://paginas.fe.up.pt/ esicup/tiki-list_file_gallery.php?galleryId=3> |
| [27] | Faina, L., An application of simulated annealing to the cutting stock problem, European Journal of Operational Research, 114, 3, 542-556 (1999) · Zbl 0938.90057 |
| [28] | Frenk, J. B.G.; Galambos, G., Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem, Computing, 39, 3, 201-217 (1987) · Zbl 0626.68037 |
| [29] | Friesen, D. K.; Langston, M. A., Variable-sized bin packing, SIAM Journal on Computing, 15, 1, 222-230 (1986) · Zbl 0589.68036 |
| [30] | Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting-stock problem, Operations Research, 11, 6, 849-859 (1961) · Zbl 0096.35501 |
| [31] | Gilmore, P. C.; Gomory, R. E., A linear programming approach to the cutting-stock problem - Part II, Operations Research, 9, 6, 863-888 (1963) · Zbl 0124.36307 |
| [32] | Gilmore, P. C.; Gomory, R. E., Multistage cutting problems of two and more dimensions, Operations Research, 13, 1, 94-120 (1965) · Zbl 0128.39601 |
| [33] | Girkar, M.; MacLeod, B.; Moll, R., Performance bound for bottom-left guillotine packing of rectangles, Journal of the Operational Research Society, 43, 2, 169-175 (1992) · Zbl 0751.90061 |
| [34] | Golan, I., Performance bounds for orthogonal oriented two-dimensional packing algorithms, SIAM Journal on Computing, 10, 3, 571-582 (1981) · Zbl 0461.68076 |
| [35] | J.F. Gonçalves, M.G.C. Resende, A hybrid heuristic for the constrained two-dimensional non-guillotine orthogonal cutting problem, Technical Report, AT&T Labs Research, Florham Park, NJ, 2006.; J.F. Gonçalves, M.G.C. Resende, A hybrid heuristic for the constrained two-dimensional non-guillotine orthogonal cutting problem, Technical Report, AT&T Labs Research, Florham Park, NJ, 2006. |
| [36] | Gradišar, M.; Resinovič, G.; Kljajić, M., Evaluation of algorithms for one-dimensional cutting, Computers and Operations Research, 29, 9, 1207-1220 (2002) · Zbl 1008.90049 |
| [37] | Hifi, M.; Zissimopoulos, V., Constrained two-dimensional cutting: An improvement of Christofides and Whitlock’s exact algorithm, Journal of the Operational Research Society, 48, 3, 324-331 (1997) · Zbl 0890.90157 |
| [38] | E. Hopper, Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods, Ph.D. Thesis, University of Wales, Cardiff, 2000.; E. Hopper, Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods, Ph.D. Thesis, University of Wales, Cardiff, 2000. |
| [39] | Hopper, E.; Turton, B. C.H., A genetic algorithm for a 2D industrial packing problem, Computers in Engineering, 37, 1, 375-378 (1999) |
| [40] | Hopper, E.; Turton, B. C.H., An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem, European Journal of Operational Research, 128, 1, 34-57 (2001) · Zbl 0982.90044 |
| [41] | Hopper, E.; Turton, B. C.H., A review of the application of meta-heuristic algorithms to 2D strip packing problems, Artificial Intelligence Review, 16, 4, 257-300 (2001) · Zbl 1032.68721 |
| [42] | Hopper, E.; Turton, B. C.H., Problem generators for rectangular packing problems, Studia Informatica Universalis, 2, 1, 123-136 (2002) |
| [43] | Jakobs, S., On genetic algorithms for the packing of polygons, European Journal of Operational Research, 88, 1, 165-181 (1996) · Zbl 0913.90229 |
| [44] | D.S. Johnson, Near-optimal bin packing algorithms, Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA, 1973.; D.S. Johnson, Near-optimal bin packing algorithms, Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA, 1973. |
| [45] | Johnson, D. S.; Demars, A.; Ullman, J. D.; Garey, M. R.; Graham, R. L., Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM Journal on Computing, 3, 4, 295-325 (1974) · Zbl 0297.68028 |
| [46] | Johnsonbaugh, R.; Schaefer, M., Algorithms (2004), Pearson Prentice-Hall: Pearson Prentice-Hall Upper Saddle River, NJ |
| [47] | Kang, J.; Park, S., Algorithms for the variable sized bin packing problem, European Journal of Operational Research, 147, 2, 365-372 (2003) · Zbl 1031.90027 |
| [48] | Kantorovich, L. V., Mathematical methods of organizing and planning production, Management Science, 6, 4, 366-422 (1960), (reprint and translation of 1939 original manuscript) · Zbl 0995.90532 |
| [49] | Liu, D.; Teng, H., An improved BL-algorithm for genetic algorithms of the orthogonal packing of rectangles, European Journal of Operational Research, 112, 2, 413-419 (1999) · Zbl 0970.90077 |
| [50] | Lodi, A.; Martello, S.; Monaci, M., Two-dimensional packing problems: A survey, European Journal of Operational Research, 141, 2, 241-252 (2002) · Zbl 1081.90576 |
| [51] | 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, MA), 125-139 · Zbl 0970.90079 |
| [52] | Lodi, A.; Martello, S.; Vigo, D., Approximation algorithms for the oriented two-dimensional bin packing problem, European Journal of Operational Research, 112, 1, 158-166 (2002) · Zbl 0937.90121 |
| [53] | Lodi, A.; Martello, S.; Vigo, D., Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems, INFORMS Journal on Computing, 11, 4, 345-357 (1999) · Zbl 1034.90500 |
| [54] | Lodi, A.; Martello, S.; Vigo, D., Recent advances on two-dimensional bin packing problems, Discrete Applied Mathematics, 123, 1, 379-396 (2002) · Zbl 1022.90020 |
| [55] | Lodi, A.; Martello, S.; Vigo, D., Models and bounds for two-dimensional level packing problems, Journal of Combinatorial Optimization, 8, 3, 363-379 (2004) · Zbl 1084.90031 |
| [56] | Martello, S.; Monaci, M.; Vigo, D., An exact approach to the strip-packing problem, INFORMS Journal on Computing, 15, 3, 310-319 (2003) · Zbl 1238.90116 |
| [57] | M. Monaci, Algorithms for packing and scheduling problems, Ph.D. Thesis, Università di Bologna, Bologna, 2001.; M. Monaci, Algorithms for packing and scheduling problems, Ph.D. Thesis, Università di Bologna, Bologna, 2001. · Zbl 1041.90529 |
| [58] | N. Ntene, An algorithmic approach to the 2D oriented strip packing problem, Ph.D. Thesis, University of Stellenbosch, Stellenbosch, 2007.; N. Ntene, An algorithmic approach to the 2D oriented strip packing problem, Ph.D. Thesis, University of Stellenbosch, Stellenbosch, 2007. |
| [59] | Ntene, N.; Van Vuuren, J. H., A survey and comparison of guillotine heuristics for the 2D oriented offline strip packing problem, Discrete Optimization, 6, 2, 174-188 (2009) · Zbl 1159.90527 |
| [60] | Pisinger, D.; Sigurd, M., The two-dimensional bin packing problem with variable bin sizes and costs, Discrete Optimization, 2, 2, 154-167 (2005) · Zbl 1077.90057 |
| [61] | Pisinger, D.; Sigurd, M., Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem, INFORMS Journal on Computing, 19, 1, 35-36 (2007) · Zbl 1241.90118 |
| [62] | Pureza, V.; Morabito, R., Some experiments with a simple tabu search algorithm for the manufacturer’s pallet loading problem, Computers and Operations Research, 33, 3, 804-819 (2006) · Zbl 1088.90046 |
| [63] | Sleator, D. D.K. D.B., A 2.5 times optimal algorithm for packing in two dimensions, Information Processing Letters, 10, 1, 37-40 (1980) · Zbl 0426.05023 |
| [64] | Sweeney, P. E.; Paternoster, E. R., Cutting and packing problems: A categorized, application-oriented research bibliography, Journal of the Operational Research Society, 43, 7, 691-706 (1992) · Zbl 0757.90055 |
| [65] | C.L. Valenzuela, P.Y. Wang, Heuristics for large strip packing problems with guillotine patterns: An empirical study, in: Metaheuristic International Conference: Porto, Cited: 2008-04-22, 2001. <http://users.cs.cf.ac.uk/C.L.Mumford/papers/binpaper.pdf>; C.L. Valenzuela, P.Y. Wang, Heuristics for large strip packing problems with guillotine patterns: An empirical study, in: Metaheuristic International Conference: Porto, Cited: 2008-04-22, 2001. <http://users.cs.cf.ac.uk/C.L.Mumford/papers/binpaper.pdf> |
| [66] | J.H. Van Vuuren, F.G. Ortmann, Benchmarks, under “Benchmarks”, Cited: 2008-09-10, 2008. <http://www.vuuren.co.za/main.php>; J.H. Van Vuuren, F.G. Ortmann, Benchmarks, under “Benchmarks”, Cited: 2008-09-10, 2008. <http://www.vuuren.co.za/main.php> |
| [67] | Wang, P. Y., Two algorithms for constrained two-dimensional cutting stock problems, Operations Research, 31, 3, 573-586 (1983) · Zbl 0517.90093 |
| [68] | Wang, P. Y.; Valenzuela, C. L., Data set generation for rectangular placement problems, European Journal of Operational Research, 134, 2, 378-391 (2001) · Zbl 0990.90104 |
| [69] | Wäscher, G.; Haußner, H.; Schumann, H., An improved typology of cutting and packing problems, European Journal of Operational Research, 183, 3, 1109-1130 (2007) · Zbl 1278.90347 |
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.
