The DH/KD algorithm: A hybrid approach for unconstrained two-dimensional cutting problems

DOI10.1016/S0377-2217(96)00060-4zbMath0929.90073OpenAlexW2160776415WikidataQ127613595 ScholiaQ127613595MaRDI QIDQ1278579

Mhand Hifi

Publication date: 22 February 1999

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

Full work available at URL: https://doi.org/10.1016/s0377-2217(96)00060-4

zbMATH Keywords

dynamic programmingdepth-first searchhill-climbingone-dimensional knapsackweighted and unweighted unconstrained two-dimensional guillotine cutting

Mathematics Subject Classification ID

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

Related Items (19)

An integrated cutting stock and sequencing problem ⋮ A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem ⋮ An improvement of Viswanathan and Bagchi's exact algorithm for constrained two-dimensional cutting stock ⋮ Two-stage general block patterns for the two-dimensional cutting problem ⋮ A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem ⋮ Exact approaches for the unconstrained two-dimensional cutting problem with defects ⋮ The cutting stock problem in a hardboard industry: A case study. ⋮ An improved best-first branch-and-bound algorithm for unconstrained two-dimensional cutting problems ⋮ Exact algorithms for unconstrained three-dimensional cutting problems: A comparative study ⋮ A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects ⋮ Strip generation algorithms for constrained two-dimensional two-staged cutting problems ⋮ A note on linear models for two-group and three-group two-dimensional guillotine cutting problems ⋮ A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems ⋮ Two-stage two-dimensional guillotine cutting stock problems with usable leftover ⋮ Heurísticas para os problemas de geração e sequenciamento de padrões de corte bidimensionais ⋮ Hybrid greedy heuristics based on linear programming for the three‐dimensional single bin‐size bin packing problem ⋮ Linear models for 1-group two-dimensional guillotine cutting problems ⋮ A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting ⋮ Generating optimal two-section cutting patterns for rectangular blanks

Cites Work

• Unnamed Item
• Unnamed Item
• An approximation algorithm for solving unconstrained two-dimensional knapsack problems
• Dynamic programming algorithms for the zero-one knapsack problem
• An and-or-graph approach for two-dimensional cutting problems
• Pipeline architectures for dynamic programming algorithms
• An improved version of Wang's algorithm for two-dimensional cutting problems
• Mathematical Methods of Organizing and Planning Production
• 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
• Nonorthogonal Two-Dimensional Cutting Patterns
• An Algorithm for Two-Dimensional Cutting Problems
• Best-First Search Methods for Constrained Two-Dimensional Cutting Stock Problems
• Multistage Cutting Stock Problems of Two and More Dimensions
• The Theory and Computation of Knapsack Functions
• Recursive Computational Procedure for Two-dimensional Stock Cutting

This page was built for publication: The DH/KD algorithm: A hybrid approach for unconstrained two-dimensional cutting problems