An Algorithm for Two-Dimensional Cutting Problems

DOI10.1287/opre.25.1.30zbMath0369.90059OpenAlexW2018182024MaRDI QIDQ4146535

Charles Whitlock, Nicos Christofides

Publication date: 1977

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

Full work available at URL: https://semanticscholar.org/paper/12f869c7f7da3e50986aee99963555f02d26c8f2

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Applications of mathematical programming (90C90) Integer programming (90C10) Search theory (90B40) Hamilton-Jacobi theories (49L99)

Related Items

An iterative bidirectional heuristic placement algorithm for solving the two-dimensional knapsack packing problem, Heuristic and exact algorithms for generating homogeneous constrained three-staged cutting patterns, Solving the pallet loading problem, 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, A tabu search algorithm for a two-dimensional non-guillotine cutting problem, The one dimensional Compartmentalised Knapsack problem: a case study, A new exact method for the two-dimensional orthogonal packing problem, A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem, An integrated cutting stock and sequencing problem, Optimising the cutting of wood fibre plates in the hardboard industry, Combinatorial Benders' Cuts for the Strip Packing Problem, Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem, An approach to two-dimensional cutting stock problems, The rectangular two-dimensional strip packing problem real-life practical constraints: a bibliometric overview, An EDA for the 2D knapsack problem with guillotine constraint, An introduction to the two‐dimensional rectangular cutting and packing problem, Rectangle packing with a recursive pilot method, 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, Exact approaches for the unconstrained two-dimensional cutting problem with defects, A NEW HEURISTIC ALGORITHM FOR CONSTRAINED RECTANGLE-PACKING PROBLEM, A nonlinear optimization model for the balanced vehicle routing problem with loading constraints, One-dimensional stock cutting resilient against singular random defects, An Exact Algorithm for the Two-Dimensional Stage-Unrestricted Guillotine Cutting/Packing Decision Problem, Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming, The Meet-in-the-Middle Principle for Cutting and Packing Problems, A new constraint programming approach for the orthogonal packing problem, HEURISTICS WITH STOCHASTIC NEIGHBORHOOD STRUCTURES FOR TWO-DIMENSIONAL BIN PACKING AND CUTTING STOCK PROBLEMS, An enumeration scheme to generate constrained exact checkerboard patterns, Consecutive ones matrices for multi-dimensional orthogonal packing problems, Strip generation algorithms for constrained two-dimensional two-staged cutting problems, The pallet packing problem for non-uniform box sizes, A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems, Heuristics for packing semifluids, Consecutive ones matrices for multi-dimensional orthogonal packing problems, An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem, The pallet loading problem: a review of solution methods and computational experiments, SLOPPGEN: a problem generator for the two-dimensional rectangular single large object placement problem with defects, A mixed integer programming formulation for the three-dimensional bin packing problem deriving from an air cargo application, A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem, The exact solutions of several types of container loading problems, An open space based heuristic for the 2D strip packing problem with unloading constraints, Using GPU Computing for Solving the Two-Dimensional Guillotine Cutting Problem, A genetic algorithm for the two-dimensional knapsack problem with rectangular pieces, Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems, Improved flow-based formulations for the skiving stock problem, 3-D container packing heuristics, An optimization model for the vehicle routing problem with practical three-dimensional loading constraints, Sequential design with applications to the trim-loss problem, Generating optimal two-section cutting patterns for rectangular blanks, Optimization Models for the Three-Dimensional Container Loading Problem with Practical Constraints, A population heuristic for constrained two-dimensional non-guillotine cutting, Logistic constraints in container loading problems: the impact of complete shipment conditions, A block-based layer building approach for the 2D guillotine strip packing problem, On the effectivity of gradient methods for cutting stock problems, A hybrid evolutionary algorithm for the two-dimensional packing problem, A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang, A hybrid algorithm based on variable neighbourhood for the strip packing problem, Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem, The nesting problem in the leather manufacturing industry, Practical adaptations of the Gilmore-Gomory approach to cutting stock problems, An exact algorithm for generating homogeneous T-shape cutting patterns, An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems, An effective tabu search approach with improved loading algorithms for the 3L-CVRP, 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, Models and algorithms for packing rectangles into the smallest square, 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, The computer as an aid to physical distribution management, Corner occupying theorem for the two-dimensional integral rectangle packing problem, A hybrid demon algorithm for the two-dimensional orthogonal strip packing problem, Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem, An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems, An approximation algorithm for solving unconstrained two-dimensional knapsack problems, Exact solutions for constrained two-dimensional cutting problems, An analytical model for the container loading problem, Bun splitting: a practical cutting stock problem, 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, The trim-loss and assortment problems: A survey, 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 best-first branch and bound algorithm for unconstrained two-dimensional cutting problems., Improving the efficiency of a best-first bottom-up approach for the constrained 2D cutting problem, Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines, A linear optimization approach to the combined production planning model, A recursive branch-and-bound algorithm for constrained homogeneous T-shape cutting patterns, 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, Approximate algorithms for constrained circular cutting problems, On the two-dimensional knapsack problem, A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects, Rectangle blanket problem: binary integer linear programming formulation and solution algorithms, Reactive GRASP for the strip-packing problem, Two-dimensional knapsack-block packing problem, An and-or-graph approach for two-dimensional cutting problems, Improved state space relaxation for constrained two-dimensional guillotine cutting problems, Composite stock cutting through simulated annealing, Limiting the number of each piece in two-dimensional cutting stock patterns, Knowledge based approach to the cutting stock problem, Packing problems, A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems, Heuristic approaches for the two- and three-dimensional knapsack packing problem, Fast heuristic for constrained homogenous T-shape cutting patterns, MIP-based approaches for the container loading problem with multi-drop constraints, Exact algorithms for the two-dimensional guillotine knapsack, A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem, Three-dimensional container loading models with cargo stability and load bearing constraints, An efficient deterministic heuristic for two-dimensional rectangular packing, Recent advances on two-dimensional bin packing problems, Multi-dimensional bin packing problems with guillotine constraints, A branch-and-cut algorithm for the pallet loading problem, Grids for cutting and packing problems: a study in the 2D knapsack problem, Exact solution techniques for two-dimensional cutting and packing, Computing stable loads for pallets, Classification and literature review of integrated lot-sizing and cutting stock problems, A bidirectional building approach for the 2D constrained guillotine knapsack packing problem, Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows, The maximum diversity assortment selection problem, 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, Solution for the constrained Guillotine cutting problem by simulated annealing, Stock cutting to minimize cutting length, Lumber production optimization, An exact algorithm for the pallet loading problem, 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, The DH/KD algorithm: A hybrid approach for unconstrained two-dimensional cutting problems, A hybrid metaheuristic for the two-dimensional strip packing problem, An improved version of Wang's algorithm for two-dimensional cutting problems, Selection of stockplate characteristics and cutting style for two dimensional cutting stock situations, Optimal solutions for the cutting stock problem, Load planning for shipments of low density products, Metaheuristics for vehicle routing problems with three-dimensional loading constraints, A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting, New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems, Trim-loss pattern rearrangement and its relevance to the flat-glass industry, Network flows and non-guillotine cutting patterns, Fixed charge problems with identical fixed charges, Enhanced formulation for the Guillotine 2D Cutting knapsack problem, An algorithm for the 2D guillotine cutting stock problem, 2DPackLib: a two-dimensional cutting and packing library