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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Buchwald, T., Scheithauer, G.: Improved Performance Bounds of the COMB-3D Heuristic for the three-dimensional Strip Packing Problem. Preprint MATH-NM-01-2015, Technische Universität Dresden
Buchwald, T., Scheithauer, G.: Upper bounds for heuristic approaches to the strip packing problem. Int. Trans. Oper. Res. 23/1-2, 93–119 (2016)
Coffman Jr., E.G., et al.: Performance bounds for level-oriented two-dimensional packing algorithms. SIAM J. Comput. 9, 808–826 (1980)
Epstein, L., Van Stee, R.: This side up!. Approximation and Online Algorithms, pp. 48–60. Springer, Berlin Heidelberg (2005)
Miyazawa, F.K., Wakabayashi, Y.: Approximation algorithms for the orthogonal z-oriented three-dimensional packing problem. SIAM J. Comput. 29, 1008–1029 (2000)
Schiermeyer, I.: Reverse-fit: A 2-optimal algorithm for packing rectangles. In: Algorithms-ESA’94, pp. 290–299 (1994)
Steinberg, A.: A strip-packing algorithm with absolute performance bound 2. SIAM J. Comput. 26, 401–409 (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Buchwald, T., Scheithauer, G. (2016). Upper Bounds for Heuristic Approaches to the Strip Packing Problem. In: Lübbecke, M., Koster, A., Letmathe, P., Madlener, R., Peis, B., Walther, G. (eds) Operations Research Proceedings 2014. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-319-28697-6_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-28697-6_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-28695-2
Online ISBN: 978-3-319-28697-6
eBook Packages: Business and ManagementBusiness and Management (R0)