The best-fit heuristic for the rectangular strip packing problem: An efficient implementation and the worst-case approximation ratio
From MaRDI portal
Publication:732899
DOI10.1016/j.cor.2009.05.008zbMath1175.90429MaRDI QIDQ732899
Mutsunori Yagiura, Shinji Imahori
Publication date: 15 October 2009
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cor.2009.05.008
time complexity; cutting and packing; approximation ratio; best-fit heuristic; rectangular strip packing
90C60: Abstract computational complexity for mathematical programming problems
90C59: Approximation methods and heuristics in mathematical programming
Related Items
An iterative bidirectional heuristic placement algorithm for solving the two-dimensional knapsack packing problem, Rectangle packing with a recursive pilot method, An effective shaking procedure for 2D and 3D strip packing problems, Efficient implementations of construction heuristics for the rectilinear block packing problem, A skyline heuristic for the 2D rectangular packing and strip packing problems, A squeaky wheel optimisation methodology for two-dimensional strip packing, An improved skyline based heuristic for the 2D strip packing problem and its efficient implementation, A two-dimensional heuristic decomposition approach to a three-dimensional multiple container loading problem, Exact solution techniques for two-dimensional cutting and packing, Bidirectional best-fit heuristic for orthogonal rectangular strip packing, The rectangular two-dimensional strip packing problem real-life practical constraints: a bibliometric overview, An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem, Upper bounds for heuristic approaches to the strip packing problem, An improved best-fit heuristic for the orthogonal strip packing problem
Cites Work
- Reactive GRASP for the strip-packing problem
- On genetic algorithms for the packing of polygons
- An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem
- An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles
- A typology of cutting and packing problems
- Improved local search algorithms for the rectangle packing problem with general spatial costs
- A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces
- An improved typology of cutting and packing problems
- A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
- A Simulated Annealing Enhancement of the Best-Fit Heuristic for the Orthogonal Stock-Cutting Problem
- The Bottomn-Left Bin-Packing Heuristic: An Efficient Implementation
- On strip packing With rotations
- Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
- Orthogonal Packings in Two Dimensions
- A Strip-Packing Algorithm with Absolute Performance Bound 2
- Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems
- A New Placement Heuristic for the Orthogonal Stock-Cutting Problem
- Data set generation for rectangular placement problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
