Strip packing problem

An example of solutions generated by the Bottom-Up Left-Justified algorithm.

This algorithm was first described by Baker et al.[2] It works as follows:

Let ${\displaystyle L}$ be a sequence of rectangular items. The algorithm iterates the sequence in the given order. For each considered item ${\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 ${\displaystyle r}$ at the bottom-most left-most possible coordinate ${\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 ${\displaystyle M>0}$ there exists a list ${\displaystyle L}$ of rectangular items ordered by increasing width such that ${\displaystyle BL(L)/OPT(L)>M}$, where ${\displaystyle BL(L)}$ is the height of the packing created by the BL algorithm and ${\displaystyle OPT(L)}$ is the height of the optimal solution for ${\displaystyle L}$.[2]
• If the items are ordered by decreasing widths, then ${\displaystyle BL(L)/OPT(L)\leq 3}$.[2]
• If the item are all squares and are ordered by decreasing widths, then ${\displaystyle BL(L)/OPT(L)\leq 2}$.[2]
• For any ${\displaystyle \delta >0}$, there exists a list ${\displaystyle L}$ of rectangles ordered by decreasing widths such that ${\displaystyle BL(L)/OPT(L)>3-\delta }$.[2]
• For any ${\displaystyle \delta >0}$, there exists a list ${\displaystyle L}$ of squares ordered by decreasing widths such that ${\displaystyle BL(L)/OPT(L)>2-\delta }$.[2]
• For each ${\displaystyle \varepsilon \in (0,1]}$, there exists an instance containing only squares where each order of the squares ${\displaystyle L}$ has a ratio of ${\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.[2]

An example for NFDH and FFDH applied to the same instance

This algorithm was first described by Coffman et al.[9] in 1980 and works as follows:

Let ${\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 ${\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 ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))}$ and if the items are already sorted even by ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|)}$.
• For every set of items ${\displaystyle {\mathcal {I}}}$, it produces a packing of height ${\displaystyle NFDH({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})}$, where ${\displaystyle h_{\max }}$ is the largest height of an item in ${\displaystyle {\mathcal {I}}}$.[9]
• For every ${\displaystyle \varepsilon >0}$ there exists a set of rectangles ${\displaystyle {\mathcal {I}}}$ such that ${\displaystyle NFDH({\mathcal {I}}|)>(2-\varepsilon )OPT({\mathcal {I}}).}$[9]
• 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.

This algorithm, first described by Coffman et al.[9] 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 ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}$, since there are at most ${\displaystyle |{\mathcal {I}}|}$ levels.
• For every set of items ${\displaystyle {\mathcal {I}}}$ it produces a packing of height ${\displaystyle FFDH({\mathcal {I}})\leq 1.7OPT({\mathcal {I}})+h_{\max }\leq 2.7OPT({\mathcal {I}})}$, where ${\displaystyle h_{\max }}$ is the largest height of an item in ${\displaystyle {\mathcal {I}}}$.[9]
• Let ${\displaystyle m\geq 2}$. For any set of items ${\displaystyle {\mathcal {I}}}$ and strip with width ${\displaystyle W}$ such that ${\displaystyle w(i)\leq W/m}$ for each ${\displaystyle i\in {\mathcal {I}}}$, it holds that ${\displaystyle FFDH({\mathcal {I}})\leq \left(1+1/m\right)OPT({\mathcal {I}})+h_{\max }}$. Furthermore, for each ${\displaystyle \varepsilon >0}$, there exists such a set of items ${\displaystyle {\mathcal {I}}}$ with ${\displaystyle FFDH({\mathcal {I}})>\left(1+1/m-\varepsilon \right)OPT({\mathcal {I}})}$.[9]
• If all the items in ${\displaystyle {\mathcal {I}}}$ are squares, it holds that ${\displaystyle FFDH({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+h_{\max }}$. Furthermore, for each ${\displaystyle \varepsilon >0}$, there exists a set of squares ${\displaystyle {\mathcal {I}}}$ such that ${\displaystyle FFDH({\mathcal {I}})>\left(3/2-\varepsilon \right)OPT({\mathcal {I}})}$.[9]
• 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.

This algorithm was first described by Coffman et al.[9] For a given set of items ${\displaystyle {\mathcal {I}}}$ and strip with width ${\displaystyle W}$, it works as follows:

1. Determinate ${\displaystyle m\in \mathbb {N} }$, the largest integer such that the given rectangles have width ${\displaystyle W/m}$ or less.
2. Divide ${\displaystyle {\mathcal {I}}}$ into two sets ${\displaystyle {\mathcal {I}}_{wide}}$ and ${\displaystyle {\mathcal {I}}_{narrow}}$, such that ${\displaystyle {\mathcal {I}}_{wide}}$ contains all the items ${\displaystyle i\in {\mathcal {I}}}$ with a width ${\displaystyle w(i)>W/(m+1)}$ while ${\displaystyle {\mathcal {I}}_{narrow}}$ contains all the items with ${\displaystyle w(i)\leq W/(m+1)}$.
3. Order ${\displaystyle {\mathcal {I}}_{wide}}$ and ${\displaystyle {\mathcal {I}}_{narrow}}$ by nonincreasing height.
4. Pack the items in ${\displaystyle {\mathcal {I}}_{wide}}$ with the FFDH algorithm.
5. Reorder the levels/shelves constructed by FFDH such that all the shelves with a total width larger than ${\displaystyle W(m+1)/(m+2)}$ are below the more narrow ones.
6. This leaves a rectangular area ${\displaystyle R}$ of with ${\displaystyle W/(m+2)}$, next to more narrow levels/shelves, that contains no item.
7. Use the FFDH algorithm to pack the items in ${\displaystyle {\mathcal {I}}_{narrow}}$ using the area ${\displaystyle R}$ as well.

This algorithm has the following properties:

• For every set of items ${\displaystyle {\mathcal {I}}}$ and the corresponding ${\displaystyle m}$, it holds that ${\displaystyle SF({\mathcal {I}})\leq (m+2)/(m+1)OPT({\mathcal {I}})+2h_{\max }}$.[9] Note that for ${\displaystyle m=1}$, it holds that ${\displaystyle SF({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+2h_{\max }}$
• For each ${\displaystyle \varepsilon >0}$, there is a set of items ${\displaystyle {\mathcal {I}}}$ such that ${\displaystyle SF({\mathcal {I}})>\left((m+2)/(m+1)-\varepsilon \right)OPT({\mathcal {I}})}$.[9]

For a given set of items ${\displaystyle {\mathcal {I}}}$ and strip with width ${\displaystyle W}$, it works as follows:

1. Find all the items with a width larger than ${\displaystyle W/2}$ and stack them at the bottom of the strip (in random order). Call the total height of these items ${\displaystyle h_{0}}$. All the other items will be placed above ${\displaystyle h_{0}}$.
2. Sort all the remaining items in nonincreasing order of height. The items will be placed in this order.
3. Consider the horizontal line at ${\displaystyle h_{0}}$ as a shelf. The algorithm places the items on this shelf in nonincreasing order of height until no item is left or the next one does not fit.
4. Draw a vertical line at ${\displaystyle W/2}$, which cuts the strip into two equal halves.
5. Let ${\displaystyle h_{l}}$ be the highest point covered by any item in the left half and ${\displaystyle h_{r}}$ the corresponding point on the right half. Draw two horizontal line segments of length ${\displaystyle W/2}$ at ${\displaystyle h_{l}}$ and ${\displaystyle h_{r}}$ across the left and the right half of the strip. These two lines build new shelves on which the algorithm will place the items, as in step 3. Choose the half which has the lower shelf and place the items on this shelf until no other item fits. Repeat this step until no item is left.

This algorithm has the following properties:

• The running time can be bounded by ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))}$ and if the items are already sorted even by ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|)}$.
• For every set of items ${\displaystyle {\mathcal {I}}}$ it produces a packing of height ${\displaystyle A({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }/2\leq 2.5OPT({\mathcal {I}})}$, where ${\displaystyle h_{\max }}$ is the largest height of an item in ${\displaystyle {\mathcal {I}}}$.[10]

This algorithm is an extension of Sleator's approach and was first described by Golan.[11] It places the items in nonincreasing order of width. The intuitive idea is to split the strip into sub-strips while placing some items. Whenever possible, the algorithm places the current item ${\displaystyle i}$ side-by-side of an already placed item ${\displaystyle j}$. In this case, it splits the corresponding sub-strip into two pieces: one containing the first item ${\displaystyle j}$ and the other containing the current item ${\displaystyle i}$. If this is not possible, it places ${\displaystyle i}$ on top of an already placed item and does not split the sub-strip.

This algorithm creates a set S of sub-strips. 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.

function Split Algorithm (SP) is
    input: items  I, width of the strip W
    output: A packing of the items
    Sort I in nonincreasing order of widths;
    Define empty list S of sub-strips;
    Define a new sub-strip s with s.xposition = 0, s.yposition = 0, s.width = W, s.lower = 0, s.upper = 0, s.itemWidth = W;
    Add s to S;
    while I not empty do
        i := I.pop(); Removes widest item from I
        Define new list S_2 containing all the substrips with s.width - s.itemWidth ≥ i.width; 
        S_2 contains all sub-strips where i fits next to the already placed item
        if S_2 is empty then
            In this case, place the item on top of another one.
            Find the sub-strip s in S with smallest s.upper; i.e. the least filled sub-strip
            Place i at position (s.xposition, s.upper);
            Update s: s.lower := s.upper; s.upper := s.upper+i.height; s.itemWidth := i.width;
        else 
            In this case, place the item next to another one at the same level and split the corresponding sub-strip at this position.
            Find s ∈ S_2 with the smallest s.lower;
            Place i at position (s.xposition + s.itemWidth, s.lower);
            Remove s from S;
            Define two new sub-strips s1 and s2 with 
            s1.xposition = s.xposition, s1.yposition = s.upper, s1.width = s.itemWidth, s1.lower = s.upper, s1.upper = s.upper, s1.itemWidth = s.itemWidth;
            s2.xposition = s.xposition+s.itemWidth, s2.yposition = s.lower, s2.width = s.width - s.itemWidth, s2.lower = s.lower, s2.upper = s.lower + i.height, s2.itemWidth = i.width;
            S.add(s1,s2);
    return 
end function

This algorithm has the following properties:

• The running time can be bounded by ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}$ since the number of substrips is bounded by ${\displaystyle |{\mathcal {I}}|}$.
• For any set of items ${\displaystyle {\mathcal {I}}}$ it holds that ${\displaystyle SP({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})}$.[11]
• For any ${\displaystyle \varepsilon >0}$, there exists a set of items ${\displaystyle {\mathcal {I}}}$ such that ${\displaystyle SP({\mathcal {I}})>(3-\varepsilon )OPT({\mathcal {I}})}$.[11]
• For any ${\displaystyle \varepsilon >0}$ and ${\displaystyle C>0}$, there exists a set of items ${\displaystyle {\mathcal {I}}}$ such that ${\displaystyle SP({\mathcal {I}})>(2-\varepsilon )OPT({\mathcal {I}})+C}$.[11]

This algorithm was first described by Schiermeyer.[13] The description of this algorithm needs some additional notation. For a placed item ${\displaystyle i\in {\mathcal {I}}}$, its lower left corner is denoted by ${\displaystyle (a_{i},c_{i})}$ and its upper right corner by ${\displaystyle (b_{i},d_{i})}$.

Given a set of items ${\displaystyle {\mathcal {I}}}$ and a strip of width ${\displaystyle W}$, it works as follows:

1. Stack all the rectangles of width greater than ${\displaystyle W/2}$ on top of each other (in random order) at the bottom of the strip. Denote by ${\displaystyle H_{0}}$ the height of this stack. All other items will be packed above ${\displaystyle H_{0}}$.
2. Sort the remaining items in order of nonincreasing height and consider the items in this order in the following steps. Let ${\displaystyle h_{\max }}$ be the height of the tallest of these remaining items.
3. Place the items one by one left aligned on a shelf defined by ${\displaystyle H_{0}}$ until no other item fit on this shelf or there is no item left. Call this shelf the first level.
4. Let ${\displaystyle h_{1}}$ be the height of the tallest unpacked item. Define a new shelf at ${\displaystyle H_{0}+h_{\max }+h_{1}}$. The algorithm will fill this shelf from right to left, aligning the items to the right, such that the items touch this shelf with their top. Call this shelf the second reverse-level.
5. Place the items into the two shelves due to First-Fit, i.e., placing the items in the first level where they fit and in the second one otherwise. Proceed until there are no items left, or the total width of the items in the second shelf is at least ${\displaystyle W/2}$.
6. Shift the second reverse-level down until an item from it touches an item from the first level. Define ${\displaystyle H_{1}}$ as the new vertical position of the shifted shelf. Let ${\displaystyle f}$ and ${\displaystyle s}$ be the right most pair of touching items with ${\displaystyle f}$ placed on the first level and ${\displaystyle s}$ on the second reverse-level. Define ${\displaystyle x_{r}:=\max(b_{f},b_{s})}$.
7. If ${\displaystyle x_{r}<W/2}$ then ${\displaystyle s}$ is the last rectangle placed in the second reverse-level. Shift all the other items from this level further down (all the same amount) until the first one touches an item from the first level. Again the algorithm determines the rightmost pair of touching items ${\displaystyle f'}$ and ${\displaystyle s'}$. Define ${\displaystyle h_{2}}$ as the amount by which the shelf was shifted down.
   1. If ${\displaystyle h_{2}\leq h(s)}$ then shift ${\displaystyle s}$ to the left until it touches another item or the border of the strip. Define the third level at the top of ${\displaystyle s'}$.
   2. If ${\displaystyle h_{2}>h(s)}$ then shift ${\displaystyle s}$ define the third level at the top of ${\displaystyle s'}$. Place ${\displaystyle s}$ left-aligned in this third level, such that it touches an item from the first level on its left.
8. Continue packing the items using the First-Fit heuristic. Each following level (starting at level three) is defined by a horizontal line through the top of the largest item on the previous level. Note that the first item placed in the next level might not touch the border of the strip with their left side, but an item from the first level or the item ${\displaystyle s}$.

This algorithm has the following properties:

• The running time can be bounded by ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|^{2})}$, since there are at most ${\displaystyle |{\mathcal {I}}|}$ levels.
• For every set of items ${\displaystyle {\mathcal {I}}}$ it produces a packing of height ${\displaystyle RF({\mathcal {I}})\leq 2OPT({\mathcal {I}})}$.[13]

Steinbergs algorithm is a recursive one. Given a set of rectangular items ${\displaystyle {\mathcal {I}}}$ and a rectangular target region with width ${\displaystyle W}$ and height ${\displaystyle H}$, it proposes four reduction rules, that place some of the items and leaves a smaller rectangular region with the same properties as before regarding of the residual items. Consider the following notations: Given a set of items ${\displaystyle {\mathcal {I}}}$ we denote by ${\displaystyle h_{\max }({\mathcal {I}})}$ the tallest item height in ${\displaystyle {\mathcal {I}}}$, ${\displaystyle w_{\max }({\mathcal {I}})}$ the largest item width appearing in ${\displaystyle {\mathcal {I}}}$ and by ${\displaystyle \mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}w(i)h(i)}$ the total area of these items. Steinbergs shows that if

${\displaystyle h_{\max }({\mathcal {I}})\leq H}$, ${\displaystyle w_{\max }({\mathcal {I}})\leq W}$, and ${\displaystyle \mathrm {AREA} ({\mathcal {I}})\leq W\cdot H-(2h_{\max }({\mathcal {I}})-h)_{+}(2w_{\max }({\mathcal {I}})-W)_{+}}$, where ${\displaystyle (a)_{+}:=\max\{0,a\}}$,

then all the items can be placed inside the target region of size ${\displaystyle W\times H}$. 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.

Procedure 1: It can be applied if ${\displaystyle w_{\max }({\mathcal {I}}')\geq W/2}$.

1. Find all the items ${\displaystyle i\in {\mathcal {I}}}$ with width ${\displaystyle w(i)\geq W/2}$ and remove them from ${\displaystyle {\mathcal {I}}}$.
2. Sort them by nonincreasing width and place them left-aligned at the bottom of the target region. Let ${\displaystyle h_{0}}$ be their total height.
3. Find all the items ${\displaystyle i\in {\mathcal {I}}}$ with width ${\displaystyle h(i)>H-h_{0}}$. Remove them from ${\displaystyle {\mathcal {I}}}$ and place them in a new set ${\displaystyle {\mathcal {I}}_{H}}$.
4. If ${\displaystyle {\mathcal {I}}_{H}}$ is empty, define the new target region as the area above ${\displaystyle h_{0}}$, i.e. it has height ${\displaystyle H-h_{0}}$ and width ${\displaystyle W}$. Solve the problem consisting of this new target region and the reduced set of items with one of the procedures.
5. If ${\displaystyle {\mathcal {I}}_{H}}$ is not empty, sort it by nonincreasing height and place the items right allinged one by one in the upper right corner of the target area. Let ${\displaystyle w_{0}}$ be the total width of these items. Define a new target area with width ${\displaystyle W-w_{0}}$ and height ${\displaystyle H-h_{0}}$ in the upper left corner. Solve the problem consisting of this new target region and the reduced set of items with one of the procedures.

Procedure 2: It can be applied if the following conditions hold: ${\displaystyle w_{\max }({\mathcal {I}})\leq W/2}$, ${\displaystyle h_{\max }({\mathcal {I}})\leq H/2}$, and there exist two different items ${\displaystyle i,i'\in {\mathcal {I}}}$ with ${\displaystyle w(i)\geq W/4}$, ${\displaystyle w(i')\geq W/4}$, ${\displaystyle h(i)\geq H/4}$, ${\displaystyle h(i')\geq H/4}$ and ${\displaystyle 2(\mathrm {AREA} ({\mathcal {I}})-w(i)h(i)-w(i')h(i'))\leq (W-\max\{w(i),w(i')\})H}$.

1. Find ${\displaystyle i}$ and ${\displaystyle i'}$ and remove them from ${\displaystyle {\mathcal {I}}}$.
2. Place the wider one in the lower-left corner of the target area and the more narrow one left-aligned on the top of the first.
3. Define a new target area on the right of these both items, such that it has the width ${\displaystyle W-\max\{w(i),w(i')\}}$ and height ${\displaystyle H}$.
4. Place the residual items in ${\displaystyle {\mathcal {I}}}$ into the new target area using one of the procedures.

Procedure 3: It can be applied if the following conditions hold: ${\displaystyle w_{\max }({\mathcal {I}})\leq W/2}$, ${\displaystyle h_{\max }({\mathcal {I}})\leq H/2}$, ${\displaystyle |{\mathcal {I}}|>1}$, and when sorting the items by decreasing width there exist an index ${\displaystyle m}$ such that when defining ${\displaystyle {\mathcal {I'}}}$ as the first ${\displaystyle m}$ items it holds that ${\displaystyle \mathrm {AREA} ({\mathcal {I}})-WH/4\leq \mathrm {AREA} ({\mathcal {I'}})\leq 3WH/8}$ as well as ${\displaystyle w(i_{m+1})\leq W/4}$

1. Set ${\displaystyle W_{1}:=\max {W/2,2\mathrm {AREA} ({\mathcal {I'}})/H}}$.
2. Define two new rectangular target areas one at the lower-left corner of the original one with height ${\displaystyle H}$ and width ${\displaystyle W_{1}}$ and the other left of it with height ${\displaystyle H}$ and width ${\displaystyle W-W_{1}}$.
3. Use one of the procedures to place the items in ${\displaystyle {\mathcal {I'}}}$ into the first new target area and the items in ${\displaystyle {\mathcal {I}}\setminus {\mathcal {I'}}}$ into the second one.

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

Procedure 4: It can be applied if the following conditions hold: ${\displaystyle w_{\max }({\mathcal {I}})\leq W/2}$, ${\displaystyle h_{\max }({\mathcal {I}})\leq H/2}$, and there exists an item ${\displaystyle i\in {\mathcal {I}}}$ such that ${\displaystyle w(i)h(i)\geq \mathrm {AREA} ({\mathcal {I}})-WH/4}$.

1. Place the item ${\displaystyle i}$ in the lower-left corner of the target area and remove it from ${\displaystyle {\mathcal {I}}}$.
2. Define a new target area right of this item such that it has the width ${\displaystyle W-w(i)}$ and height ${\displaystyle H}$ and place the residual items inside this area using one of the procedures.

This algorithm has the following properties:

• The running time can be bounded by ${\displaystyle {\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|)^{2}/\log(\log(|{\mathcal {I}}|)))}$.[8]
• For every set of items ${\displaystyle {\mathcal {I}}}$ it produces a packing of height ${\displaystyle ST({\mathcal {I}})\leq 2OPT({\mathcal {I}})}$.[8]