Packing Rectangles into a Strip

Guntram Scheithauer
Additional contact information
Guntram Scheithauer: TU Dresden

Chapter Chapter 7 in Introduction to Cutting and Packing Optimization, 2018, pp 183-226 from Springer

Abstract: Abstract Within this chapter we consider the following problem of minimizing material consumption in the two-dimensional case: there are given a list of rectangles and a strip of fixed width and unlimited height. The task is to pack all rectangles orthogonally into the strip such that the minimal needed height is used. The Strip Packing Problem (SPP) belongs, like many other cutting and packing problems, to the class of NP-hard optimization problems. It is polynomially equivalent to the Orthogonal Packing (Feasibility) Problem. Due to the NP-hardness, efficient heuristics are considered in the majority of related literature. Besides an appropriate modeling of the SPP, we describe and analyze some heuristic and metaheuristic approaches. Moreover, based on lower bounds, we present a branch-and-bound algorithm which packs the pieces sequentially. The Guillotine Strip Packing Problem is considered as well.

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:isochp:978-3-319-64403-5_7

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

DOI: 10.1007/978-3-319-64403-5_7

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().