An Exact Algorithm for the Two-Dimensional Strip-Packing Problem

References

• Alvarez-Valdes R., Parreño F., Tamarit J. M. Reactive GRASP for the strip-packing problem. Comput. Oper. Res. (2008) 35(4):1065–1083Crossref, Google Scholar
• Alvarez-Valdes R., Parreño F., Tamarit J. M. A branch and bound algorithm for the strip packing problem. OR Spectrum (2009) 31(2):431–459Crossref, Google Scholar
• Alvarez-Valdes R., Marti R., Tamarit J. M., Parajon A. GRASP and path relinking for the two-dimensional two-stage cutting stock problem. INFORMS J. Comput. (2007) 19(2):261–272Link, Google Scholar
• Alves C. Cutting and packing: Problems, models and exact algorithms. (2005) . Ph.D. thesis, Universidade do Minho, Braga, PortugalGoogle Scholar
• Baker B. S., Coffman G., Rivest R. L. Orthogonal packings in two dimensions. SIAM J. Comput. (1980) 9(4):808–826Crossref, Google Scholar
• Baldacci R., Boschetti M. A. A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem. Eur. J. Oper. Res. (2007) 183(3):1136–1149Crossref, Google Scholar
• Beasley J. E. Algorithms for unconstrained two-dimensional guillotine cutting. J. Oper. Res. Soc. (1985a) 36(4):297–306Crossref, Google Scholar
• Beasley J. E. An exact two-dimensional non-guillotine cutting tree search procedure. Oper. Res. (1985b) 33(1):49–64Link, Google Scholar
• Belov G., Scheithauer G. Setup amd open-stack minimization in one-dimensional stock cutting. INFORMS J. Comput. (2007) 19(1):27–35Link, Google Scholar
• Belov G., Scheithauer G., Mukhacheva E. A. One-dimensional heuristics adapted for two-dimensional rectangular strip packing. (2006) . Preprint MATH-NM-02-2006, Dresden University, Dresden, GermanyGoogle Scholar
• Bengtsson B. E. Packing rectangular pieces—A heuristic approach. Comput. J. (1982) 25(3):353–357Crossref, Google Scholar
• Berkey J. O., Wang P. Y. Two dimensional finite bin packing algorithms. J. Oper. Res. Soc. (1987) 38(5):423–429Crossref, Google Scholar
• Bortfeldt A. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. Eur. J. Oper. Res. (2006) 172(3):814–837Crossref, Google Scholar
• Boschetti M. A. New lower bounds for the three-dimensional finite bin packing problems. Discrete Appl. Math. (2004) 140(1–3):241–258Crossref, Google Scholar
• Boschetti M. A., Mingozzi A. The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case. 4OR (2003a) 1(1):27–42Crossref, Google Scholar
• Boschetti M. A., Mingozzi A. The two-dimensional finite bin packing problem. Part II: New lower and upper bounds. 4OR (2003b) 1(2):137–147Crossref, Google Scholar
• Boschetti M. A., Hadjinconstantinou E., Mingozzi A. New upper bounds for the finite two-dimensional orthogonal non-guillotine cutting stock problem. IMA J. Management Math. (2002) 13(2):95–119Crossref, Google Scholar
• Burke E. K., Kendall G., Whitwell G. A new placement heuristic for the orthogonal stock-cutting problem. Oper. Res. (2004) 54(4):655–671Link, Google Scholar
• Burke E. K., Kendall G., Whitwell G. A simulated annealing enhancement of the best-fit heuristic for the orthogonal stock cutting problem. INFORMS J. Comput. (2009) 21(3):505–516Link, Google Scholar
• Carlier J., Clautiaux F., Moukrim A. New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation. Comput. Oper. Res. (2007) 34(8):2223–2250Crossref, Google Scholar
• Chazelle B. The bottom-left bin packing heuristic: An efficient implementation. IEEE Trans. Comput. (1983) 32(8):697–707Crossref, Google Scholar
• Christofides N., Whitlock C. An algorithm for two-dimensional cutting problems. Oper. Res. (1977) 25(1):30–44Link, Google Scholar
• Clautiaux F., Alves C., Valério de Carvalho J. A comparative analysis and computational study of dual-feasible functions for bin-packing problems. (2007a) . Technical report, Université des Sciences et Technologies de Lille, Lille, FranceGoogle Scholar
• Clautiaux F., Carlier J., Moukrim A. A new exact method for the two-dimensional bin-packing problem with fixed orientation. Oper. Res. Lett. (2007b) 35(3):357–364Crossref, Google Scholar
• Clautiaux F., Carlier J., Moukrim A. A new exact method for the two-dimensional orthogonal packing problem. Eur. J. Oper. Res. (2007c) 183(3):1196–1211Crossref, Google Scholar
• Clautiaux F., Jouglet A., El Hayek J. A new lower bound for the non-oriented two-dimensional bin-packing problem. Oper. Res. Lett. (2007d) 35(3):365–373Crossref, Google Scholar
• Clautiaux F., Jouglet A., Carlier J., Moukrim A. A new constraint programming approach for the orthogonal packing problem. Comput. Oper. Res. (2008) 35(3):944–959Crossref, Google Scholar
• Fekete S. P., Schepers J. A new exact algorithm for general orthogonal d-dimensional knapsack problems. Lecture Notes in Computer Science, ESA '97—5th Annual European Symposium (1997) (Springer, New York) 144–156Crossref, Google Scholar
• Fekete S. P., Schepers J. New classes of lower bounds for bin-packing problem. Lecture Notes in Computer Science, IPCO 98 (1998) (Springer, London) 257–270Crossref, Google Scholar
• Fekete S. P., Schepers J. On more-dimensional packing II: Bounds. (2000) . Technical Report 97.289, Universität zu Köln, Köln, GermanyGoogle Scholar
• Fekete S. P., Schepers J., van der Veen J. C. An exact algorithm for higher-dimensional orthogonal packing. Oper. Res. (2007) 55(3):569–587Link, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability, A Guide to the Theory of NP-Completeness (1979) (Freeman, New York) Google Scholar
• Gómez A., de la Fuente D. Resolution of strip-packing problems with genetic algorithms. J. Oper. Res. Soc. (2000) 51(11):1289–1295Crossref, Google Scholar
• Herz J. C. Recursive computational procedure for the two dimensional stock cutting. IBM J. Res. Development (1972) 16(5):462–469Crossref, Google Scholar
• Hopper E., Turton B. C. H. An empirical investigation of meta-heuristic and heuristic algorithm for a 2D packing problem. Eur. J. Oper. Res. (2001) 128(1):34–57Crossref, Google Scholar
• Imahori S., Yagiura M. The best-fit heuristic for the rectangular strip packing problem: An efficient implementation and the worst-case approximation ratio. Comput. Oper. Res. (2010) 37(2):325–333Crossref, Google Scholar
• Iori M., Martello S., Monaci M., Pardalos P. M., Korotkith V. Metaheuristic algorithms for the strip packing problem. Optimization and Industry: New Frontiers (2003) (Kluwer Academic Publishers, Boston) 159–179Crossref, Google Scholar
• Jakobs S. On genetic algorithms for the packing of polygons. Eur. J. Oper. Res. (1996) 88(1):165–181Crossref, Google Scholar
• Johnson D. S. Near-optimal bin packing algorithms. (1973) . Dissertation, MIT, Cambridge, MAGoogle Scholar
• Lesh N., Mitzenmacher M. BubbleSearch: A simple heuristic for improving priority-based greedy algorithms. Inform. Processing Lett. (2006) 97(4):161–169Crossref, Google Scholar
• Lesh N., Marks J., McMahon A., Mitzenmacher M. New heuristic and interactive approaches to 2D rectangular strip packing. ACM J. Experiment. Algorithmics (2005) 10:1–18Google Scholar
• Liu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. Eur. J. Oper. Res. (1999) 112(2):413–420Crossref, Google Scholar
• Lueker G. S. Bin packing with items uniformly distributed over intervals [a, b]. Proc. 24th Annual Sympos. Foundations Comput. Sci. (FOCS 83) (1983) (IEEE Computer Society Press, New York) 289–297Crossref, Google Scholar
• Martello S., Toth P.Knapsack Problems: Algorithms and Computer Implementations (1990) (John Wiley & Sons, Chichester, UK) Google Scholar
• Martello S., Vigo D. Exact solution of the two-dimensional finite bin packing problem. Management Sci. (1998) 44(3):388–399Link, Google Scholar
• Martello S., Monaci M., Vigo D. An exact approach to the strip packing problem. INFORMS J. Comput. (2003) 15(3):310–319Link, Google Scholar
• Mukhacheva E. A., Belov G. N., Kartack V. M., Mukhacheva A. S. Linear one-dimensional cutting-packing problems: Numerical experiments with the sequential value correction method (SVC) and a modified banch-and-bound method (MBB). Pesquisa Operacional (2000) 20(2):153–168Crossref, Google Scholar
• Pisinger D. An expanding-core algorithm for the exact 0–1 knapsack problem. Eur. J. Oper. Res. (1995) 87(1):175–187Crossref, Google Scholar
• Scheithauer G. LP-based bounds for the container and multi-container loading problem. Internat. Trans. Oper. Res. (1999) 6(2):199–213Crossref, Google Scholar
• Wäscher G., Haussner H., Schumann H. An improved typology of cutting and packing problems. Eur. J. Oper. Res. (2007) 183(3):1109–1130Crossref, Google Scholar
• Yeungm L. H. W., Tang W. K. S. Strip-packing using hybrid genetic approach. Engrg. Appl. Artificial Intelligence (2004) 17(2):169–177Crossref, Google Scholar