Two-dimensional packing problems: a survey

DOI10.1016/S0377-2217(02)00123-6zbMath1081.90576DBLPjournals/eor/LodiMM02WikidataQ56169156 ScholiaQ56169156MaRDI QIDQ1847188

Andrea Lodi, Michele Monaci, Silvano Martello

Publication date: 17 November 2002

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

zbMATH Keywords

Bin packing problemsStrip packing problemsTwo-dimensional packing

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

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

Optimisation of a multi-objective two-dimensional strip packing problem based on evolutionary algorithms ⋮ Integrated shipment dispatching and packing problems: a case study ⋮ On the Approximability of Orthogonal Order Preserving Layout Adjustment ⋮ Sequential heuristic for the two-dimensional bin-packing problem ⋮ A variable neighborhood descent approach for the two-dimensional bin packing problem ⋮ TS\(^2\)PACK: A two-level tabu search for the three-dimensional bin packing problem ⋮ A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem ⋮ An effective hybrid algorithm for the problem of packing circles into a larger containing circle ⋮ An improved typology of cutting and 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 new exact method for the two-dimensional orthogonal packing problem ⋮ A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem ⋮ Applying self-adaptive evolutionary algorithms to two-dimensional packing problems using a four corners' heuristic ⋮ A dynamic adaptive local search algorithm for the circular packing problem ⋮ An integrated cutting stock and sequencing problem ⋮ A two-dimensional strip cutting problem with sequencing constraint ⋮ Optimising the cutting of wood fibre plates in the hardboard industry ⋮ Exhaustive approaches to 2D rectangular perfect packings ⋮ Arc-flow model for the two-dimensional guillotine cutting stock problem ⋮ An efficient heuristic algorithm for arbitrary shaped rectilinear block packing problem ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Chance-Constrained Multiple Bin Packing Problem with an Application to Operating Room Planning ⋮ Numerical optimization methods for packing equal orthogonally oriented ellipses in a rectangular domain ⋮ Compact integer linear programming formulations for the temporal bin packing problem with fire-ups ⋮ Vehicle routing with private and shared delivery locations ⋮ The rectangular two-dimensional strip packing problem real-life practical constraints: a bibliometric overview ⋮ The bin packing problem with item fragmentation: a worst-case analysis ⋮ Optimizing two-dimensional vehicle loading and dispatching decisions in freight logistics ⋮ Drainage area maximization in unconventional hydrocarbon fields with integer linear programming techniques ⋮ Hybrid heuristic for the production replanning problem under varying demands in manufacturing industries ⋮ An introduction to the two‐dimensional rectangular cutting and packing problem ⋮ Branch‐and‐bound approach for optima localization in scheduling multiprocessor jobs ⋮ Models for the two‐dimensional rectangular single large placement problem with guillotine cuts and constrained pattern ⋮ Mathematical models for the two-dimensional variable-sized cutting stock problem in the home textile industry ⋮ Modeling Two-Dimensional Guillotine Cutting Problems via Integer Programming ⋮ The evolution of rectangular bin packing problem -- a review of research topics, applications, and cited papers ⋮ An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem ⋮ A mathematical modeling approach to optimize composite parts placement in autoclave ⋮ Metaheuristics for truck loading in the car production industry ⋮ Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width ⋮ HEURISTICS WITH STOCHASTIC NEIGHBORHOOD STRUCTURES FOR TWO-DIMENSIONAL BIN PACKING AND CUTTING STOCK PROBLEMS ⋮ Asymptotically optimal scheduling of random malleable demands in smart grid ⋮ Batching-Based Approaches for Optimized Packing of Jobs in the Spatial Scheduling Problem ⋮ An enumeration scheme to generate constrained exact checkerboard patterns ⋮ An optimization algorithm for a penalized knapsack problem ⋮ Two-dimensional bin packing with one-dimensional resource augmentation ⋮ O problema de corte de estoque em indústrias de móveis de pequeno e médio portes ⋮ Efficient algorithms for orthogonal packing problems ⋮ Improved local search algorithms for the rectangle packing problem with general spatial costs ⋮ A 3-approximation algorithm for two-dimensional bin packing ⋮ A new heuristic recursive algorithm for the strip rectangular packing problem ⋮ Unnamed Item ⋮ TOC-based planning and scheduling model ⋮ Orthogonal packing of rectangular items within arbitrary convex regions by nonlinear optimization ⋮ Robust Distributed Query Processing for Streaming Data ⋮ The Two Dimensional Bin Packing Problem with Side Constraints ⋮ A note on linear models for two-group and three-group two-dimensional guillotine cutting problems ⋮ Foldabilizing furniture ⋮ An efficient intelligent search algorithm for the two-dimensional rectangular strip packing problem ⋮ Upper bounds for heuristic approaches to the strip packing problem ⋮ 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 ⋮ New Inequalities for 1D Relaxations of the 2D Rectangular Strip Packing Problem ⋮ Optimisation hybride par colonies de fourmis pour le problème de découpe à deux dimensions ⋮ Hybrid approach for the two-dimensional bin packing problem with two-staged patterns ⋮ New Lower Bound and Exact Method for the Continuous Berth Allocation Problem ⋮ 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 ⋮ Optimal aircraft load balancing ⋮ Some experiments with a simple tabu search algorithm for the manufacturer's pallet loading problem ⋮ Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems ⋮ An efficient deterministic optimization approach for rectangular packing problems ⋮ Linear models for the approximate solution of the problem of packing equal circles into a given domain ⋮ Asynchronous optimization of part logistics routing problem ⋮ Quasi-phi-functions and optimal packing of ellipses ⋮ Compact visualisation of video summaries ⋮ Solving real-world cutting stock-problems in the paper industry: mathematical approaches, experience and challenges ⋮ Constrained order packing: comparison of heuristic approaches for a new bin packing problem ⋮ A hybrid evolutionary algorithm for the two-dimensional packing problem ⋮ New exact approaches and approximation results for the penalized knapsack problem ⋮ A goal-driven ruin and recreate heuristic for the 2D variable-sized bin packing problem with guillotine constraints ⋮ 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 ⋮ Provider selection and task allocation in telecommunications with QoS degradation policy ⋮ A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints ⋮ Adaptive simulated annealing with greedy search for the circle bin packing problem ⋮ The vehicle routing problem with simultaneous pick-ups and deliveries and two-dimensional loading constraints ⋮ Bin packing and cutting stock problems: mathematical models and exact algorithms ⋮ Models for the two-dimensional two-stage cutting stock problem with multiple stock size ⋮ An effective shaking procedure for 2D and 3D strip packing problems ⋮ An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems ⋮ Logic based Benders' decomposition for orthogonal stock cutting problems ⋮ Fast machine reassignment ⋮ Scheduling under the network of temporo-spatial proximity relationships ⋮ Packing unequal rectangles and squares in a fixed size circular container using formulation space search ⋮ Combined cutting stock and lot-sizing problem with pattern setup ⋮ A simple randomized algorithm for two-dimensional strip packing ⋮ Three insertion heuristics and a justification improvement heuristic for two-dimensional bin packing with guillotine cuts ⋮ An exact strip packing algorithm based on canonical forms

Uses Software

• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hybrid next-fit algorithm for the two-dimensional rectangle bin-packing problem
• Average-case analysis of cutting and packing in two dimensions
• An analytical model for the container loading problem
• A 2.5 times optimal algorithm for packing in two dimensions
• An improved BL lower bound
• Bin packing can be solved within 1+epsilon in linear time
• Packing problems
• On genetic algorithms for the packing of polygons
• Some experiments with simulated annealing techniques for packing problems
• An approximation scheme for strip packing of rectangles with bounded dimensions
• An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts
• An exact algorithm for general, orthogonal, two-dimensional knapsack problems
• Approximation algorithm for the oriented two-dimensional bin packing problem
• Guided local search and its application to the traveling salesman problem
• Heuristic algorithms for the three-dimensional bin packing problem
• Models and bounds for two-dimensional level packing problems
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• Exact Solution of the Two-Dimensional Finite Bin Packing Problem
• An Exact Approach to the Strip-Packing Problem
• The Bottomn-Left Bin-Packing Heuristic: An Efficient Implementation
• A Linear Programming Approach to the Cutting-Stock Problem
• An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure
• Two-Dimensional Finite Bin-Packing Algorithms
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Orthogonal Packings in Two Dimensions
• Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms
• A algorithm for two-dimensional packing
• On Packing Two-Dimensional Bins
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems
• The Three-Dimensional Bin Packing Problem
• Optimal Scheduling of Tasks on Identical Parallel Processors
• A Linear Programming Approach to the Cutting Stock Problem—Part II
• Multistage Cutting Stock Problems of Two and More Dimensions

This page was built for publication: Two-dimensional packing problems: a survey