Models for the two-dimensional level strip packing problem – a review and a computational evaluation

References

• Alvarez-Valdés, R., Parajón, A., & Tamarit, J. M. (2002). A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems. Computers & Operations Research, 29(7), 925–947. doi:10.1016/S0305-0548(00)00095-2
   Web of Science ®Google Scholar
• Beasley, J. E. (1985). An exact two-dimensional non-guillotine cutting tree search procedure. Operations Research, 33(1), 49–64. doi:10.1287/opre.33.1.49
   Web of Science ®Google Scholar
• Bekrar, A., & Kacem, I. (2009). An exact method for the 2d guillotine strip packing problem. Advances in Operations Research, 2009, 20p.
   Google Scholar
• Belov, G., & Scheithauer, G. (2006). A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. European Journal of Operational Research, 171(1), 85– 106. doi:10.1016/j.ejor.2004.08.036. doi:10.1016/j.ejor.2004.08.036
   Web of Science ®Google Scholar
• Berkey, J. O., & Wang, P. Y. (1987). Two-dimensional finite bin-packing algorithms. Journal of the Operational Research Society, 38(5), 423–429. doi:10.1057/jors.1987.70
   Web of Science ®Google Scholar
• Bettinelli, A., Ceselli, A., & Righini, G. (2008). A branch-and-price algorithm for the two-dimensional level strip packing problem. 4OR, 6(4), 361–374. doi:10.1007/s10288-007-0051-7
   Web of Science ®Google Scholar
• Bezerra, V. M. R., Leao, A. A. S., Oliveira, J. F., & Santos, M. O. (2017). Análise de formulações matemáticas para o problema de empacotamento em faixas bidimensional guilhotinado 2-estágios. In XLIX Simpósio Brasileiro de Pesquisa Operacional, Blumenau, SC. [CrossRef]
   Google Scholar
• Castro, P. M., & Oliveira, J. F. (2011). Scheduling inspired models for two-dimensional packing problems. European Journal of Operational Research, 215(1), 45–56. doi:10.1016/j.ejor.2011.06.001
   Web of Science ®Google Scholar
• Chen, C., Lee, S., & Shen, Q. (1995). An analytical model for the container loading problem. European Journal of Operational Research, 80(1), 68–76. doi:10.1016/0377-2217(94)00002-T
   Web of Science ®Google Scholar
• Christofides, N., & Whitlock, C. (1977). An algorithm for two-dimensional cutting problems. Operations Research, 25(1), 30–44. doi:10.1287/opre.25.1.30
   Web of Science ®Google Scholar
• Cintra, G., Miyazawa, F., Wakabayashi, Y., & Xavier, E. (2008). Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. European Journal of Operational Research, 191(1), 61– 85. doi:10.1016/j.ejor.2007.08.007
   Web of Science ®Google Scholar
• Côté, J.-F., Dell'Amico, M., & Iori, M. (2014). Combinatorial benders’ cuts for the strip packing problem. Operations Research, 62(3), 643–661. doi:10.1287/opre.2013.1248
   Web of Science ®Google Scholar
• Delorme, M., Iori, M., & Martello, S. (2017). Logic based benders’ decomposition for orthogonal stock cutting problems. Computers & Operations Research, 78, 290–298. doi:10.1016/j.cor.2016.09.009
   Web of Science ®Google Scholar
• Dolan, E. D., & Moré, J. J. (2002). Benchmarking optimization software with performance profiles. Mathematical Programming, 91(2), 201–213. doi:10.1007/s101070100263
   Web of Science ®Google Scholar
• Dolatabadi, M., Lodi, A., & Monaci, M. (2012). Exact algorithms for the two-dimensional guillotine knapsack. Computers & Operations Research, 39(1), 48–53. doi:10.1016/j.cor.2010.12.018
   Web of Science ®Google Scholar
• Dyckhoff, H. (1981). A new linear programming approach to the cutting stock problem. Operations Research, 29(6), 1092–1104. doi:10.1287/opre.29.6.1092
   Web of Science ®Google Scholar
• Dyckhoff, H. (1990). A typology of cutting and packing problems. European Journal of Operational Research, 44(2), 145–159. doi:10.1016/0377-2217(90)90350-K
   Web of Science ®Google Scholar
• Furini, F., & Malaguti, E. (2013). Models for the two-dimensional two-stage cutting stock problem with multiple stock size. Computers & Operations Research, 40(8), 1953– 1962. doi:10.1016/j.cor.2013.02.026
   Web of Science ®Google Scholar
• Furini, F., Malaguti, E., Durán, R. M., Persiani, A., & Toth, P. (2012). A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size. European Journal of Operational Research, 218(1), 251–260. doi:10.1016/j.ejor.2011.10.018
   Web of Science ®Google Scholar
• Furini, F., Malaguti, E., & Thomopulos, D. (2016). Modeling two-dimensional guillotine cutting problems via integer programming. INFORMS Journal on Computing, 28(4), 736–751. doi:10.1287/ijoc.2016.0710
   Web of Science ®Google Scholar
• Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849–859. doi:10.1287/opre.9.6.849
   Web of Science ®Google Scholar
• Gilmore, P. C., & Gomory, R. E. (1963). A linear programming approach to the cutting stock problem-part ii. Operations Research, 11(6), 863–888. doi:10.1287/opre.11.6.863
   Web of Science ®Google Scholar
• Gilmore, P. C., & Gomory, R. E. (1965). Multistage cutting stock problems of two and more dimensions. Operations Research, 13(1), 94–120. doi:10.1287/opre.13.1.94
   Web of Science ®Google Scholar
• Herz, J. C. (1972). Recursive computational procedure for two-dimensional stock cutting. IBM Journal of Research and Development, 16(5), 462–469. doi:10.1147/rd.165.0462
   Web of Science ®Google Scholar
• Hifi, M. (1998). Exact algorithms for the guillotine strip cutting/packing problem. Computers & Operations Research, 25(11), 925–940. doi:https://doi.org/10.1016/S0305-0548(98)00008-2. doi:10.1016/S0305-0548(98)00008-2
   Web of Science ®Google Scholar
• Hopper, E., & Turton, B. C. (2001a). An empirical investigation of meta-heuristic and heuristic algorithms for a 2d packing problem. European Journal of Operational Research, 128(1), 34–57. doi:10.1016/S0377-2217(99)00357-4
   Web of Science ®Google Scholar
• Hopper, E., & Turton, B. C. (2001b). A review of the application of meta-heuristic algorithms to 2d strip packing problems. Artificial Intelligence Review, 16(4), 257–300.
   Web of Science ®Google Scholar
• Kantorovich, L. V. (1960). Mathematical methods of organizing and planning production. Management Science, 6(4), 366–422. doi:10.1287/mnsc.6.4.366
   Web of Science ®Google Scholar
• Lodi, A., Martello, S., & Monaci, M. (2002). Two-dimensional packing problems: A survey. European Journal of Operational Research, 141(2), 241–252. doi:10.1016/S0377-2217(02)00123-6
   Web of Science ®Google Scholar
• Lodi, A., Martello, S., & Vigo, D. (1999). Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS Journal on Computing, 11(4), 345–357. doi:10.1287/ijoc.11.4.345
   Web of Science ®Google Scholar
• Lodi, A., Martello, S., & Vigo, D. (2004). Models and bounds for two-dimensional level packing problems. Journal of Combinatorial Optimization, 8(3), 363–379. doi:10.1023/B:JOCO.0000038915.62826.79
   Web of Science ®Google Scholar
• Lodi, A., & Monaci, M. (2003). Integer linear programming models for 2-staged two-dimensional knapsack problems. Mathematical Programming, 94(2/3), 257–278. doi:10.1007/s10107-002-0319-9
   Web of Science ®Google Scholar
• Macedo, R., Alves, C., & Valério de Carvalho, J. (2010). Arc-flow model for the two-dimensional guillotine cutting stock problem. Computers & Operations Research, 37(6), 991–1001. doi:10.1016/j.cor.2009.08.005
   Web of Science ®Google Scholar
• Martello, S., & Vigo, D. (1998). Exact solution of the two-dimensional finite bin packing problem. Management Science, 44(3), 388–399. doi:10.1287/mnsc.44.3.388
   Web of Science ®Google Scholar
• Morabito, R., & Arenales, M. (2000). Optimizing the cutting of stock plates in a furniture company. International Journal of Production Research, 38(12), 2725–2742. doi:10.1080/002075400411457
   Web of Science ®Google Scholar
• Mrad, M. (2015). An arc flow-based optimization approach for the two-stage guillotine strip cutting problem. Journal of the Operational Research Society, 66(11), 1850–1859. doi:10.1057/jors.2015.8
   Web of Science ®Google Scholar
• Ntene, N., & van Vuuren, J. (2009). A survey and comparison of guillotine heuristics for the 2d oriented offline strip packing problem. Discrete Optimization, 6(2), 174–188. doi:10.1016/j.disopt.2008.11.002
   Web of Science ®Google Scholar
• Oliveira, J. F., Neuenfeldt, A. J., Silva, E., & Carravilla, M. A. (2016). A survey on heuristics for the two-dimensional rectangular strip packing problem. Pesquisa Operacional, 36(2), 197–226. doi:10.1590/0101-7438.2016.036.02.0197
   Google Scholar
• Pisinger, D., & Sigurd, M. (2005). The two-dimensional bin packing problem with variable bin sizes and costs. Discrete Optimization, 2(2), 154– 167. doi:10.1016/j.disopt.2005.01.002
   Google Scholar
• Pisinger, D., & Sigurd, M. (2007). Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. INFORMS Journal on Computing, 19(1), 36–51. doi:10.1287/ijoc.1060.0181
   Web of Science ®Google Scholar
• Puchinger, J., & Raidl, G. R. (2007). Models and algorithms for three-stage two-dimensional bin packing. European Journal of Operational Research, 183(3), 1304– 1327. doi:10.1016/j.ejor.2005.11.064
   Web of Science ®Google Scholar
• Riff, M. C., Bonnaire, X., & Neveu, B. (2009). A revision of recent approaches for two-dimensional strip-packing problems. Engineering Applications of Artificial Intelligence, 22(4/5), 823–827. doi:10.1016/j.engappai.2008.10.025
   Web of Science ®Google Scholar
• Rinaldi, F., & Franz, A. (2007). A two-dimensional strip cutting problem with sequencing constraint. European Journal of Operational Research, 183(3), 1371–1384. doi:10.1016/j.ejor.2005.12.050. doi:10.1016/j.ejor.2005.12.050
   Web of Science ®Google Scholar
• Sawaya, N. W., & Grossmann, I. E. (2005). A cutting plane method for solving linear generalized disjunctive programming problems. Computers & Chemical Engineering, 29(9), 1891–1913. doi:10.1016/j.compchemeng.2005.04.004
   Web of Science ®Google Scholar
• Scheithauer, G. (2002). On a two-dimensional guillotine cutting problem. Presented at IFORS 2002, Edinburgh, UK. [CrossRef
   Google Scholar
• Silva, E., Alvelos, F., & Valério de Carvalho, J. (2010). An integer programming model for two-and three-stage two-dimensional cutting stock problems. European Journal of Operational Research, 205(3), 699–708. doi:10.1016/j.ejor.2010.01.039
   Web of Science ®Google Scholar
• Trespalacios, F., & Grossmann, I. E. (2017). Symmetry breaking for generalized disjunctive programming formulation of the strip packing problem. Annals of Operations Research, 258(2), 747–759. doi:10.1007/s10479-016-2112-9
   Web of Science ®Google Scholar
• Valério de Carvalho, J. (1999). Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research, 86, 629–659.
   Web of Science ®Google Scholar
• Vanderbeck, F. (2001). A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem. Management Science, 47(6), 864–879. doi:10.1287/mnsc.47.6.864.9809
   Web of Science ®Google Scholar
• Wäscher, G., Haußner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, 183(3), 1109–1130. doi:10.1016/j.ejor.2005.12.047
   Web of Science ®Google Scholar
• Westerlund, J., Papageorgiou, L. G., & Westerlund, T. (2007). A milp model for n-dimensional allocation. Computers & Chemical Engineering, 31(12), 1702– 1714. doi:10.1016/j.compchemeng.2007.02.006
   Web of Science ®Google Scholar
• Yanasse, H. H., & Morabito, R. (2006). Linear models for 1-group two-dimensional guillotine cutting problems. International Journal of Production Research, 44(17), 3471–3491. doi:10.1080/00207540500478603
   Web of Science ®Google Scholar
• Yanasse, H. H., & Morabito, R. (2008). A note on linear models for two-group and three-group two-dimensional guillotine cutting problems. International Journal of Production Research, 46(21), 6189–6206. doi:10.1080/00207540601011543
   Web of Science ®Google Scholar