Creating Worst-Case Instances for Upper and Lower Bounds of the Two-Dimensional 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 2015, 2017, pp 55-61 from Springer

Abstract: Abstract We present a new approach to create instances with large performance ratio, i.e., worst-case instances, of common heuristics for the two-dimensional Strip Packing Problem. The idea of this new approach is to optimise the width and the height of all items aiming to find an instance with maximal performance ratio with respect to the considered heuristic. Therefore, we model the pattern obtained by the heuristic as a solution of an ILP problem and merge this model with a Padberg-type model of the two-dimensional Strip Packing Problem. In fact, the composed model allows to compute the absolute worst-case performance ratio of the heuristic with respect to a limited number of items. We apply the new approach for the Next-Fit Decreasing-Height, the First-Fit Decreasing-Height, and the Best-Fit Decreasing-Height heuristic. Furthermore, we provide an opportunity to use this idea to create worst-case instances for lower bounds.

Date: 2017
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-42902-1_8

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

DOI: 10.1007/978-3-319-42902-1_8

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