Upper Bounds for Heuristic Approaches to the Strip Packing Problem

Torsten Buchwald () and Guntram Scheithauer ()
Additional contact information
Torsten Buchwald: Dresden University of Technology
Guntram Scheithauer: Dresden University of Technology

A chapter in Operations Research Proceedings 2014, 2016, pp 65-70 from Springer

Abstract: Abstract We present an algorithm for the two-dimensional strip packing problem (SPP) that improves the packing of the FFDH heuristic, and we state theoretical results of this algorithm. We also present an implementation of the FFDH heuristic for the three-dimensional case which is used to construct the COMB-3D heuristic with absolute worst-case performance ratio of 5. We also show, that this heuristic has absolute worst-case performance ratio of at most 4.25 for the z-oriented three-dimensional SPP. Based on this heuristic, we derive a general upper bound for the optimal height which depends on the continuous and the maximum height lower bound. We prove that the combination of both lower bounds also has an absolute worst-case performance ratio of at most 5 for the standard three-dimensional SPP. We also show that the layer-relaxation has a worst-case performance ratio of at most 4.25 for the z-oriented three-dimensional SPP.

Date: 2016
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-28697-6_10

Ordering information: This item can be ordered from
http://www.springer.com/9783319286976

DOI: 10.1007/978-3-319-28697-6_10

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().