A two-phase heuristic for strip packing: Algorithm and probabilistic analysis

DOI10.1016/0167-6377(87)90006-XMaRDI QIDQ579140zbMATH OpenOpenAlexFDO

Authors S. Sadones, Fabien Chauny, Richard Loulou, François Soumis

Publication date 1987

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

Full work available at URL https://doi.org/10.1016/0167-6377(87)90006-x

zbMATH Keywords

heuristicstrip packingrelaxationprobabilistic analysisrecursive knapsack operatingstock cuttingtwo-dimensional layout

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Combinatorial optimization (90C27) Production models (90B30)

Recommendations

• scientific article; zbMATH DE number 4059096
• A new heuristic recursive algorithm for the strip rectangular packing problem
• A recursive heuristic algorithm for 2D rectangular strip packing problems
• Probabilistic analysis of shelf algorithms for strip packing
• A Strip-Packing Algorithm with Absolute Performance Bound 2

Cites work

• scientific article; zbMATH DE number 3890754 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3223982 (Why is no real title available?)
• scientific article; zbMATH DE number 3278887 (Why is no real title available?)
• An Introduction to Combinatorial Models of Dynamic Storage Allocation
• Probabilistic analysis for simple one- and two-dimensional bin packing algorithms
• Two-dimensional packing: expected performance of simple level algorithms
• Worst-Case Analysis of a Placement Algorithm Related to Storage Allocation

Cited in

(16)

• New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems
• scientific article; zbMATH DE number 5732394 (Why is no real title available?)
• A multi-objective programming approach to 1.5-dimensional assortment problem
• scientific article; zbMATH DE number 2050771 (Why is no real title available?)
• Probabilistic analysis of shelf algorithms for strip packing
• scientific article; zbMATH DE number 4059096 (Why is no real title available?)
• A new heuristic recursive algorithm for the strip rectangular packing problem
• Recursive algorithm for generating layer patterns for strip packing
• On a comparison between the strip packing problem and a scheduling problem
• Triple-solution approach for the strip packing problem with two-staged patterns
• The best-fit heuristic for the rectangular strip packing problem: An efficient implementation and the worst-case approximation ratio
• Creating worst-case instances for upper and lower bounds of the two-dimensional strip packing problem
• A survey and comparison of guillotine heuristics for the 2D oriented offline strip packing problem
• An effective shaking procedure for 2D and 3D strip packing problems
• A simple randomized algorithm for two-dimensional strip packing
• Heuristics for the score-constrained strip-packing problem

This page was built for publication: A two-phase heuristic for strip packing: Algorithm and probabilistic analysis

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