The strip packing problem is a 2-dimensional geometric minimization 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. This problem is a cutting and packing problem and is classified as an Open Dimension Problem according to Wäscher et al. This problem arises in the area of scheduling, where it models jobs that require a contiguous portion of the memory over a given time period. 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. This problem was first studied in 1980. It is strongly-NP hard and there exists no polynomial-time approximation algorithm with a ratio smaller than 3 / 2 {\displaystyle 3/2} unless P = N P {\displaystyle P=NP} . However, the best approximation ratio achieved so far (by a polynomial time algorithm by Harren et al.) is ( 5 / 3 + ε ) {\displaystyle (5/3+\varepsilon )} , imposing an open question of whether there is an algorithm with approximation ratio 3 / 2 {\displaystyle 3/2} .
Definition An instance I = ( I , W ) {\displaystyle I=({\mathcal {I}},W)} of the strip packing problem consists of a strip with width W = 1 {\displaystyle W=1} and infinite height, as well as a set I {\displaystyle {\mathcal {I}}} of rectangular items. Each item i ∈ I {\displaystyle i\in {\mathcal {I}}} has a width w i ∈ ( 0 , 1 ] ∩ Q {\displaystyle w_{i}\in (0,1]\cap \mathbb {Q} } and a height h i ∈ ( 0 , 1 ] ∩ Q {\displaystyle h_{i}\in (0,1]\cap \mathbb {Q} } . A packing of the items is a mapping that maps each lower-left corner of an item i ∈ I {\displaystyle i\in {\mathcal {I}}} to a position ( x i , y i ) ∈ ( [ 0 , 1 − w i ] ∩ Q ) × Q ≥ 0 {\displaystyle (x_{i},y_{i})\in ([0,1-w_{i}]\cap \mathbb {Q} )\times \mathbb {Q} _{\geq 0}} inside the strip. An inner point of a placed item i ∈ I {\displaystyle i\in {\mathcal {I}}} is a point from the set i n n ( i ) = { ( x , y ) ∈ Q × Q | x i < x < x i + w i , y i < y < y i + h i } {\displaystyle \mathrm {inn} (i)=\{(x,y)\in \mathbb {Q} \times \mathbb {Q} |x_{i}<x<x_{i}+w_{i},y_{i}<y<y_{i}+h_{i}\}} . Two (placed) items overlap if they share an inner point. The height of the packing is defined as max { y i + h i | i ∈ I } {\displaystyle \max\{y_{i}+h_{i}|i\in {\mathcal {I}}\}} . The objective is to find an overlapping-free packing of the items inside the strip while minimizing the height of the packing. This definition is used for all polynomial time algorithms. For pseudo-polynomial time and FPT-algorithms, the definition is slightly changed for the simplification of notation. In this case, all appearing sizes are integral. Especially the width of the strip is given by an arbitrary integer number larger than 1. Note that these two definitions are equivalent.
Variants There are several variants of the strip packing problem that have been studied. These variants concern the objects' geometry, the problem's dimension, the rotateability of the items, and the structure of the packing. Geometry: In the standard variant of this problem, the set of given items consists of rectangles. In an often considered subcase, all the items have to be squares. This variant was already considered in the first paper about strip packing. Additionally, variants where the shapes are circular or even irregular have been studied. In the latter case, it is referred to as irregular strip packing. Dimension: When not mentioned differently, the strip packing problem is a 2-dimensional problem. However, it also has been studied in three or even more dimensions. In this case, the objects are hyperrectangles, and the strip is open-ended in one dimension and bounded in the residual ones. Rotation: In the classical strip packing problem, the items are not allowed to be rotated. However, variants have been studied where rotating by 90 degrees or even an arbitrary angle is allowed. Structure: In the general strip packing problem, the structure of the packing is irrelevant. However, there are applications that have explicit requirements on the structure of the packing. One of these requirements is to be able to cut the items from the strip by horizontal or vertical edge-to-edge cuts. Packings that allow this kind of cutting are called guillotine packing.
Hardness The strip packing problem contains the bin packing problem as a special case when all the items have the same height 1. For this reason, it is strongly NP-hard, and there can be no polynomial time approximation algorithm that has an approximation ratio smaller than 3 / 2 {\displaystyle 3/2} unless P = N P {\displaystyle P=NP} . Furthermore, unless P = N P {\displaystyle P=NP} , there cannot be a pseudo-polynomial time algorithm that has an approximation ratio smaller than 5 / 4 {\displaystyle 5/4} , which can be proven by a reduction from the strongly NP-complete 3-partition problem. Note that both lower bounds 3 / 2 {\displaystyle 3/2} and 5 / 4 {\displaystyle 5/4} also hold for the case that a rotation of the items by 90 degrees is allowed. Additionally, it was proven by Ashok et al. that strip packing is W[1]-hard when parameterized by the height of the optimal packing.
Properties of optimal solutions There are two trivial lower bounds on optimal solutions. The first is the height of the largest item. Define h max ( I ) := max { h ( i ) | i ∈ I } {\displaystyle h_{\max }(I):=\max\{h(i)|i\in {\mathcal {I}}\}} . Then it holds that
O P T ( I ) ≥ h max ( I ) {\displaystyle OPT(I)\geq h_{\max }(I)} . Another lower bound is given by the total area of the items. Define A R E A ( I ) := ∑ i ∈ I h ( i ) w ( i ) {\displaystyle \mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}h(i)w(i)} then it holds that
O P T ( I ) ≥ A R E A ( I ) / W {\displaystyle OPT(I)\geq \mathrm {AREA} ({\mathcal {I}})/W} . 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 O ( n log ( n ) ) {\displaystyle {\mathcal {O}}(n\log(n))} . For the first lower bound assume that the items are sorted by non-increasing height. Define k := max { i : ∑ j = 1 k w ( j ) ≤ W } {\displaystyle k:=\max\{i:\sum _{j=1}^{k}w(j)\leq W\}} . For each l > k {\displaystyle l>k} define i ( l ) ≤ k {\displaystyle i(l)\leq k} the first index such that w ( l ) + ∑ j = 1 i ( l ) w ( j ) > W {\displaystyle w(l)+\sum _{j=1}^{i(l)}w(j)>W} . Then it holds that
O P T ( I ) ≥ max { h ( l ) + h ( i ( l ) ) | l > k ∧ w ( l ) + ∑ j = 1 i ( l ) w ( j ) > W } {\displaystyle OPT(I)\geq \max\{h(l)+h(i(l))|l>k\wedge w(l)+\sum _{j=1}^{i(l)}w(j)>W\}} . For the second lower bound, partition the set of items into three sets. Let α ∈ [ 1 , W / 2 ] ∩ N {\displaystyle \alpha \in [1,W/2]\cap \mathbb {N} } and define I 1 ( α ) := { i ∈ I | w ( i ) > W − α } {\displaystyle {\mathcal {I}}_{1}(\alpha ):=\{i\in {\mathcal {I}}|w(i)>W-\alpha \}} , I 2 ( α ) := { i ∈ I | W − α ≥ w ( i ) > W / 2 } {\displaystyle {\mathcal {I}}_{2}(\alpha ):=\{i\in {\mathcal {I}}|W-\alpha \geq w(i)>W/2\}} , and I 3 ( α ) := { i ∈ I | W / 2 ≥ w ( i ) > α } {\displaystyle {\mathcal {I}}_{3}(\alpha ):=\{i\in {\mathcal {I}}|W/2\geq w(i)>\alpha \}} . Then it holds that
O P T ( I ) ≥ max α ∈ [ 1 , W / 2 ] ∩ N { ∑ i ∈ I 1 ( α ) ∪ I 2 ( α ) h ( i ) + ( ∑ i ∈ I 3 ( α ) h ( i ) w ( i ) − ∑ i ∈ I 2 ( α ) ( W − w ( i ) ) h ( i ) W ) + } {\displaystyle OPT(I)\geq \max _{\alpha \in [1,W/2]\cap \mathbb {N} }{\Bigg \{}\sum _{i\in {\mathcal {I}}_{1}(\alpha )\cup {\mathcal {I}}_{2}(\alpha )}h(i)+\left({\frac {\sum _{i\in {\mathcal {I}}_{3}(\alpha )h(i)w(i)-\sum _{i\in {\mathcal {I}}_{2}(\alpha )}(W-w(i))h(i)}}{W}}\right)_{+}{\Bigg \}}} , where ( x ) + := max { x , 0 } {\displaystyle (x)_{+}:=\max\{x,0\}} for each x ∈ R {\displaystyle x\in \mathbb {R} } . On the other hand, Steinberg has shown that the height of an optimal solution can be upper bounded by
O P T ( I ) ≤ 2 max { h max ( I ) , A R E A ( I ) / W } . {\displaystyle OPT(I)\leq 2\max\{h_{\max }(I),\mathrm {AREA} ({\mathcal {I}})/W\}.}
More precisely he showed that given a W ≥ w max ( I ) {\displaystyle W\geq w_{\max }({\mathcal {I}})} and a H ≥ h max ( I ) {\displaystyle H\geq h_{\max }(I)} then the items I {\displaystyle {\mathcal {I}}} can be placed inside a box with width W {\displaystyle W} and height H {\displaystyle H} if
W H ≥ 2 A R E A ( I ) + ( 2 w max ( I ) − W ) + ( 2 h max ( I ) − H ) + {\displaystyle WH\geq 2\mathrm {AREA} ({\mathcal {I}})+(2w_{\max }({\mathcal {I}})-W)_{+}(2h_{\max }(I)-H)_{+}} , where ( x ) + := max { x , 0 } {\displaystyle (x)_{+}:=\max\{x,0\}} .
Polynomial time approximation algorithms Since this problem is NP-hard, approximation algorithms have been studied for this problem. Most of the heuristic approaches have an approximation ratio between 3 {\displaystyle 3} and 2 {\displaystyle 2} . Finding an algorithm with a ratio below 2 {\displaystyle 2} seems complicated, and the complexity of the corresponding algorithms increases regarding their running time and their descriptions. The smallest approximation ratio achieved so far is ( 5 / 3 + ε ) {\displaystyle (5/3+\varepsilon )} .
Bottom-up left-justified (BL)
This algorithm was first described by Baker et al. It works as follows: Let L {\displaystyle L} be a sequence of rectangular items. The algorithm iterates the sequence in the given order. For each considered item r ∈ L {\displaystyle r\in L} , it searches for the bottom-most position to place it and then shifts it as far to the left as possible. Hence, it places r {\displaystyle r} at the bottom-most left-most possible coordinate ( x , y ) {\displaystyle (x,y)} in the strip. This algorithm has the following properties:
The approximation ratio of this algorithm cannot be bounded by a constant. More precisely they showed that for each M > 0 {\displaystyle M>0} there exists a list L {\displaystyle L} of rectangular items ordered by increasing width such that B L ( L ) / O P T ( L ) > M {\displaystyle BL(L)/OPT(L)>M} , where B L ( L ) {\displaystyle BL(L)} is the height of the packing created by the BL algorithm and O P T ( L ) {\displaystyle OPT(L)} is the height of the optimal solution for L {\displaystyle L} . If the items are ordered by decreasing widths, then B L ( L ) / O P T ( L ) ≤ 3 {\displaystyle BL(L)/OPT(L)\leq 3} . If the item are all squares and are ordered by decreasing widths, then B L ( L ) / O P T ( L ) ≤ 2 {\displaystyle BL(L)/OPT(L)\leq 2} . For any δ > 0 {\displaystyle \delta >0} , there exists a list L {\displaystyle L} of rectangles ordered by decreasing widths such that B L ( L ) / O P T ( L ) > 3 − δ {\displaystyle BL(L)/OPT(L)>3-\delta } . For any δ > 0 {\displaystyle \delta >0} , there exists a list L {\displaystyle L} of squares ordered by decreasing widths such that B L ( L ) / O P T ( L ) > 2 − δ {\displaystyle BL(L)/OPT(L)>2-\delta } . For each ε ∈ ( 0 , 1 ] {\displaystyle \varepsilon \in (0,1]} , there exists an instance containing only squares where each order of the squares L {\displaystyle L} has a ratio of B L ( L ) / O P T ( L ) > 12 11 + ε {\displaystyle BL(L)/OPT(L)>{\frac {12}{11+\varepsilon }}} , i.e., there exist instances where BL does not find the optimum even when iterating all possible orders of the items. In 2024 this lower bound has been improved by Hougardy and Zondervan to B L ( L ) / O P T ( L ) > 4 3 + ε {\displaystyle BL(L)/OPT(L)>{\frac {4}{3+\varepsilon }}} . In 2025, Hougardy and Zondervan constructed an ordering of rectangles (called the F Q W {\displaystyle {\mathcal {FQW}}} -ordering), such that B L ( L ) / O P T ( L ) ≤ 13 6 {\displaystyle BL(L)/OPT(L)\leq {\frac {13}{6}}} .
Next-fit decreasing-height (NFDH)
This algorithm was first described by Coffman et al. in 1980 and works as follows: Let I {\displaystyle {\mathcal {I}}} be the given set of rectangular items. First, the algorithm sorts the items by order of nonincreasing height. Then, starting at position ( 0 , 0 ) {\displaystyle (0,0)} , the algorithm places the items next to each other in the strip until the next item will overlap the right border of the strip. At this point, the algorithm defines a new level at the top of the tallest item in the current level and places the items next to each other in this new level. This algorithm has the following properties:
The running time can be bounded by O ( | I | log ( | I | ) ) {\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))} and if the items are already sorted even by O ( | I | ) {\displaystyle {\mathcal {O}}(|{\mathcal {I}}|)} . For every set of items I {\displaystyle {\mathcal {I}}} , it produces a packing of height N F D H ( I ) ≤ 2 O P T ( I ) + h max ≤ 3 O P T ( I ) {\displaystyle NFDH({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})} , where h max {\displaystyle h_{\max }} is the largest height of an item in I {\displaystyle {\mathcal {I}}} . For every ε > 0 {\displaystyle \varepsilon >0} there exists a set of rectangles I {\displaystyle {\mathcal {I}}} such that N F D H ( I | ) > ( 2 − ε ) O P T ( I ) . {\displaystyle NFDH({\mathcal {I}}|)>(2-\varepsilon )OPT({\mathcal {I}}).}
The packing generated is a guillotine packing. This means the items can be obtained through a sequence of horizontal or vertical edge-to-edge cuts.
First-fit decreasing-height (FFDH) This algorithm, first described by Coffman et al. in 1980, works similar to the NFDH algorithm. However, when placing the next item, the algorithm scans the levels from bottom to top and places the item in the first level on which it will fit. A new level is only opened if the item does not fit in any previous ones. This algorithm has the following properties:
The running time can be bounded by O ( | I | 2 ) {\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})} , since there are at most | I | {\displaystyle |{\mathcal {I}}|} levels. For every set of items I {\displaystyle {\mathcal {I}}} it produces a packing of height F F D H ( I ) ≤ 1.7 O P T ( I ) + h max ≤ 2.7 O P T ( I ) {\displaystyle FFDH({\mathcal {I}})\leq 1.7OPT({\mathcal {I}})+h_{\max }\leq 2.7OPT({\mathcal {I}})} , where h max {\displaystyle h_{\max }} is the largest height of an item in I {\displaystyle {\mathcal {I}}} . Let m ≥ 2 {\displaystyle m\geq 2} . For any set of items I {\displaystyle {\mathcal {I}}} and strip with width W {\displaystyle W} such that w ( i ) ≤ W / m {\displaystyle w(i)\leq W/m} for each i ∈ I {\displaystyle i\in {\mathcal {I}}} , it holds that F F D H ( I ) ≤ ( 1 + 1 / m ) O P T ( I ) + h max {\displaystyle FFDH({\mathcal {I}})\leq \left(1+1/m\right)OPT({\mathcal {I}})+h_{\max }} . Furthermore, for each ε > 0 {\displaystyle \varepsilon >0} , there exists such a set of items I {\displaystyle {\mathcal {I}}} with F F D H ( I ) > ( 1 + 1 / m − ε ) O P T ( I ) {\displaystyle FFDH({\mathcal {I}})>\left(1+1/m-\varepsilon \right)OPT({\mathcal {I}})} . If all the items in I {\displaystyle {\mathcal {I}}} are squares, it holds that F F D H ( I ) ≤ ( 3 / 2 ) O P T ( I ) + h max {\displaystyle FFDH({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+h_{\max }} . Furthermore, for each ε > 0 {\displaystyle \varepsilon >0} , there exists a set of squares I {\displaystyle {\mathcal {I}}} such that F F D H ( I ) > ( 3 / 2 − ε ) O P T ( I ) {\displaystyle FFDH({\mathcal {I}})>\left(3/2-\varepsilon \right)OPT({\mathcal {I}})} . The packing generated is a guillotine packing. This means the items can be obtained through a sequence of horizontal or vertical edge-to-edge cuts.
The split-fit algorithm (SF) This algorithm was first described by Coffman et al. For a given set of items I {\displaystyle {\mathcal {I}}} and strip with width W {\displaystyle W} , it works as follows:
Determinate m ∈ N {\displaystyle m\in \mathbb {N} } , the largest integer such that the given rectangles have width W / m {\displaystyle W/m} or less. Divide I {\displaystyle {\mathcal {I}}} into two sets I w i d e {\displaystyle {\mathcal {I}}_{wide}} and I n a r r o w {\displaystyle {\mathcal {I}}_{narrow}} , such that I w i d e {\displaystyle {\mathcal {I}}_{wide}} contains all the items i ∈ I {\displaystyle i\in {\mathcal {I}}} with a width w ( i ) > W / ( m + 1 ) {\displaystyle w(i)>W/(m+1)} while I n a r r o w {\displaystyle {\mathcal {I}}_{narrow}} contains all the items with w ( i ) ≤ W / ( m + 1 ) {\displaystyle w(i)\leq W/(m+1)} . Order I w i d e {\displaystyle {\mathcal {I}}_{wide}} and I n a r r o w {\displaystyle {\mathcal {I}}_{narrow}} by nonincreasing height. Pack the items in I w i d e {\displaystyle {\mathcal {I}}_{wide}} with the FFDH algorithm. Reorder the levels/shelves constructed by FFDH such that all the shelves with a total width larger than W ( m + 1 ) / ( m + 2 ) {\displaystyle W(m+1)/(m+2)} are below the more narrow ones. This leaves a rectangular area R {\displaystyle R} of with W / ( m + 2 ) {\displaystyle W/(m+2)} , next to more narrow levels/shelves, that contains no item. Use the FFDH algorithm to pack the items in I n a r r o w {\displaystyle {\mathcal {I}}_{narrow}} using the area R {\displaystyle R} as well. This algorithm has the following properties:
For every set of items I {\displaystyle {\mathcal {I}}} and the corresponding m {\displaystyle m} , it holds that S F ( I