A general heuristic for two-dimensional nesting problems with limited-size containers

References

• Alvarez-Valdes, R., A. Martinez, and J. M. Tamarit. 2013. “A Branch & Bound Algorithm for Cutting and Packing Irregularly Shaped Pieces.” International Journal of Production Economics 145 (2): 463–477.
   Web of Science ®Google Scholar
• Armas, J. D., C. León, G. Miranda, and C. Segura. 2010. “Optimisation of a Multi-objective Two-dimensional Strip Packing Problem Based on Evolutionary Algorithms.” International Journal of Production Research 48 (7): 2011–2028.
   Web of Science ®Google Scholar
• Bennell, J. A., and X. Song. 2010. “A Beam Search Implementation for the Irregular Shape Packing Problem.” Journal of Heuristics 16: 167–188.
   Web of Science ®Google Scholar
• Bennell, J. A., and J. F. Oliveira. 2008. “The Geometry of Nesting Problems: A Tutorial.” European Journal of Operational Research 184 (2): 397–415.
   Web of Science ®Google Scholar
• Birgin, E. G., and E. D. Lobato. 2010. “Orthogonal Packing of Identical Rectangles Within Isotropic Convex Regions.” Computers & Industrial Engineering 59 (4): 595–602.
   Web of Science ®Google Scholar
• Cherri, Luiz H., Leandro R. Mundim, Marina Andretta, Franklina M. B. Toledo, José F. Oliveira, and Maria Antónia Carravilla. 2016. “Robust Mixed-integer Linear Programming Models for the Irregular Strip Packing Problem.” European Journal of Operational Research 253 (3): 570–583. http://www.sciencedirect.com/science/article/pii/S0377221716301370.
   Web of Science ®Google Scholar
• Cintra, G. F., F. K. Miyazawa, Y. Wakabayashi, and E. C. Xavier. 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.
   Web of Science ®Google Scholar
• Dagli, C. H., and M. Y. Tatoglu. 1987. “An Approach to Two-dimensional Cutting Stock Problems.” International Journal of Production Research 25 (2): 175–190.
   Web of Science ®Google Scholar
• Dalalah, D., S. Khrais, and K. Bataineh. 2014. “Waste Minimization in Irregular Stock Cutting.” Journal of Manufacturing Systems 33 (1): 27–40.
   Web of Science ®Google Scholar
• Dighe, R., and M. J. Jakiela. 1996. “Solving Pattern Nesting Problems with Genetic Algorithms Employing Task Decomposition and Contact Detection.” Evolutionary Computation 3: 239–266.
   Web of Science ®Google Scholar
• Fischetti, M., and I. Luzzi. 2009. “Mixed-integer Programming Models for Nesting Problems.” Journal of Heuristics 15 (3): 201–226.
   Web of Science ®Google Scholar
• Gilmore, P. C., and R. E. Gomory. 1961. “A Linear Programming Approach to the Cutting-Stock Problem.” Operations Research 9 (6): 849–859.
   Web of Science ®Google Scholar
• Gilmore, P. C., and R. E. Gomory. 1963. “A Linear Programming Approach to the Cutting-Stock Problem, Part II.” Operations Research 11: 863–888.
   Web of Science ®Google Scholar
• Gomes, M. A., and J. F. Oliveira. 2006. “Solving Irregular Strip Packing Problems by Hybridising Simulated Annealing and Linear Programming.” European Journal of Operational Research 171 (3): 811–829. Feature Cluster: Heuristic and Stochastic Methods in OptimizationFeature Cluster: New Opportunities for Operations Research.
   Web of Science ®Google Scholar
• Hu, Y., H. Hashimoto, S. Imahori, and M. Yagiura. 2015. “Efficient Implementations of Construction Heuristics for the Rectilinear Block Packing Problem.” Computers & Operations Research 53: 206–222.
   Web of Science ®Google Scholar
• Ismail, H. S., and K. K. B. Hon. 1992. “New Approaches for the Nesting of Two-dimensional Shapes for Press Tool Design.” International Journal of Production Research 30 (4): 825–837.
   Web of Science ®Google Scholar
• Kang, M., and K. Yoon. 2011. “An Improved Best-first Branch-and-bound Algorithm for Unconstrained Two-dimensional Cutting Problems.” International Journal of Production Research 49 (15): 4437–4455.
   Web of Science ®Google Scholar
• Kos, L., and J. Duhovnik. 2002. “Cutting Optimization with Variable-sized Stock and Inventory Status Data.” International Journal of Production Research 40 (10): 2289–2301.
   Web of Science ®Google Scholar
• Leão, A. A. S., F. M. B. Toledo, J. F. Oliveira, and M. A. Carravilla. 2016. “A Semi-continuous MIP Model for the Irregular Strip Packing Problem.” International Journal of Production Research 54 (3): 712–721.
   Web of Science ®Google Scholar
• Liu, Y., C. Chu, and K. Wang. 2011. “A Dynamic Programming-based Heuristic for the Variable Sized Two-dimensional Bin Packing Problem.” International Journal of Production Research 49 (13): 3815–3831.
   Web of Science ®Google Scholar
• Liu, Y., C. Chu, and Y. Yu. 2012. “Aggregated State Dynamic Programming for a Multiobjective Two-dimensional Bin Packing Problem.” International Journal of Production Research 50 (15): 4316–4325.
   Web of Science ®Google Scholar
• López-Camacho, E., H. Terashima-Marin, P. Ross, and G. Ochoa. 2014. “A Unified Hyper-heuristic Framework for Solving Bin Packing Problems.” Expert Systems with Applications 41 (15): 6876–6889.
   Web of Science ®Google Scholar
• López-Camacho, Eunice, Gabriela Ochoa, Hugo Terashima-Mar\’{\i}n, and EdmundK Burke . 2013. “An Effective Heuristic for the Two-dimensional Irregular Bin Packing Problem.” Annals of Operations Research 206 (1): 241–264.
   Web of Science ®Google Scholar
• Martinez-Sykora, A., R. Alvarez-Valdes, J. Bennell, R. Ruiz, and J. M. Tamarit. 2016. “Matheuristics for the Irregular Bin Packing Problem with Free Rotations.” European Journal of Operational Research 258 (2): 440–455.
   Web of Science ®Google Scholar
• Martins, T. C., and M. S. G. Tsuzuki. 2010. “Simulated Annealing Applied to the Irregular Rotational Placement of Shapes Over Containers with Fixed Dimensions.” Expert Systems with Applications 37 (3): 1955–1972.
   Web of Science ®Google Scholar
• MirHassani, S. A., and A. Jalaeian Bashirzadeh. 2015. “A GRASP Meta-heuristic for Two-dimensional Irregular Cutting Stock Problem.” The International Journal of Advanced Manufacturing Technology 81 (1–4): 455–464.
   Web of Science ®Google Scholar
• Mundim, Leandro R., Marina Andretta, and Thiago Alves de Queiroz. 2017. “A Biased Random Key Genetic Algorithm for Open Dimension Nesting Problems Using No-fit Raster.” Expert Systems with Applications 81: 358–371. http://www.sciencedirect.com/science/article/pii/S0957417417302233.
   Web of Science ®Google Scholar
• Rodrigues, Marcos Okamura, and Franklina M. B. Toledo. 2017. “A Clique Covering MIP Model for the Irregular Strip Packing Problem.” Computers & Operations Research 87 (Supplement C): 221–234. http://www.sciencedirect.com/science/article/pii/S0305054816302702.
   Web of Science ®Google Scholar
• Ross, P., S. Schulenburg, J. G. Marín-Blázquez, and E. Hart. 2002. “Hyper-heuristics: Learning To Combine Simple Heuristics in Bin-packing Problems.” In Proceedings of the Genetic and Evolutionary Computation Conference GECCO’02, San Francisco, CA, USA, 942–948. Morgan Kaufmann Publishers Inc.
   Google Scholar
• Song, X., and J. A. Bennell. 2014. “Column Generation and Sequential Heuristic Procedure.” Journal of the Operational Research Society 65 (7): 1037–1052.
   Web of Science ®Google Scholar
• Terashima-Marín, H., P. Ross, C. J. Farías-Zárate, E. López-Camacho, and M. Valenzuela-Rendón. 2010. “Generalized Hyper-heuristics for Solving 2D Regular and Irregular Packing Problems.” Annals of Operations Research 179 (1): 369–392.
   Web of Science ®Google Scholar
• Toledo, F. M. B., M. A. Carravilla, Cristina Ribeiro, J. F. Oliveira, and M. A. Gomes. 2013. “The Dotted-Board Model: A new MIP Model for Nesting Irregular Shapes.” International Journal of Production Economics 145 (2): 478–487.
   Web of Science ®Google Scholar
• Valle, A. M., T. A. Del, F. K. Miyazawa Queiroz, and E. C. Xavier. 2012. “Heuristics for Two-dimensional Knapsack and Cutting Stock Problems with Items of Irregular Shape.” Expert Systems with Applications 39 (16): 12589–12598.
   Web of Science ®Google Scholar
• Vasantha, G. V. A., A. P. Jagadeesan, J. R. Corney, A. Lynn, and A. Agrawal. 2016. “Crowdsourcing Solutions to 2D Irregular Strip Packing Problems from Internet Workers.” International Journal of Production Research 54 (14): 4104–4125.
   Web of Science ®Google Scholar
• Wang, Y., R. Xiao, and H. Wang. 2017. “A Flexible Labour Division Approach to the Polygon Packing Problem Based on Space Allocation.” International Journal of Production Research 55 (11): 3025–3045.
   Web of Science ®Google Scholar
• Wäscher, G., H. Haußner, and H. Schumann. 2007. “An Improved Typology of Cutting and Packing Problems.” European Journal of Operational Research 183 (3): 1109–1130.
   Web of Science ®Google Scholar
• Wu, Tai-Hsi, Jeng-Fung Chen, Chinyao Low, and Pang-Ting Tang. 2003. “Nesting of Two-dimensional Parts in Multiple Plates Using Hybrid Algorithm.” International Journal of Production Research 41 (16): 3883–3900.
   Web of Science ®Google Scholar
• Yanasse, H. H., and R. Morabito. 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.
   Web of Science ®Google Scholar