A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects

DOI10.1007/S00291-014-0363-XzbMath1305.90401OpenAlexW1981367194MaRDI QIDQ480780

Gerhard Wäscher, Ali Niknejad, Mohsen Afsharian

Publication date: 11 December 2014

Published in: OR Spectrum (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00291-014-0363-x

zbMATH Keywords

computational complexitydynamic programmingdefectstwo-dimensional cutting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Dynamic programming (90C39) Discrete location and assignment (90B80)

Related Items (5)

Exact approaches for the unconstrained two-dimensional cutting problem with defects ⋮ A MIP model and a biased random-key genetic algorithm based approach for a two-dimensional cutting problem with defects ⋮ Solving a large cutting problem in the glass manufacturing industry ⋮ One-dimensional stock cutting resilient against singular random defects ⋮ An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem

Uses Software

• SLOPPGEN

Cites Work

• Unnamed Item
• A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem
• A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting
• An approximation algorithm for solving unconstrained two-dimensional knapsack problems
• An and-or-graph approach for two-dimensional cutting problems
• Determining cutting stock patterns when defects are present
• A recursive exact algorithm for weighted two-dimensional cutting
• 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
• Integrated defect detection and optimization for cross cutting of wooden boards
• A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems.
• Dynamic programming and hill-climbing techniques for constrained two-dimensional cutting stock problems
• Cutting rectangles avoiding rectangular defects
• A population heuristic for constrained two-dimensional non-guillotine cutting
• An improved typology of cutting and packing problems
• SLOPPGEN: a problem generator for the two-dimensional rectangular single large object placement problem with defects
• An improved best-first branch-and-bound algorithm for unconstrained two-dimensional cutting problems
• An efficient approach for large-scale two-dimensional guillotine cutting stock problems
• A Linear Programming Approach to the Cutting-Stock Problem
• An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure
• Algorithms for Unconstrained Two-Dimensional Guillotine Cutting
• Guillotine cutting of defective boards
• An Optimum Solution for One-Dimensional Slitting Problems: A Dynamic Programming Approach
• An Algorithm for Two-Dimensional Cutting Problems
• The cutting-wrapping problem in the textile industry: Optimal overlap of fabric lengths and defects for maximizing return based on quality
• A new upper bound for unconstrained two-dimensional cutting and packing
• A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems
• Reducibility among Combinatorial Problems
• Multistage Cutting Stock Problems of Two and More Dimensions
• Two-Dimensional Guillotineable-Layout Cutting Problems with a Single Defect - An AND/OR-Graph Approach
• The Theory and Computation of Knapsack Functions
• Recursive Computational Procedure for Two-dimensional Stock Cutting

This page was built for publication: A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects