New resolution algorithm and pretreatments for the two-dimensional bin-packing problem

DOI10.1016/J.COR.2007.02.013MaRDI QIDQ2482368zbMATH OpenOpenAlexFDO

Authors Joseph El Hayek, A. Moukrim, Stéphane Nègre

Publication date 16 April 2008

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2007.02.013

zbMATH Keywords

bin-packingcuttingheuristic algorithmspretreatments

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Review text

The authors consider the two-dimensional bin-packing problem, i.e. the problem of finding the minimum number of identical rectangles called bins that must be used to pack a given set of rectangular items without overlapping. The items can be rotated. The authors introduce the concept of dependent orientation items, and propose three pretreatments that allow to reduce the cardinality of the set of items. A new heuristic based on a best-fit strategy is proposed. The algorithm and the pretreatments are tested on benchmarks from the literature.

Recommendations

• Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems
• A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts
• The two-dimensional finite bin packing problem. I: New lower bounds for the oriented case
• A new exact method for the two-dimensional bin-packing problem with fixed orientation
• Two-dimensional packing problems: a survey

Cites work

• A general framework for bounds for higher-dimensional orthogonal packing problems.
• A lower bound for the non-oriented two-dimensional bin packing problem
• A New Placement Heuristic for the Orthogonal Stock-Cutting Problem
• Exact solution of the two-dimensional finite bin packing problem
• Guided local search for the three-dimensional bin-packing problem
• Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems
• scientific article; zbMATH DE number 3890754 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation
• Recent advances on two-dimensional bin packing problems
• The Bottomn-Left Bin-Packing Heuristic: An Efficient Implementation
• The two-dimensional finite bin packing problem. I: New lower bounds for the oriented case
• The two-dimensional finite bin packing problem. II: New lower and upper bounds
• Two-Dimensional Finite Bin-Packing Algorithms

Cited in

(10)

• Strips minimization in two-dimensional cutting stock of circular items
• An open space based heuristic for the 2D strip packing problem with unloading constraints
• A new exact method for the two-dimensional bin-packing problem with fixed orientation
• Sequential heuristic for the two-dimensional bin-packing problem
• The evolution of rectangular bin packing problem -- a review of research topics, applications, and cited papers
• Prospective network flow models and algorithms for bin packing problems
• Heuristics with stochastic neighborhood structures for two-dimensional bin packing and cutting stock problems
• Constrained order packing: comparison of heuristic approaches for a new bin packing problem
• A modified partially mapped multicrossover genetic algorithm for two-dimensional bin packing problem
• Heuristic placement routines for two-dimensional bin packing problem

This page was built for publication: New resolution algorithm and pretreatments for the two-dimensional bin-packing problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2482368)