A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
From MaRDI portal
Publication:2757657
DOI10.1287/moor.25.4.645.12118zbMath0977.90043OpenAlexW2060963575MaRDI QIDQ2757657
Publication date: 26 November 2001
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/543feea9e06ad188e9d4eef2c42a906f437ec2a9
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items (67)
A Fast Approximation Scheme for the Multiple Knapsack Problem ⋮ Rectangle packing with one-dimensional resource augmentation ⋮ Strip packing with precedence constraints and strip packing with release times ⋮ Approximate strip packing: revisited ⋮ APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS ⋮ Approximating Smallest Containers for Packing Three-Dimensional Convex Objects ⋮ A new lower bound for online strip packing ⋮ Two for One: Tight Approximation of 2D Bin Packing ⋮ Polynomial-time approximation schemes for circle and other packing problems ⋮ Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Combinatorial Benders' Cuts for the Strip Packing Problem ⋮ iGreen: green scheduling for peak demand minimization ⋮ A faster FPTAS for the unbounded knapsack problem ⋮ The rectangular two-dimensional strip packing problem real-life practical constraints: a bibliometric overview ⋮ A \((5/3+\varepsilon)\)-approximation for strip packing ⋮ Redundant cumulative constraints to compute preemptive bounds ⋮ A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing ⋮ Peak demand minimization via sliced strip packing ⋮ On contiguous and non-contiguous parallel task scheduling ⋮ A Polynomial Time Approximation Scheme for the Square Packing Problem ⋮ An improved approximation algorithm for scheduling monotonic moldable tasks ⋮ High multiplicity strip packing with three rectangle types ⋮ Unnamed Item ⋮ Packing Rectangles into 2OPT Bins Using Rotations ⋮ An effective approximation algorithm for the malleable parallel task scheduling problem ⋮ Corner cuts are close to optimal: from solid grids to polygons and back ⋮ Absolute approximation ratios for packing rectangles into bins ⋮ A family of heuristic-based inequalities for maximizing overall safety margins in aircraft parking stands arrangement problems ⋮ A hierarchical approach for solving an integrated packing and sequence-optimization problem in production of glued laminated timber ⋮ Two-dimensional packing with conflicts ⋮ Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation ⋮ Asymptotically optimal scheduling of random malleable demands in smart grid ⋮ A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem ⋮ Large gaps in one-dimensional cutting stock problems ⋮ Parameterized complexity of strip packing and minimum volume packing ⋮ Two-dimensional bin packing with one-dimensional resource augmentation ⋮ On Guillotine Separability of Squares and Rectangles. ⋮ A Tight (3/2+ε) Approximation for Skewed Strip Packing. ⋮ New upper bounds for online strip packing ⋮ Commitment under uncertainty: Two-stage stochastic matching problems ⋮ TWO FOR ONE: TIGHT APPROXIMATION OF 2D BIN PACKING ⋮ Algorithms for 3D guillotine cutting problems: unbounded knapsack, cutting stock and strip packing ⋮ Recent advances on two-dimensional bin packing problems ⋮ A 3-approximation algorithm for two-dimensional bin packing ⋮ An approximation algorithm for the general max-min resource sharing problem ⋮ The two-dimensional cutting stock problem revisited ⋮ Improved approximation for two dimensional strip packing with polynomial bounded width ⋮ Online strip packing with modifiable boxes ⋮ On-line algorithms for packing rectangles into several strips ⋮ Complexity and inapproximability results for parallel task scheduling and strip packing ⋮ The best-fit heuristic for the rectangular strip packing problem: An efficient implementation and the worst-case approximation ratio ⋮ Closing the Gap for Pseudo-Polynomial Strip Packing ⋮ A survey and comparison of guillotine heuristics for the 2D oriented offline strip packing problem ⋮ Three-dimensional packings with rotations ⋮ Approximation Schemes for Machine Scheduling with Resource (In-)dependent Processing Times ⋮ A Survey on Approximation Algorithms for Scheduling with Machine Unavailability ⋮ Hardness of approximation for orthogonal rectangle packing and covering problems ⋮ A note on the Kenyon-Remila strip-packing algorithm ⋮ A branch-and-price algorithm for the two-dimensional level strip packing problem ⋮ Approximation algorithms for orthogonal packing problems for hypercubes ⋮ Probabilistic analysis of shelf algorithms for strip packing ⋮ Approximate algorithms to pack rectangles into several strips ⋮ PACKING SOFT RECTANGLES ⋮ Two-dimensional packing problems: a survey ⋮ Resource augmentation in two-dimensional packing with orthogonal rotations ⋮ New approximability results for two-dimensional bin packing
This page was built for publication: A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
