Algorithms for Unconstrained Two-Dimensional Guillotine Cutting

DOI10.2307/2582416zbMath0589.90040OpenAlexW4238190594MaRDI QIDQ3718470

John E. Beasley

Publication date: 1985

Published in: The Journal of the Operational Research Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2582416

zbMATH Keywords

heuristiccutting stockComputational resultsunconstrained, two-dimensional, guillotine cutting problem

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Numerical optimization and variational techniques (65K10) Production models (90B30) Dynamic programming (90C39)

Related Items (only showing first 100 items - show all)

An introduction to the two‐dimensional rectangular cutting and packing problem ⋮ Rectangle packing with a recursive pilot method ⋮ Constrained two‐dimensional guillotine cutting problem: upper‐bound review and categorization ⋮ Exact approaches for the unconstrained two-dimensional cutting problem with defects ⋮ MPQ-trees for orthogonal packing problem ⋮ 2DCPackGen: a problem generator for two-dimensional rectangular cutting and packing problems ⋮ Exact algorithm for generating two-segment cutting patterns of punched strips ⋮ On the effectivity of gradient methods for cutting stock problems ⋮ A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang ⋮ Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem ⋮ An iterative bidirectional heuristic placement algorithm for solving the two-dimensional knapsack packing problem ⋮ Practical adaptations of the Gilmore-Gomory approach to cutting stock problems ⋮ An improved typology of cutting and packing problems ⋮ PackLib\(^{2}\): an integrated library of multi-dimensional packing problems ⋮ A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem ⋮ A hybrid genetic algorithm for the two-dimensional single large object placement problem ⋮ An integrated cutting stock and sequencing problem ⋮ Optimising the cutting of wood fibre plates in the hardboard industry ⋮ An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems ⋮ A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem ⋮ Logic based Benders' decomposition for orthogonal stock cutting problems ⋮ An improved skyline based heuristic for the 2D strip packing problem and its efficient implementation ⋮ A simple randomized algorithm for two-dimensional strip packing ⋮ Heuristic for constrained T-shape cutting patterns of rectangular pieces ⋮ Models and algorithms for packing rectangles into the smallest square ⋮ Packing into the smallest square: worst-case analysis of lower bounds ⋮ An improvement of Viswanathan and Bagchi's exact algorithm for constrained two-dimensional cutting stock ⋮ Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem ⋮ A hybrid demon algorithm for the two-dimensional orthogonal strip packing problem ⋮ Combinatorial Benders' Cuts for the Strip Packing Problem ⋮ Two-stage general block patterns for the two-dimensional cutting problem ⋮ An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems ⋮ Exact solutions for constrained two-dimensional cutting problems ⋮ The rectangular two-dimensional strip packing problem real-life practical constraints: a bibliometric overview ⋮ A hybrid GRASP/VND algorithm for two- and three-dimensional bin packing ⋮ A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem ⋮ An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts ⋮ An exact algorithm for general, orthogonal, two-dimensional knapsack problems ⋮ The off-line group seat reservation problem ⋮ An EDA for the 2D knapsack problem with guillotine constraint ⋮ MPQ-trees for the orthogonal packing problem ⋮ A new dynamic programming procedure for three-staged cutting patterns ⋮ An Exact Algorithm for the Two-Dimensional Stage-Unrestricted Guillotine Cutting/Packing Decision Problem ⋮ A skyline heuristic for the 2D rectangular packing and strip packing problems ⋮ The cutting stock problem in a hardboard industry: A case study. ⋮ Exact algorithms for the guillotine strip cutting/packing problem. ⋮ A parallel algorithm for two-staged two-dimensional fixed-orientation cutting problems ⋮ A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems. ⋮ The Meet-in-the-Middle Principle for Cutting and Packing Problems ⋮ Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation ⋮ Exact algorithms for unconstrained three-dimensional cutting problems: A comparative study ⋮ On the two-dimensional knapsack problem ⋮ A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects ⋮ T-shape homogeneous block patterns for the two-dimensional cutting problem ⋮ Cutting stock problems and solution procedures ⋮ Exact and heuristic algorithms for the circle cutting problem in the manufacturing industry of electric motors ⋮ Reactive GRASP for the strip-packing problem ⋮ An enumeration scheme to generate constrained exact checkerboard patterns ⋮ An and-or-graph approach for two-dimensional cutting problems ⋮ Improved state space relaxation for constrained two-dimensional guillotine cutting problems ⋮ Simple block patterns for the two-dimensional cutting problem ⋮ Composite stock cutting through simulated annealing ⋮ Packing problems ⋮ Heuristic approaches for the two- and three-dimensional knapsack packing problem ⋮ Fast heuristic for constrained homogenous T-shape cutting patterns ⋮ Comparative analysis of pattern-based models for the two-dimensional two-stage guillotine cutting stock problem ⋮ Exact algorithms for the two-dimensional guillotine knapsack ⋮ A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem ⋮ Algorithms for 3D guillotine cutting problems: unbounded knapsack, cutting stock and strip packing ⋮ Consecutive ones matrices for multi-dimensional orthogonal packing problems ⋮ Strip generation algorithms for constrained two-dimensional two-staged cutting problems ⋮ Bidirectional best-fit heuristic for orthogonal rectangular strip packing ⋮ Grids for cutting and packing problems: a study in the 2D knapsack problem ⋮ Exact solution techniques for two-dimensional cutting and packing ⋮ A bidirectional building approach for the 2D constrained guillotine knapsack packing problem ⋮ A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems ⋮ Consecutive ones matrices for multi-dimensional orthogonal packing problems ⋮ An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem ⋮ Two-stage two-dimensional guillotine cutting stock problems with usable leftover ⋮ SLOPPGEN: a problem generator for the two-dimensional rectangular single large object placement problem with defects ⋮ The maximum diversity assortment selection problem ⋮ Heurísticas para os problemas de geração e sequenciamento de padrões de corte bidimensionais ⋮ Pattern-based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers ⋮ Approximation algorithm for the oriented two-dimensional bin packing problem ⋮ A survey and comparison of guillotine heuristics for the 2D oriented offline strip packing problem ⋮ A branch and bound algorithm for the strip packing problem ⋮ An open space based heuristic for the 2D strip packing problem with unloading constraints ⋮ The solution of two-stage guillotine cutting stock problems having extremely varying order demands ⋮ A recursive exact algorithm for weighted two-dimensional cutting ⋮ Staged and constrained two-dimensional guillotine cutting problems: an AND/OR-graph approach ⋮ A recursive algorithm for constrained two-dimensional cutting problems ⋮ Using GPU Computing for Solving the Two-Dimensional Guillotine Cutting Problem ⋮ The DH/KD algorithm: A hybrid approach for unconstrained two-dimensional cutting problems ⋮ Heuristic methods and applications: A categorized survey ⋮ A genetic algorithm for the two-dimensional knapsack problem with rectangular pieces ⋮ A hybrid metaheuristic for the two-dimensional strip packing problem ⋮ Knowledge-based systems for cutting stock problems ⋮ Selection of stockplate characteristics and cutting style for two dimensional cutting stock situations ⋮ A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting ⋮ Enhanced formulation for the Guillotine 2D Cutting knapsack problem

This page was built for publication: Algorithms for Unconstrained Two-Dimensional Guillotine Cutting