A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting

DOI10.1016/J.EJOR.2009.05.047zbMath1175.90405DBLPjournals/eor/SongCLNT10OpenAlexW2018212883WikidataQ57185717 ScholiaQ57185717MaRDI QIDQ1039779

J. Blot

Publication date: 23 November 2009

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2009.05.047

zbMATH Keywords

dynamic programmingheuristic2D cutting

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Dynamic programming (90C39)

Related Items (2)

A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects ⋮ Enhanced formulation for the Guillotine 2D Cutting knapsack problem

Cites Work

• Unnamed Item
• Two-stage general block patterns for the two-dimensional cutting problem
• Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation
• An approximation algorithm for solving unconstrained two-dimensional knapsack problems
• Cutting stock problems and solution procedures
• An and-or-graph approach for two-dimensional cutting problems
• Packing problems
• Staged and constrained two-dimensional guillotine cutting problems: an AND/OR-graph approach
• The DH/KD algorithm: A hybrid approach for unconstrained two-dimensional cutting problems
• 4-block heuristic for the rectangle packing problem
• An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts
• Integer linear programming models for 2-staged two-dimensional knapsack problems
• A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems.
• A typology of cutting and packing problems
• Two-dimensional packing problems: a survey
• Heuristic and exact algorithms for generating homogeneous constrained three-staged cutting patterns
• Simple block patterns for the two-dimensional cutting problem
• Strip generation algorithms for constrained two-dimensional two-staged cutting problems
• A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting
• An improved typology of cutting and packing problems
• A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem
• A tabu search algorithm for a two-dimensional non-guillotine cutting problem
• A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem
• An efficient approach for large-scale two-dimensional guillotine cutting stock problems
• Two Algorithms for Constrained Two-Dimensional Cutting Stock Problems
• An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure
• Algorithms for Unconstrained Two-Dimensional Guillotine Cutting
• Cutting and Packing Problems: A Categorized, Application-Orientated Research Bibliography
• An Algorithm for Two-Dimensional Cutting Problems
• An Exact Algorithm for Constrained Two-Dimensional Two-Staged Cutting Problems
• The Theory and Computation of Knapsack Functions
• Recursive Computational Procedure for Two-dimensional Stock Cutting
• Exact algorithms for large-scale unconstrained two and three staged cutting problems
• A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems

This page was built for publication: A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting