An Exact Algorithm for the Two-Dimensional Stage-Unrestricted Guillotine Cutting/Packing Decision Problem

References

• Alvarez-Valdes R, Parreno F, Tamarit JM (2009) A branch and bound algorithm for the strip packing problem. OR Spectrum 31(2):431–459.Crossref, Google Scholar
• Amossen RR, Pisinger D (2010) Multi-dimensional bin packing problems with guillotine constraints. Comput. Oper. Res. 37(11):1999–2006.Crossref, Google Scholar
• Beasley J (1985a) Algorithms for unconstrained two-dimensional guillotine cutting. J. Oper. Res. Soc. 36(4):297–306.Crossref, Google Scholar
• Beasley JE (1985b) An exact two-dimensional non-guillotine cutting tree search procedure. Oper. Res. 33(1):49–64.Link, Google Scholar
• Bekrar A, Kacem I, Chu C, Sadfi C (2010) An improved heuristic and an exact algorithm for the 2d strip and bin packing problem. Internat. J. Product Development 10(1):217–240.Crossref, Google Scholar
• Bengtsson BE (1982) Packing rectangular pieces—A heuristic approach. Comput. J. 25(3):353–357.Crossref, Google Scholar
• Berkey JO, Wang PY (1987) Two-dimensional finite bin-packing algorithms. J. Oper. Res. Soc. 38(5):423–429.Crossref, Google Scholar
• Boschetti MA, Montaletti L (2010) An exact algorithm for the two-dimensional strip-packing problem. Oper. Res. 58(6):1774–1791.Link, Google Scholar
• Burke EK, Kendall G, Whitwell G (2004) A new placement heuristic for the orthogonal stock-cutting problem. Oper. Res. 52(4):655–671.Link, Google Scholar
• Christofides N, Hadjiconstantinou E (1995) An exact algorithm for orthogonal 2-d cutting problems using guillotine cuts. Eur. J. Oper. Res. 83(1):21–38.Crossref, Google Scholar
• Christofides N, Whitlock C (1977) An algorithm for two-dimensional cutting problems. Oper. Res. 25(1):30–44.Link, Google Scholar
• Clautiaux F, Carlier J, Moukrim A (2007) A new exact method for the two-dimensional orthogonal packing problem. Eur. J. Oper. Res. 183(3):1196–1211.Crossref, Google Scholar
• Clautiaux F, Jouglet A, Moukrim A (2013) A new graph-theoretical model for the guillotine-cutting problem. INFORMS J. Comput. 25(1):72–86.Link, Google Scholar
• Clautiaux F, Jouglet A, Carlier J, Moukrim A (2008) A new constraint programming approach for the orthogonal packing problem. Comput. Oper. Res. 35(3):944–959.Crossref, Google Scholar
• Dolatabadi M, Lodi A, Monaci M (2012) Exact algorithms for the two-dimensional guillotine knapsack. Comput. Oper. Res. 39(1):48–53.Crossref, Google Scholar
• Fekete SP, Schepers J (2004) A general framework for bounds for higher-dimensional orthogonal packing problems. Math. Methods Oper. Res. 60(2):311–329.Crossref, Google Scholar
• Fekete SP, Schepers J, van der Veen JC (2007) An exact algorithm for higher-dimensional orthogonal packing. Oper. Res. 55(3):569–587.Link, Google Scholar
• Fleszar K (2013) Three insertion heuristics and a justification improvement heuristic for two-dimensional bin packing with guillotine cuts. Comput. Oper. Res. 40(1):463–474.Crossref, Google Scholar
• Furini F, Malaguti E, Thomopulos D (2016) A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem. INFORMS J. Comput. Forthcoming.Google Scholar
• Hifi M (1997) An improvement of Viswanathan and Bagchi’s exact algorithm for constrained two-dimensional cutting stock. Comput. Oper. Res. 24(8):727–736.Crossref, Google Scholar
• Hifi M (1998) Exact algorithms for the guillotine strip cutting/packing problem. Comput. Oper. Res. 25(11):925–940.Crossref, Google Scholar
• Hopper E, Turton B (2001) An empirical investigation of meta-heuristic and heuristic algorithms for a 2d packing problem. Eur. J. Oper. Res. 128(1):34–57.Crossref, Google Scholar
• Lodi A, Martello S, Vigo D (1998) Neighborhood search algorithm for the guillotine non-oriented two-dimensional bin packing problem. Voss S, Martello S, Osman I, Roucairol C, eds. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (Kluwer Academic Publishers, Boston), 125–139.Google Scholar
• Martello S, Vigo D (1998) Exact solution of the two-dimensional finite bin packing problem. Management Sci. 44(3):388–399.Link, Google Scholar
• Martello S, Monaci M, Vigo D (2003) An exact approach to the strip-packing problem. INFORMS J. Comput. 15(3):310–319.Link, Google Scholar
• Morabito R, Arenales MN (1996) Staged and constrained two-dimensional guillotine cutting problems: An and/or-graph approach. Eur. J. Oper. Res. 94(3):548–560.Crossref, Google Scholar
• Morabito R, Pureza V (2010) A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem. Ann. Oper. Res. 179(1):297–315.Crossref, Google Scholar
• Oliveira J, Ferreira J (1990) An improved version of wang’s algorithm for two-dimensional cutting problems. Eur. J. Oper. Res. 44(2):256–266.Crossref, Google Scholar
• Pisinger D, Sigurd M (2005) The two-dimensional bin packing problem with variable bin sizes and costs. Discrete Optim. 2(2):154–167.Crossref, Google Scholar
• Pisinger D, Sigurd M (2007) Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. INFORMS J. Comput. 19(1):36–51.Link, Google Scholar
• Vasko FJ (1989) A computational improvement to wang’s two-dimensional cutting stock algorithm. Comput. Indust. Engrg. 16(1):109–115.Crossref, Google Scholar
• Viswanathan KV, Bagchi A (1993) Best-first search methods for constrained two-dimensional cutting stock problems. Oper. Res. 41(4):768–776.Link, Google Scholar
• Wang PY (1983) Two algorithms for constrained two-dimensional cutting stock problems. Oper. Res. 31(3):573–586.Link, Google Scholar
• Wäscher G, Haußner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183(3):1109–1130.Crossref, Google Scholar