1 Introduction

In the area of packing, there are different kinds of problems that need to be addressed. One of them is the strip packing problem. It was first introduced by Baker et al. (1980), and it is one of the best-known two-dimensional packing problems of computer science. Here, we have a list of items and a unit-width strip with infinite height, and our goal is to pack the items into this strip without overlaps such that the top of the uppermost item is as low as possible.

In this paper, we concentrate on a generalized version of this problem, where we have several given strips, and their widths may be different (each strip has a unique width). To the best of our knowledge, there is only one existing paper (Ye and Mei 2012) that considers a similar framework. There, the problem was formulated as a scheduling problem, where the items are jobs, their height is the time requirement of the job, their width is the amount of processors needed for the job, and the strips are clusters with a different number of processors (i.e. the width of the strip). The objective function had to minimize the maximum height achieved in any of the strips. We will also investigate this model, and we will define another interesting objective function based on the used area of the strips.

In this study, we consider only the online variant of the problem, where the algorithms know the strips and their widths beforehand, but they have no idea about the input list of items; and even the number of the items is unspecified. The items appear one-by-one and the algorithms have to pack them immediately, and they are not allowed to repack the items later on. As usual, we will measure the performance of online algorithms with their competitive ratios. For a problem instance I, let us denote the objective value of algorithm ALG applied to I by \(ALG\left( I \right) \), and let \(OPT\left( I \right) \) stand for the offline optimal value for this instance. Then ALG is called asymptotically C-competitive if there exists a constant D such that \(ALG\left( I \right) \le C \cdot OPT\left( I \right) + D\) for every instance I. The smallest C, which satisfies this inequality is the asymptotic competitive ratio of ALG. When D equals zero, ALG is called absolutely C-competitive, and the smallest such C is the absolute competitive ratio of ALG.

In their paper, Ye and Mei (2012) proposed an online algorithm with absolute competitive ratio of 14.2915. Here, we will analyze the asymptotic competitive ratio of the algorithms we introduce.

The first investigation of the online strip packing problem was conducted by Baker and Schwarz (1983). They proposed the so-called shelf algorithms: the NextFit Shelf algorithm and the FirstFit Shelf algorithm. The former is asymptotically \(2 \cdot r\)-competitive, while the latter is asymptotically \(1.7 \cdot r\)-competitive, where \(r \in \left\{ x \in {\mathbb {R}}| x>1\right\} \) is a parameter of the algorithm. Csirik and Woeginger (1997) introduced the Harmonic Shelf algorithm that has an asymptotic competitive ratio arbitrarily close to \(1.69103 \cdot r\).

We will define several algorithms and analyze their asymptotic competitiveness. Our algorithms apply ideas taken from investigations into the variable-sized bin packing problem, which was first presented by Friesen and Langston (1986). In this model, we have given a fixed collection of bin sizes and we have an infinite number of bins of every size. The objective is to minimize the total size of the bins, i.e. we have to minimize the wasted space. Kinnersley and Langston (1989) described two ways to adapt NextFit and FirstFit to the variable-sized bin packing problem: ’only with Largest bin’ and ’using Smallest possible bin’. NextFit was adapted to the former approach, while FirstFit was adapted to both of them. It was shown that these three algorithms have an asymptotic competitive ratio of 2. Csirik (1989) defined the Variable Harmonic algorithm with an asymptotic competitive ratio of \(1.691\ldots \). Han et al. (2016) proposed an algorithmic framework that can apply any Harmonic-based bin packing algorithm to the online variant of the strip packing problem such that their asymptotic competitive ratio remains the same. For a detailed overview of the results for this problem, we refer the reader to Csirik (2018).

2 Problem definition

Now, we give a formal definition of the variable-width strip packing problem (VWSPP) and introduce the necessary notations.

For an instance of the VWSPP, we will use the notation \(I=\left( \sigma , {\mathbf {W}}\right) \), where \(\sigma \) is the list of n input items, and \({\mathbf {W}}\) is the vector of the widths of the m strips.

Every item i is represented by its width \(w_i\) and its height \(h_i\). So \(\sigma \) is the list of these pairs; that is, \(\sigma = \left[ \left( w_1, h_1\right) , \left( w_2, h_2\right) , \ldots , \left( w_n, h_n\right) \right] \). The area of item i is denoted by \(A_i\). The height of the highest item will be \(h_{max}\).

The vector \({\mathbf {W}}\) defines the widths of the strips such that \({\mathbf {W}} = \left\langle W_1, W_2, \ldots , W_m \right\rangle \), where \(W_j\) is the width of strip j. The height of the strip j, namely the top of the uppermost item in the strip (also called ’makespan’), will be denoted by \(H_j\).

Without loss of generality, we can assume, that \(0 < h_{max} \le 1\), and \(0 < w_i \le 1\) holds for every item i, and \(1 = W_1> W_2> \ldots> W_m > 0\) holds for the strips.

Using these notations, in the VWSPP, one has to pack the items of \(\sigma \) without rotations such that they never exceed the width of the given strips, and the items never overlap each other (but they can touch the boundaries of each other). In the online variant being investigated here, the items appear one-by-one, and repacking them is not allowed.

We will consider two objective functions for this problem. The first one, which is based on the area being used from the strips, can be formulated as \(\min \sum _{j=1}^m \left( H_j \cdot W_j \right) \). We will denote this area-based model by VWSPP-A. The other one is a makepsan-based objective formulated as \(\min \max _{j=1}^m H_j\), and denoted by VWSPP-M.

The reader might think that these two objectives are equivalent, but this is not the case, which can be demonstrated by the following example. Let \({\mathbf {W}} = \left\langle 1, 0.3 \right\rangle \), that is, we have a strip with a width of 1 and another with a width of 0.3, and \(\sigma \) contains n items of size \(\left( 0.3, 1\right) \) – that is, every item has a width of 0.3 and height of 1. Then, for the area-based objective function, the optimal solution is to pack every item into the 0.3-width strip, so we use an area of \(0.3 \cdot n\), and the makespan is n. However, for the makespan-based objective function, the optimal solution would be to pack the items in a balanced way, meaning we have to pack \(\frac{n}{4}\) items into the 0.3-width strip, and \(\frac{3n}{4}\) items into the 1-width strip, so the height of each strip (i.e. the makespan) is only \(\frac{n}{4}\).

3 Dimension reducing algorithms

Next, we will define a class of the dimension reducing algorithms. They use a partitioning to adapt the standard one dimensional bin packing algorithms to the VWSPP. We will use this definition and the lemma below to make the proofs here simpler.

Definition 1

A variable-width strip packing algorithm is a dimension reducing algorithm, if it partitions the strips vertically into blocks of (possibly) different height such that the height of the items packed into a block is at least \(\alpha \) times the height of the block (where \(0<\alpha \le 1\)), and it packs the items into these blocks horizontally using a one dimensional variable-sized bin packing algorithm.

Let us remark that these blocks are used in a quite similar way to the bins in the variable-sized bin packing problem, because the items are packed next to each other such that they cannot exceed the width of the strip.

Lemma 1

Suppose we have a dimension reducing algorithm ALG for the VWSPP, which uses the variable-sized bin packing algorithm ALG1 for the horizontal packing inside the blocks, and ALG1 is asymptotically C-competitive for the variable-sized bin packing problem. Then ALG is asymptotically \(\frac{1}{\alpha } \cdot C\)-competitive for the VWSPP-A.

Proof

Let us consider separately the groups of items packed into blocks with the same height. The packing of such a group is equivalent to solving the variable-sized bin packing problem where the sizes of the items are the widths of the original items and the possible bin sizes are the widths of the strips.

Since we know that ALG1 is asymptotically C-competitive for the variable-sized bin packing problem, we can be sure that asymptotically OPT cannot be more than C times better than ALG in the horizontal direction. Furthermore, ALG uses at least a fraction \(\alpha \) of every block vertically by definition. Since even OPT cannot do better than completely fill every strip, OPT—even by mixing items with small and large height—cannot be more than \(\frac{1}{\alpha }\) times better than ALG vertically.

These two results confirm the truth of the lemma. \(\square \)

4 NextFit algorithm

The NextFit algorithm is one of the most widely known online algorithms applied in the bin packing problem. It keeps only one bin open at a time, and it attempts to pack the upcoming item into this bin. When the item does not fit into the bin, NextFit closes this bin and opens a new one. A closed bin is never used again for a later item.

Now, we will introduce a version of the NextFit algorithm for the VWSPP. We will start with the definition of the NextFit Shelf algorithm, which is a well-known variant of NextFit for the strip packing problem. Then, we will modify this algorithm such that it is able to handle variable-widths. This modification will be similar to the one made in Kinnersley and Langston (1989) for adapting NextFit to the variable-sized bin packing problem.

The Shelf algorithms pack the items of a strip packing problem such that every item is assigned to a shelf based on its height, and a standard bin packing algorithm is applied to choose among the shelves with the same height. More formally, let \(h\left( p\right) = \frac{1}{r^k}\) denote the height of the shelf p, where \(k \in \mathbb {Z^+} \cup \left\{ 0 \right\} \) and \(r \in \left\{ x \in {\mathbb {R}}| x>1\right\} \) is a parameter of the algorithm. Then the item i with size \(\left( w_i, h_i\right) \) is assigned to shelf p, iff \(h\left( p\right) = \frac{1}{r^k}\) and \(\frac{1}{r^{k+1}} < h_i \le \frac{1}{r^k}\).

The NextFit Shelf (NFS) algorithm is a Shelf algorithm, which uses NextFit to choose among the shelves with the same height; that is, NFS checks to see if there is any shelf with the desired height. If there is not, or the current item does not fit into this shelf, then a new shelf is opened with this height, the item is packed into this and the earlier shelf with this height is closed (if there is any).

In Kinnersley and Langston (1989), NextFit was adapted to the variable-sized bin packing problem such that it uses only the largest bins, and it never opens a smaller one. This algorithm was called NFL (Next Fit, only with Largest bins). It was proven that NFL is asymptotically 2-competitive for the variable-sized bin packing problem.

Applying the idea of NFL to the NextFit Shelf algorithm, we can define the NFSL (Next Fit Shelf, only with Largest strip) algorithm for the VWSPP. This algorithm packs every item into the largest strip (which has a width of 1), and uses the NextFit Shelf algorithm to pack the items inside this strip.

In the next lemma for the VWSPP-A, we will state a result generalised to a whole class of algorithms. Then, we will present our result for the NFSL algorithm in the VWSPP-A.

Lemma 2

For the VWSPP-A, the asymptotic competitive ratio is at least \(2 \cdot r\) for every (online and offline) Shelf algorithm using just the largest strip.

Proof

The proof is based on the following problem instance. Let \({\mathbf {W}} = \left\langle 1, \frac{1}{2}+\varepsilon \right\rangle \) and let \(\sigma \) contain items only with size \(\left( \frac{1}{2}+\varepsilon , \frac{1}{r}+\varepsilon \right) \). Then these algorithms pack every item into the 1-width strip on a 1-height shelf, and only one item goes into each shelf. OPT can pack every item into the other strip exactly on top of each other, so OPT can pack without any wasted area. This immediately gives us the lower-bound. \(\square \)

Theorem 1

The NFSL algorithm is asymptotically \(2 \cdot r\)-competitive for the VWSPP-A, and this ratio is tight.

Proof

For the lower-bound, we can apply Lemma 2 for NFSL by definition.

We know that NFL is asymptotically 2-competitive for the variable-sized bin packing problem (Kinnersley and Langston 1989). Since NFSL is a dimension reducing algorithm using NFL with \(\alpha =\frac{1}{r}\), we can apply Lemma 1 to get the upper-bound. \(\square \)

In the next lemma, we will state a general result for the VWSPP-M.

Lemma 3

Suppose we have a Shelf algorithm ALG which is asymptotically C-competitive for the standard strip packing problem. Let us define ALGL as ALG, adapted to the VWSPP, such that only the largest strip is used. For the VWSPP-M, ALGL is asymptotically \(C \cdot m\)-competitive.

Proof

Let us define the OPTL algorithm such that it uses only the 1-width strip, but it packs the items inside this strip in an optimal way.

Then, we get the following inequality from the competitive ratio of ALG in the standard strip packing problem: \(\frac{ALGL}{OPTL} \le C\).

Furthermore, OPT can use the other strips as well, and it can pack the items into the same height in every strip (if this is possible). This means that \(\frac{OPTL}{m} \le OPT\) holds.

When we combine these two inequalities, we get the upper-bound of the theorem:

$$\begin{aligned} \frac{ALGL}{OPT} \le \frac{ALGL}{\frac{OPTL}{m}} = \frac{ALGL}{OPTL} \cdot m \le C \cdot m. \end{aligned}$$

\(\square \)

Theorem 2

The NFSL algorithm is asymptotically \(2 \cdot r \cdot m\)-competitive for the VWSPP-M, and this ratio is tight.

Proof

For the upper-bound, we can apply Lemma 3 for NFSL by definition, because NFS is asymptotically \(2 \cdot r\) competitive for the standard strip packing problem (Baker and Schwarz 1983).

To prove the tightness of this bound, let us examine the following problem instance. Let \({\mathbf {W}} = \left\langle 1, 1-\varepsilon , 1-2\cdot \varepsilon , \ldots , 1-(m-1)\cdot \varepsilon \right\rangle \), and let \(\sigma \) contain \(n=2\cdot k\) items such that each height is \(\frac{1}{r}+\varepsilon \) and each width comes from the following list:

$$\begin{aligned} \left[ \frac{1}{2}-\frac{(m-1)\cdot \varepsilon }{2}, \frac{(m-1)\cdot \varepsilon }{2} + \varepsilon \right] ^k. \end{aligned}$$

NFSL packs these items with a total height of k into the 1-width strip, because, after each pair, a new shelf is opened with a height of 1.

Meanwhile, OPT packs the first items of each iteration in an equally balanced way among all the strips, because two such items fit next to each other in any strip. If \(\varepsilon \) is small enough, then all the narrow items can be packed next to each other into the 1-width strip. So, OPT can pack these items into a height of \(\frac{k}{2\cdot m} \cdot \left( \frac{1}{r}+\varepsilon \right) + \frac{1}{r}+\varepsilon \).

Comparing the performance of NFSL and OPT for this input, we get the following ratio:

$$\begin{aligned} \lim _{\begin{array}{c} k \rightarrow \infty \\ \varepsilon \rightarrow 0 \end{array}} \frac{k}{\frac{k}{2\cdot m} \cdot \left( \frac{1}{r}+\varepsilon \right) + \frac{1}{r}+\varepsilon } = \lim _{k \rightarrow \infty } \frac{k}{\frac{k}{2\cdot m} \cdot \frac{1}{r} + \frac{1}{r}} = \frac{1}{\frac{1}{2 \cdot m \cdot r}} = 2 \cdot m \cdot r. \end{aligned}$$

\(\square \)

5 FirstFit algorithm

The FirstFit (FF) algorithm is also a well-known online bin packing algorithm. The key difference to NextFit is that FirsFit keeps all the bins open at the same time. If an item fits into any of the bins, it will choose the earliest opened one. For the strip packing problem, FirstFit was adapted to FirstFit Shelf (FFshelf), which uses FirstFit to choose the appropriate shelf to pack the item. This means that it maintains a list of shelves and it packs the item into the first opened shelf with the desired height (Baker and Schwarz 1983).

FirstFit was adapted in two ways for the variable-sized bin packing problem in the paper by Kinnersley and Langston (1989): FFL (FirstFit, only with Largest bin) and FFS (FirstFit, using the Smallest possible bin). Next, we will describe these algorithms and adapt them to the VWSPP as we did for the NFS case.

5.1 FFSL

The FFSL (FirstFit Shelf, only with Largest strip) algorithm differs from NFSL only by using FirstFit instead of NextFit; that is, we pack every item into the largest strip, and use the FirstFit Shelf algoritm inside this strip.

For the VWSPP-A, FFSL has exactly the same competitive ratio as NFSL has.

Theorem 3

The FFSL algorithm is asymptotically \(2 \cdot r\)-competitive for the VWSPP-A, and this ratio is tight.

Proof

For the lower-bound, we can apply Lemma 2 to FFSL by using the definition.

We know that FFL is asymptotically 2-competitive for the variable-sized bin packing problem (Kinnersley and Langston 1989). Since FFSL is a dimension reducing algorithm using FFL with \(\alpha =\frac{1}{r}\), we can apply Lemma 1 for the upper-bound. \(\square \)

Theorem 4

The FFSL algorithm is asymptotically \(1.7 \cdot r \cdot m\)-competitive for the VWSPP-M.

Proof

For this upper-bound, we can apply Lemma 3 for FFSL by definiton, because FirstFit Shelf is asymptotically \(1.7 \cdot r\) competitive for the standard strip packing problem (Baker and Schwarz 1983). \(\square \)

Theorem 5

The FFSL algorithm is asymptotically not better than \(\frac{10}{6} \cdot r \cdot m\)-competitive for the VWSPP-M.

Proof

For this lower-bound, let us examine the following problem instance. Let \({\mathbf {W}} = \left\langle 1, 1-\varepsilon , 1-2\cdot \varepsilon , \ldots , 1-(m-1)\cdot \varepsilon \right\rangle \), and let \(\sigma \) contain \(n=18\cdot k\) items such that each height is \(\frac{1}{r}+\varepsilon \) and each width comes from the following list:

$$\begin{aligned}&\left[ \frac{1 - (m-1)\cdot \varepsilon }{6} - 2 \cdot \varepsilon _2\right] ^{6k}, \\&\left[ \frac{1 - (m-1)\cdot \varepsilon }{3} + \varepsilon _2\right] ^{6k}, \\&\left[ \frac{1 - (m-1)\cdot \varepsilon }{2} + \varepsilon _2\right] ^{6k}, \end{aligned}$$

where \(\varepsilon _2 > \frac{(m-1)\cdot \varepsilon }{2}\).

These items are packed by FFSL into the largest strip in the following way. From the first block, 6 items are packed into the same shelf. The second block is packed pairwise. The items of the third block are packed into separate shelves one-by-one. So, \(k+3k+6k\) shelves are opened with a height of 1. This means that FFSL packs these items into a height of \(10 \cdot k\).

However, OPT can pack one item from every block next to each other, and it can pack these \(\left( 1 - (m-1)\cdot \varepsilon , \frac{1}{r}+\varepsilon \right) \) size items in a balanced way among the strips. So, OPT packs with a height of \(\frac{6k}{m} \cdot \left( \frac{1}{r}+\varepsilon \right) \).

Consolidating these results, we get the following:

$$\begin{aligned} \lim _{n\rightarrow \infty } \frac{FFSL}{OPT} = \lim _{k\rightarrow \infty } \frac{10k}{\frac{6k}{m} \cdot \left( \frac{1}{r}+\varepsilon \right) } = \frac{10}{\frac{6}{m\cdot r}} = \frac{10}{6} \cdot m \cdot r. \end{aligned}$$

\(\square \)

5.2 FFSS

In Kinnersley’s and Langston’s paper (1989), the other adaptation of FirstFit to the variable-sized bin packing was FFS (FirstFit, using the Smallest possible bin), which opens the new bins with the smallest size the current item fits into. Using the basic idea behind this algorithm, we will define the FFSS (First Fit Shelf, using the Smallest possible strip) algorithm such that, if an item does not fit into any of the open shelves, it will open a new shelf in the smallest strip the item fits into.

Theorem 6

The FFSS algorithm is asymptotically \(2 \cdot r\)-competitive for the VWSPP-A, and this ratio is tight.

Proof

We know that FFS is asymptotically 2-competitive for the variable-sized bin packing problem (Kinnersley and Langston 1989). Since FFSS is a dimension reducing algorithm using FFS with \(\alpha =\frac{1}{r}\), we can apply Lemma 1 to get the upper-bound.

To prove the tightness of this upper-bound, let us look at the following problem instance. Let \({\mathbf {W}} = \left\langle 1, 1-\varepsilon \right\rangle \), and let \(\sigma \) contain items with a width of \(\frac{1}{2}\) and a height of \(\frac{1}{r}+\varepsilon \). FFSS packs these items one-by-one into the smaller strip, while OPT fills the space completely by packing them into the larger strip pairwise. \(\square \)

Theorem 7

The FFSS algorithm is asymptotically not constant competitive for the VWSPP-M.

Proof

Let \({\mathbf {W}} = \left\langle 1, \frac{1}{n} \right\rangle \), and let \(\sigma \) contain n items with a width of \(\frac{1}{n}\) and a height of 1.

FFSS packs these items into the smaller strip, and produces a makepsan of n, while OPT packs every item into the 1-width strip and its makepsan is just 1. \(\square \)

6 Variable Harmonic Shelf algorithm

The Harmonic algorithm was defined for the standard bin packing problem by Lee and Lee (1985). The basic idea is to classify the items based on their sizes, and pack the classes separately into bins. The classification is implemented by partitioning the interval \(\left( 0,1\right] \) into subintervals \(I_k (k=1\ldots M)\), where \(I_k = \left( \frac{1}{k+1}, \frac{1}{k}\right] \) for \(1 \le k < M\), and \(I_M=\left( 0, \frac{1}{M}\right] \). M is a positive integer parameter of the algorithm.

The asymptotic competitive ratio of this algorithm can be described with the harmonic sequence of numbers. In Lee and Lee (1985), the harmonic sequence has a recursive definition: \(\pi _1~=~1, \pi _i~=~\pi _{i-1} \cdot \left( \pi _{i-1} +1 \right) \). Then the competitive ratio of the Harmonic algorithm is the limit of the sum of the reciprocals of the first n values; that is, \(\Pi _\infty =\lim _{n \rightarrow \infty } \Pi _n =\lim _{n \rightarrow \infty } \sum _{i=1}^n \frac{1}{\pi _i} = 1.691\ldots \, .\)

Csirik and Woeginger (1997) defined the Harmonic Shelf algorithm for the strip packing problem, which uses the partitioning of the Harmonic algorithm to classify the items based on their widths. It packs the items into the shelves such that each shelf only contains items with the same width-class. It was proven that the asymptotic competitive ratio of this algorithm is \(\Pi _\infty \cdot r\).

For the variable-sized bin packing problem, Csirik introduced the Variable Harmonic (VH) algorithm (Csirik 1989) with the asymptotic competitive ratio of \(\Pi _\infty \). It was proven by Seiden (2001) to be an optimal online algorithm for the bounded space variant of the problem.

Here, we propose an adapted version of VH for the VWSPP: the Variable Harmonic Shelf (VHS) algorithm.

The height-classification of the items is the usual classification of the shelf algorithms.

The width-classification of the items is based on the definition given in Seiden (2001). First, we have to define the set T:

$$\begin{aligned} T_i=\left\{ \left. \frac{W_i}{j}\right| j \in {\mathbb {N}}^+, W_i>j\cdot \varepsilon \right\} , \qquad T=\bigcup _{i=1}^m T_i, \end{aligned}$$

where \(\varepsilon \in \left( 0, 1\right] \) is a parameter of the algorithm and \({\mathbb {N}}^+\) is the set of the positive natural numbers. The numbers in T are denoted by \(t_1, t_2, \ldots , t_v\) such that \(1 = t_1> t_2> \ldots >t_v\). Furthermore, \(t_{v+1}=\varepsilon \) and \(t_{v+2}=0\).

The type of the items is defined by the intervals \(I_k = \left( t_{k+1}, t_k\right] \), where \(k=1, 2, \ldots , v+1\). Then, an item i is of type k if \(w_i \in I_k\). The interval \(I_k\) is of class \(\gamma \) and order j, if \(t_k=\frac{W_\gamma }{j}\) (we can break ties arbitrarily).

The VHS algorithm packs items into the same shelf only if they are of the same type. When the item i arrives, we specify its type and the proper height of its shelf. From the type, we also get the class; that is, the strip to be packed into, and the order; that is, the number of items packed next to each other. If there is a shelf for the current type, where item i fits into, then item i is packed into it. If there is no proper open shelf, then the new shelf is opened in the strip corresponding to the class of this type. The items of type \(v+1\), that is, the ones with a width falling into \(\left( 0, \varepsilon \right] \), are packed using NextFit Shelf into the 1-width strip.

Theorem 8

VHS is asymptotically \(r \cdot \Pi _\infty = r \cdot 1.691\ldots \)-competitive for the VWSPP-A.

Proof

We know that VH is \(\Pi _\infty \)-competitive for the variable-sized bin packing problem (Csirik 1989). Since VHS is a dimension reducing algorithm using VH with \(\alpha =\frac{1}{r}\), we can apply Lemma 1 to get the upper-bound. \(\square \)

Theorem 9

VHS is asymptotically not competitive for the VWSPP-M.

Proof

Let \({\mathbf {W}} = \left\langle 1, \frac{1}{n}-\varepsilon \right\rangle \), and let \(\sigma \) contain n items with a width of \(\frac{1}{n}-\varepsilon \) and a height of 1.

VHS packs all the items into the smaller strip, so the makespan is n. In the meantime, OPT can pack each item into the larger strip next to each other, so the makespan is only 1. \(\square \)

7 Greedy variable Harmonic Shelf algorithm

Now, we will combine the VHS algorithm with the well-known greedy scheduling algorithm to get a constant competitive ratio for the makespan model. This is called the Greedy Variable Harmonic Shelf (GVHS) algorithm.

GVHS uses the same types as VHS, and works in a similar way. The only difference is that when we need to open a new shelf, GVHS (in contrast to VHS) can do this for any strip, where the item fits into. GVHS chooses the strip based on a greedy decision; namely the new shelf is opened in the lowest strip (i.e. where the top of the uppermost shelf is the lowest), where i fits into.

Theorem 10

GVHS is asymptotically \(2 \cdot r\)-competitive for the VWSPP-A.

Proof

The definition of the shelves implies that GVHS fills the shelves to a level of at least \(\frac{1}{r}\) vertically.

Let us look at the horizontal direction. GVHS opens a new shelf for an item only, if this item does not fit into any open shelf with appropriate height and type. This can happen iff, each such shelf is filled half horizontally. We can prove this statement indirectly. Let us suppose that there is a shelf with appropriate height and type, which is not filled half horizontally. Since the current item does not fit into this shelf, it must be wider than the half of the strip of this shelf. This means that the type has both wider and thinner items than the half of the strip. However, this is not possible from the definition of the types. So, this is a contradiction. Therefore, almost every shelf is filled half horizontally (except possibly the last shelves for each height and type). \(\square \)

Theorem 11

GVHS is asymptotically \(4 \cdot r\)-competitive for the VWSPP-M.

Proof

Let us denote the total area of the shelves of GVHS by \(A\left( GVHS\left( \sigma \right) \right) \). Based on Theorem 10, the following inequality holds:

$$\begin{aligned} A\left( GVHS\left( \sigma \right) \right) \le 2 \cdot r\cdot \sum _{i\in \sigma } A_i. \end{aligned}$$

For every type k, let \(S_{\ge k}\) and \(S_{<k}\) denote the set of strips where an item of type k does and does not fit into, respectively. With a similar notation, \(\sigma _{\ge k}\) and \(\sigma _{<k}\) will be the set of items fitting into (at least) one of the strips in \(S_{\ge k}\) and \(S_{<k}\), respectively. We should mention that \(\sigma _{<k} \subseteq \sigma _{\ge k} \equiv \sigma \).

Now, we can define a lower-bound \(\alpha _k\) for the top of the topmost item of type k in any solution, because we know that in the strips of \(S_{\ge k}\) one cannot do better than pack those items that do not fit into any other strip, in a fully balanced way. This gives the following inequality:

$$\begin{aligned} \alpha _k \ge \frac{\sum _{i \in \sigma } A_i - \sum _{i \in \sigma _{<k}} A_i}{\sum _{j \in S_{\ge k}} W_j} = \frac{\sum _{i \in \sigma {\setminus } \sigma _{<k} } A_i}{\sum _{j \in S_{\ge k}} W_j} \end{aligned}$$

Then, the following holds for OPT:

$$\begin{aligned} OPT\left( \sigma \right) \ge \max _{1\le k \le v+1} {\alpha _k} \ge \max _{1\le k \le v+1} { \frac{\sum _{i \in \sigma {\setminus } \sigma _{<k} } A_i}{\sum _{j \in S_{\ge k}} W_j}} \end{aligned}$$

Furthermore, OPT cannot do better than pack the items completely balanced among the strips. This is stated in the following inequality:

$$\begin{aligned} OPT\left( \sigma \right) \ge \frac{\sum _{i \in \sigma } A_i}{\sum _{j=1}^m W_j} \end{aligned}$$

Now, let us investigate GVHS. Let us denote by g the item defining the makespan; that is, g has the highest top of all the items. Let k and p be the type and the shelf of g, and B the bottom of p. The area of p will be denoted by \(A\left( p\right) \). Then \(GVHS\left( \sigma \right) = B + h_{max} \le B + 1\).

We will consider the items of the sets \( \sigma {\setminus } \sigma _{<k}\) and \(\sigma _{<k}\) separately in the result of GVHS. The former items are packed into the strips of \(S_{\ge k}\) as balanced as GVHS is able to. The latter items can be packed into the strips of \(S_{<k}\), so the total height of the shelves with such items in the strips of \(S_{\ge k}\) cannot be more than the height of any strip in \(S_{<k}\), because otherwise GVHS would pack those items into this lower strip of \(S_{<k}\).

Putting these two observations together, using Theorem 10, and noticing that p was opened on the lowest strip at the moment, we get the following:

$$\begin{aligned} B&\le \frac{A\left( GVHS\left( \sigma {\setminus } \sigma _{<k}\right) \right) - A\left( p\right) }{\sum _{j \in S_{\ge k}} W_j} + \frac{A\left( GVHS\left( \sigma _{<k}\right) \right) }{\sum _{j=1}^m {W_j}} \\&\le \frac{2\cdot r \cdot \sum _{i \in \sigma \setminus \sigma _{<k}} A_i - A\left( p\right) }{\sum _{j \in S_{\ge k}} W_j} + \frac{2\cdot r \cdot \sum _{i \in \sigma _{<k}}{A_i}}{\sum _{j=1}^m {W_j}} \\&\le 2\cdot r \cdot \left( \frac{\sum _{i \in \sigma {\setminus } \sigma _{<k}} A_i}{\sum _{j \in S_{\ge k}} W_j} + \frac{\sum _{i \in \sigma _{<k}}{A_i}}{\sum _{j=1}^m {W_j}} \right) \\&\le 2\cdot r \cdot \left( \frac{\sum _{i \in \sigma {\setminus } \sigma _{<k}} A_i}{\sum _{j \in S_{\ge k}} W_j} + \frac{\sum _{i \in \sigma }A_i}{\sum _{j=1}^m {W_j}} \right) \\&\le 2\cdot r \cdot \left( OPT + OPT \right) \\&\le 4 \cdot r \cdot OPT \end{aligned}$$

Now, we apply this to the objective value of GVHS

$$\begin{aligned} GVHS\left( \sigma \right)&\le B + 1 \\&\le 4 \cdot r \cdot OPT + 1. \end{aligned}$$

\(\square \)

8 Improved Variable Harmonic Strip algorithm

Next, we will introduce the Improved Variable Harmonic Strip (IVHS) algorithm based on the results of Han et al. (2016). They proposed a grouping and packing framework (\( G \& P_A\)) for strip packing using any so-called, Super Harmonic algorithm A, and they proved that the asymptotic competitive ratio of the original algorithm does not change with this method. Here, we will define the IVHS algorithm by applying this framework for the VHS algorithm.

The Super Harmonic algorithms were introduced by Seiden in Seiden (2001). This class includes the bin packing algorithms based on classifying the items into intervals by their sizes, such as Harmonic, Refined Harmonic, Modified Harmonic, Modified Harmonic 2, Harmonic+1 and Harmonic++.

One can readily see that the Variable Harmonic algorithm defined by Csirik (1989) is also a Super Harmonic algorithm, which uses the types defined in terms of a width-classification in Sect. 6, and it does not pack multiple types into the same bin.

Now, we can define the IVHS algorithm with the \( G \& P_A\) framework.

Grouping The items are grouped based on their widths according to the width-classification described in Sect. 6. This means that this grouping is equivalent to the classification by the types in VHS. The items of type \(v+1\) (i.e. if their width is less than \(\varepsilon \)) are called narrow items, and all the other ones are called wide items.

Packing The narrow items are packed using the VHS algorithm. We pack the wide items with a two-level packing: the first level packs these items into so-called slips, the second level packs these slips into so-called bins.

Items are packed into the same slip only if they are of the same type. If a slip contains the items of type i, then its size is considered to be \(\left( t_i,c\right) \), where c is a constant parameter such that \(c=o\left( OPT\left( \sigma \right) \right) >1\).

Slips are packed into the same bin only if they contain items of the same type, that is, every item of any bin has the same type. If the type of the items in a bin is of the class j, then this bin is packed into the \(W_j\)-width strip, and its size is \(\left( W_j,c\right) \).

When an item with type i arrives we check to see whether there is a slip of type i with a total height of items at most \(c-1\). If there is such a slip, then the item is packed into it; otherwise a new slip is opened with size \(\left( t_i,c\right) \). When a new slip is created we pack it into a bin. If there is a bin for the type of this slip, then it is packed into that bin; otherwise a new bin is opened for this type on the strip corresponding to the class of the type.

Theorem 12

IVHS is asymptotically \(\Pi _\infty = 1.691\ldots \)-competitive for the VWSPP-A.

Proof

We can treat IVHS as a dimension reduction algorithm packing items of at least \(\frac{c-1}{c}\) height (i.e. the slips); that is, \(\alpha =\frac{c-1}{c}\), into c-height blocks using VH. So we can apply Lemma 1 for an upper-bound of \(\frac{c}{c-1} \cdot \Pi _\infty \). Since c is a sufficiently large constant by definition, this leads us immediately to the statement of the theorem. \(\square \)

Theorem 13

IVHS is asymptotically not competitive for the VWSPP-M.

Proof

We can use the same input as in the proof of Theorem 9. IVHS will also use just the smaller strip for the items, while OPT can pack everything into the 1-width strip. \(\square \)

9 Greedy Improved Variable Harmonic Strip algorithm

Now, we will define the Greedy Improved Variable Harmonic Strip (GIVHS) algorithm, which is a combination of IVHS and the greedy scheduling algorithm.

GIVHS works in a very similar way to IVHS. The only difference is how one chooses the strips for the new bins. While IVHS always opens the new bins in the strip defined by the class of the item-type, GIVHS chooses from any strip, where the item fits into, in a greedy way and the lowest strip is chosen i.e. the one where the top of the uppermost bin is the lowest.

Theorem 14

GIVHS is asymptotically 2-competitive for the VWSPP-A.

Proof

Since GIVHS, like IVHS, packs items of at least \(\frac{c-1}{c}\) in height (i.e. the slips) into c-height bins, GIVHS has an asymptotic vertical area-usage of 1.

In the horizontal direction, we can make a similar assertion as that for GVHS in the proof of Theorem 10. GIVHS opens a new bin for a slip only, if it does not fit into any bin with appropriate type. This can happen iff, each such bin is filled at least half horizontally. The proof of this statement is also similar to that in the proof of Theorem 10. If there were a bin which is not filled half horizontally, then the corresponding type would have both wider and thinner items than the strip of the bin. Thus, almost every bin is filled half horizontally (except possibly the last bin for each type). \(\square \)

Theorem 15

GIVHS is asymptotically 4-competitive for the VWSPP-M.

Proof

We notice that inside the strips the bins of GIVHS are similar containers to the shelves of GVHS. So, this theorem can be proven in a similar way to the one for Theorem 11. We will present only the new parts here.

Let us denote the total area of the bins of GIVHS by \(A\left( GIVHS\left( \sigma \right) \right) \). From Theorem 14, the following inequality holds:

$$\begin{aligned} A\left( GIVHS\left( \sigma \right) \right) \le 2 \cdot \sum _{i \in \sigma } A_i. \end{aligned}$$

Let us denote by g the item defining the makespan; that is, g has the highest top of all the items. Let b be the bin of g, and B the bottom of b. The area of b will be denoted by \(A\left( b\right) \). Then \(GIVHS\left( \sigma \right) \le B + c\).

With the same considerations as in the proof of Theorem 11 and the fact that b was opened on the lowest strip at that moment, we get the following:

$$\begin{aligned} B \le \frac{A\left( GIVHS\left( \sigma {\setminus } \sigma _{<k}\right) \right) - A\left( b\right) }{\sum _{j \in S_{\ge k}} W_j} + \frac{A\left( GIVHS\left( \sigma _{<k}\right) \right) }{\sum _{j=1}^m {W_j}} \le 4\cdot OPT\left( \sigma \right) \end{aligned}$$

Now, we can apply this to the objective value of GIVHS:

$$\begin{aligned} GIVHS\left( \sigma \right) \le B + c \le 4 \cdot OPT\left( \sigma \right) + c. \end{aligned}$$

Next, we can compare the objective value of GIVHS and OPT, and we can use the fact that \(c=o\left( OPT\left( \sigma \right) \right) \) to get

$$\begin{aligned} \lim _{OPT \rightarrow \infty } \frac{GIVHS\left( \sigma \right) }{OPT\left( \sigma \right) } \le \lim _{OPT \rightarrow \infty } \frac{4 \cdot OPT\left( \sigma \right) + c}{OPT\left( \sigma \right) } = 4 \end{aligned}$$

\(\square \)

10 Summary

In this paper, we investigated online algorithms for a variant of the strip packing problem, where we have multiple strips with different widths. This model was investigated earlier by Ye and Mei (2012), where the makespan-based objective model and the absolute competitive ratios of algorithms were studied.

Here, we introduced a new objective function based on the area used from the strips. For both objective functions, we examined the asymptotic competitive ratios of several classical algorithms adapted for this problem.

First, we adapted NextFit and FirstFit such that they use only the largest strip all the time. Then we presented an adaptation of FirstFit using the smallest possible strip. We defined the Variable Harmonic Strip algorithm, and we also combined this with greedy scheduling. Lastly, we introduced the improved variants of these latter two algorithms. The results obtained are summarized in Table 1.

Table 1 The asymptotic competitive ratios of the online algorithms investigated. Recall that m denotes the number of the strips and \(r \in \left\{ x \in {\mathbb {R}}| x>1\right\} \) is a parameter of the Shelf algorithms
Full size table

We have several open questions in connection with the VWSPP and the above-listed algorithms. One can probably prove the tightness of the \(1.7\cdot r \cdot m\) upper-bound for FFSL with a more sophisticated list of items. And it would be nice to find appropriate lower-bounds for the harmonic algorithms described here. Since the Variable Harmonic algorithm was shown to be the optimal bounded-space algorithm for the variable-size bin packing problem (Seiden 2001), we think IVHS is also an optimal bounded-space algorithm for the area-based model, but this conjecture has yet to be proved. The off-line version of the problem is also interesting and should be thoroughly investigated.