Creating Worst-Case Instances for Lower Bounds of the 2D Strip Packing Problem

Torsten Buchwald () and Guntram Scheithauer ()
Additional contact information
Torsten Buchwald: Institute of Numerical Mathematics, Dresden University of Technology
Guntram Scheithauer: Institute of Numerical Mathematics, Dresden University of Technology

A chapter in Operations Research Proceedings 2016, 2018, pp 103-109 from Springer

Abstract: Abstract We present a new approach to create instances with high absolute worst-case performance ratio of common lower bounds for the two-dimensional rectangular Strip Packing Problem. The idea of this new approach is to optimize the width and the height of all items regarding the absolute worst case performance ratio of the lower bound. Therefore, we model the pattern related to the lower bound as a solution of an ILP problem and merge this model with the Padberg-type model of the two-dimensional Strip Packing Problem. The merged model maximizes the absolute worst-case performance ratio of the lower bound. We introduce this new model for the horizontal bar relaxation and the horizontal contiguous bar relaxation.

Date: 2018
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-55702-1_15

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

DOI: 10.1007/978-3-319-55702-1_15

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 ().