A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem

DOI10.1007/s10479-008-0457-4zbMath1201.90174OpenAlexW1969732427WikidataQ57719493 ScholiaQ57719493MaRDI QIDQ610985

Reinaldo Morabito, Vitória Pureza

Publication date: 13 December 2010

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-008-0457-4

zbMATH Keywords

heuristicsdynamic programmingand/or-graph searchconstrained two-dimensional guillotine cutting patternscutting and packing problems

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (19)

Solving the 3-staged 2-dimensional cutting stock problem by dynamic programming and variable neighborhood search ⋮ And/or-convexity: a graph convexity based on processes and deadlock models ⋮ Tractability, hardness, and kernelization lower bound for and/or graph solution ⋮ Revisiting the complexity of and/or graph solution ⋮ An MIP-CP based approach for two- and three-dimensional cutting problems with staged guillotine cuts ⋮ An introduction to the two‐dimensional rectangular cutting and packing problem ⋮ Models for the two‐dimensional rectangular single large placement problem with guillotine cuts and constrained pattern ⋮ Constrained two‐dimensional guillotine cutting problem: upper‐bound review and categorization ⋮ An Exact Algorithm for the Two-Dimensional Stage-Unrestricted Guillotine Cutting/Packing Decision Problem ⋮ A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects ⋮ Improved state space relaxation for constrained two-dimensional guillotine cutting problems ⋮ Fast heuristic for constrained homogenous T-shape cutting patterns ⋮ Exact solution techniques for two-dimensional cutting and packing ⋮ A bidirectional building approach for the 2D constrained guillotine knapsack packing problem ⋮ Two-stage two-dimensional guillotine cutting stock problems with usable leftover ⋮ A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem ⋮ Unnamed Item ⋮ Strip based compact formulation for two-dimensional guillotine cutting problems ⋮ 2DPackLib: a two-dimensional cutting and packing library

Cites Work

• Unnamed Item
• Unnamed Item
• Exact solutions for constrained two-dimensional cutting problems
• An and-or-graph approach for two-dimensional cutting problems
• Packing problems
• Solution for the constrained Guillotine cutting problem by simulated annealing
• 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
• An improvement of Viswanathan and Bagchi's exact algorithm for constrained two-dimensional cutting stock
• An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts
• A comparative numerical analysis for the guillotine two-dimensional cutting problem
• Dynamic programming and hill-climbing techniques for constrained two-dimensional cutting stock problems
• An improved version of Wang's algorithm for two-dimensional cutting problems
• A typology of cutting and packing problems
• Two-dimensional packing problems: a survey
• A new exact algorithm for the vehicle routing problem based on \(q\)-paths and \(k\)-shortest paths relaxations
• Heuristic and exact algorithms for generating homogeneous constrained three-staged cutting patterns
• Lower bounds from state space relaxations for concave cost network flow problems
• Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems
• An improved typology of cutting and packing problems
• An efficient approach for large-scale two-dimensional guillotine cutting stock problems
• Two Algorithms for Constrained Two-Dimensional Cutting Stock Problems
• Algorithms for Unconstrained Two-Dimensional Guillotine Cutting
• State-space relaxation procedures for the computation of bounds to routing problems
• Cutting and Packing Problems: A Categorized, Application-Orientated Research Bibliography
• An Algorithm for Two-Dimensional Cutting Problems
• Best-First Search Methods for Constrained Two-Dimensional Cutting Stock Problems
• An AND/OR-graph approach to the container loading problem
• A New Placement Heuristic for the Orthogonal Stock-Cutting Problem
• The Theory and Computation of Knapsack Functions
• A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems

This page was built for publication: A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem