Strip packing problem

Given a set of axis-aligned rectangles and a strip of bounded width and infinite height, determine an overlapping-free packing of the rectangles into the strip, minimizing its height.

Another example is the area of industrial manufacturing, where rectangular pieces need to be cut out of a sheet of material (e.g., cloth or paper) that has a fixed width but infinite length, and one wants to minimize the wasted material.

[2] It is strongly-NP hard and there exists no polynomial-time approximation algorithm with a ratio smaller than

However, the best approximation ratio achieved so far (by a polynomial time algorithm by Harren et al.[3]) is

For pseudo-polynomial time and FPT-algorithms, the definition is slightly changed for the simplification of notation.

Especially the width of the strip is given by an arbitrary integer number larger than 1.

These variants concern the objects' geometry, the problem's dimension, the rotateability of the items, and the structure of the packing.

[4] Geometry: In the standard variant of this problem, the set of given items consists of rectangles.

In this case, the objects are hyperrectangles, and the strip is open-ended in one dimension and bounded in the residual ones.

However, variants have been studied where rotating by 90 degrees or even an arbitrary angle is allowed.

also hold for the case that a rotation of the items by 90 degrees is allowed.

The following two lower bounds take notice of the fact that certain items cannot be placed next to each other in the strip, and can be computed in

[7] For the first lower bound assume that the items are sorted by non-increasing height.

On the other hand, Steinberg[8] has shown that the height of an optimal solution can be upper bounded by

seems complicated, and the complexity of the corresponding algorithms increases regarding their running time and their descriptions.

, it searches for the bottom-most position to place it and then shifts it as far to the left as possible.

First, the algorithm sorts the items by order of nonincreasing height.

The intuitive idea is to split the strip into sub-strips while placing some items.

In this case, it splits the corresponding sub-strip into two pieces: one containing the first item

For each sub-strip s ∈ S we know its lower left corner s.xposition and s.yposition, its width s.width, the horizontal lines parallel to the upper and lower border of the item placed last inside this sub-strip s.upper and s.lower, as well as the width of it s.itemWidth.

Each reduction rule will produce a smaller target area and a subset of items that have to be placed.

When the condition from above holds before the procedure started, then the created subproblem will have this property as well.

Note that procedures 1 to 3 have a symmetric version when swapping the height and the width of the items and the target region.

When considering this type of algorithms, all the sizes of the items and the strip are given as integrals.

Note that this is no longer considered as a polynomial running time since, in the given instance, the width of the strip needs an encoding size of

It is shown that each optimal solution can be simplified and transformed into one that has one of a constant number of structures.

The algorithm then iterates all these structures and places the items inside using linear and dynamic programming.

[5] In the online variant of strip packing, the items arrive over time.

In the first variant, it is not allowed to alter the packing once an item is placed.

The quality of an online algorithm is measured by the (absolute) competitive ratio