9.4. 9.4 On-line bin packing models

In this section we consider the on-line bin packing problem and its multidimensional generalisations. First we present some fundamental results of the area. Then we define the multidimensional generalisations and present some details from the area of on-line strip packing.

9.4.1. 9.4.1 On-line bin packing

In the bin packing problem the input is a list of items, where the -th item is given by its size . The goal is to pack the items into unit size bins and minimise the number of the bins used. In a more formal way we can say that we have to divide the items into groups where each group has the property that the total size of its items is at most , and the goal is to minimise the number of groups. This problem appears also in the area of memory management.

In this section we investigate the on-line problem which means that the decision maker has to make decisions about the packing of the -th item based on values without any information about the further items.

Algorithm Next-Fit , bounded space algorithms

First we consider the model where the number of the open bins is limited. The -bounded space model means that if the number of open bins reaches bound , then the algorithm can open a new bin only after closing some of the bins, and the closed bins cannot be used for packing further items into them. If only one bin can be open, then the evident algorithm packs the item into the open bin if it fits, otherwise it closes the bin, opens a new one and puts the item into it. This algorithm is called Next-Fit ( NF ) algorithm. We do not present the pseudocode of the algorithm, since it can be found in this book in the chapter about memory management. The asymptotic competitive ratio of algorithm NF is determined by the following theorem.

Theorem 9.12 The asymptotic competitive ratio of NF is 2.

Proof. Consider an arbitrary sequence of items, denote it by . Let denote the number of bins used by OPT and the number of bins used by NF . Furthermore, let , denote the total size of the items packed into the -th bin by NF .

Then , since in the opposite case the first item of the -th bin fits into the -th bin which contradicts to the definition of the algorithm. Therefore the total size of the items is more than .

On the other hand the optimal off-line algorithm cannot put items with total size more than into the same bin, thus we obtain that . This yields that , thus

Consequently, we proved that the algorithm is asymptotically -competitive.

Now we prove that the bound is tight. Consider the following sequence for each denoted by . The sequence contains items, the size of the -th item is , the size of the -th item is , . Algorithm NF puts the -th and the -th items into the -th bin for each bin, thus . The optimal off-line algorithm puts pairs of size items into the first bins and it puts one size item and the small items into the -th bin, thus . Since and this function tends to as tends to , we proved that the asymptotic competitive ratio of the algorithm is at least .

If , then there are better algorithms than NF for the -bounded space model. The best known bounded space on-line algorithms belong to the family of harmonic algorithms, where the basic idea is that the interval is divided into subintervals and each item has a type which is the subinterval of its size. The items of the different types are packed into different bins. The algorithm runs several NF algorithms simultaneously; each for the items of a certain type.

Algorithm First-Fit and the weight function technique

In this section we present the weight function technique which is often used in the analysis of the bin packing algorithms. We show this method by analysing algorithm First-Fit ( FF ).

Algorithm FF can be used when the number of open bins is not bounded. The algorithm puts the item into the first opened bin where it fits. If the item does not fit into any of the bins, then a new bin is opened and the algorithm puts the item into it. The pseudocode of the algorithm is also presented in the chapter of memory management. The asymptotic competitive ratio of the algorithm is bounded above by the following theorem.

Theorem 9.13 FF is asymptotically 1.7-competitive.

Proof. In the proof we use the weight function technique whose idea is that a weight is assigned to each item to measure in some way how difficult it can be to pack the certain item. The weight function and the total size of the items are used to bound the off-line and on-line objective function values. We use the following weight function

Let for any set of items. The properties of the weight function are summarised in the following two lemmas. Both lemmas can be proven by case disjunction based on the sizes of the possible items. The proofs are long and contain many technical details, therefore we omit them.

Lemma 9.14 If is valid for a set of items, then also holds.

Lemma 9.15 For an arbitrary list of items .

Using these lemmas we can prove that the algorithm is asymptotically 1.7-competitive. Consider an arbitrary list of items. The optimal off-line algorithm can pack the items of the list into bins. The algorithm packs items with total size at most into each bin, thus from Lemma 9.14 it follows that . On the other hand considering Lemma 9.15 we obtain that , which yields that , and this inequality proves that the algorithm is asymptotically 1.7-competitive.

It is important to note that the bound is tight, i.e. it is also true that the asymptotic competitive ratio of FF is . Many algorithms have been developed with smaller asymptotic competitive ratio than , the best algorithm known at present time is asymptotically -competitive.

Lower bounds

In this part we consider the techniques for proving lower bounds on the possible asymptotic competitive ratio. First we present a simple lower bound and then we show how the idea of the proof can be extended into a general method.

Theorem 9.16 No on-line algorithm for the bin packing problem can have smaller asymptotic competitive ratio than 4/3.

Proof. Let be an arbitrary on-line algorithm. Consider the following sequence of items. Let and be a list of items of size , and be a list of items of size . The input is started by . Then packs two items or one item into the bins. Denote the number of bins containing two items by . In this case the number of the used bins is . On the other hand, the optimal off-line algorithm can pack pairs of items into the bins, thus .

Now suppose that the input is the combined list . The algorithm is an on-line algorithm, therefore it does not know whether the input is or at the beginning, thus it also uses bins for packing two items from the part . Therefore among the items of size only can be paired with earlier items and the other ones need separate bin. Thus . On the other hand, the optimal off-line algorithm can pack a smaller (size ) item and a larger (size ) item into each bin, thus .

So we obtained that there is a list for algorithm where

Moreover for the above constructed lists is at least , which can be arbitrarily great. This yields that the above inequality proves that the asymptotic competitive ratio of A is at least , and this is what we wanted to prove.

The fundamental idea of the above proof is that a long sequence (in this proof ) is considered, and depending on the behaviour of the algorithm a prefix of the sequence is selected as input for which the ratio of the costs is maximal. It is an evident extension to consider more difficult sequences. Many lower bounds have been proven based on different sequences. On the other hand, the computations which are necessary to analyse the sequence have become more and more difficult. Below we show how the analysis of such sequences can be interpreted as a mixed integer programming problem, which makes it possible to use computers to develop lower bounds.

Consider the following sequence of items. Let , where contains identical items of size . If algorithm is asymptotically -competitive, then the inequality

is valid for each . It is enough to consider an algorithm for which the technique can achieve the minimal lower bound, thus our aim is to determine the value

which value gives a lower bound on the possible asymptotic competitive ratio. We can determine this value as an optimal solution of a mixed integer programming problem. To define this problem we need the following definitions.

The contain of a bin can be described by the packing pattern of the bin, which gives that how many elements are contained in the bin from each subsequence. Formally, a packing pattern is a -dimensional vector , where coordinate is the number of elements contained in the bin from subsequence . For the packing patterns the constraint must hold. (This constraint ensures that the items described by the packing pattern fit into the bin.)

Classify the set of the possible packing patterns. For each let be the set of the patterns for which the first positive coordinate is the -th one. (Pattern belongs to class if for each and .)

Consider the packing produced by A. Each bin is packed by some packing pattern, therefore the packing can be described by the packing patterns. For each denote the number of bins which are packed by the pattern by . The packing produced by the algorithm is given by variables .

Observe that the bins which are packed by a pattern from class receive their first element from subsequence . Therefore we obtain that the number of bins opened by A to pack the elements of subsequence can be given by variables as follows

Consequently, for a given the required value can be determined by the solution of the following mixed integer programming problem.

Min

,

.

The first constraints describe that the algorithm has to pack all items. The second constraints describe that is at least as large as the ratio of the on-line and off-line costs for the subsequences considered.

The set of the possible packing patterns and also the optimal solutions can be determined by the list .

In this problem the number and the value of the variables can be large, thus instead of the problem its linear programming relaxation is considered. Moreover, we are interested in the solution under the assumption that tends to and it can be proven that the integer programming and the linear programming relaxation give the same bound in this case.

The best currently known bound was proven by this method and it states that no on-line algorithm can have smaller asymptotic competitive ratio than .

9.4.2. 9.4.2 Multidimensional models

The bin packing problem has three different multidimensional generalisations: the vector packing, the box packing and the strip packing models. We consider only the strip packing problem in details. For the other generalisations we give only the model. In the vector packing problem the input is a list of -dimensional vectors, and the algorithm has to pack these vectors into the minimal number of bins. A packing is legal for a bin if for each coordinate the sum of the values of the elements packed into the bin is at most . In the on-line version the vectors are coming one by one and the algorithm has to assign the vectors to the bins without any information about the further vectors. In the box packing problem the input is a list of -dimensional boxes and the goal is to pack the items into the minimal number of d-dimensional unit cube without overlapping. In the on-line version the items are coming one by one and the algorithm has to pack them into the cubes without any information about the further items.

On-line strip packing

In the strip packing problem there is a set of two dimensional rectangles, defined by their widths and heights, and the task is to pack them into a vertical strip of width without rotation minimising the total height of the strip. We assume that the widths of the rectangles is at most and the heights of the rectangles is at most . This problem appears in many situations. Usually, scheduling of tasks with shared resource involves two dimensions, namely the resource and the time. We can consider the widths as the resources and the heights as the times. Our goal is to minimise the total amount of time used. Some applications can be found in computer scheduling problems. We consider the on-line version where the rectangles arrive from a list one by one and we have to pack each rectangle into the vertical strip without any information about the further items. Most of the algorithms developed for the strip packing problem belong to the class of shelf algorithms. We consider this family of algorithms below.

Shelf algorithms

A basic way of packing into the strip is to define shelves and pack the rectangles onto the shelves. By shelf we mean a rectangular part of the strip. Shelf packing algorithms place each rectangle onto one of the shelves. If the algorithm decides which shelf will contain the rectangle, then the rectangle is placed onto the shelf as much to the left as it is possible without overlapping the other rectangles placed onto the shelf earlier. Therefore, after the arrival of a rectangle, the algorithm has to make two decisions. The first decision is whether to create a new shelf or not. If the algorithm creates a new shelf, it also has to decide the height of the new shelf. The created shelves always start from the top of the previous shelf. The first shelf is placed to the bottom of the strip. The algorithm also has to choose which shelf to put the rectangle onto. Hereafter we will say that it is possible to pack a rectangle onto a shelf, if there is enough room for the rectangle on the shelf. It is obvious that if a rectangle is higher than a shelf, we cannot place it onto the shelf.

We consider only one algorithm in details. This algorithm was developed and analysed by Baker and Schwarz in 1983 and it is called Next-Fit-Shelf () algorithm. The algorithm depends on a parameter . For each there is at most one active shelf with height . We define how the algorithm works below.

After the arrival of a rectangle choose a value for which satisfies . If there is an active shelf with height and it is possible to pack the rectangle onto it, then pack it there. If there is no active shelf with height , or it is not possible to pack the rectangle onto the active shelf with height , then create a new shelf with height , put the rectangle onto it, and let this new shelf be the active shelf with height (if we had an active shelf with height earlier, then we close it).

Example 9.7 Let . Suppose that the size of the first item is . Therefore, it is assigned to a shelf of height . We define a shelf of height at the bottom of the strip; this will be the active shelf with height and we place the item into the left corner of this shelf. Suppose that the size of the next item is . In this case it is placed onto a shelf of height . There is no active shelf with this height so we define a new shelf of height on the top of the previous shelf. This will be the active shelf of height and the item is placed onto its left corner. Suppose that the size of the next item is . This item is placed onto a shelf of height . It is not possible to pack it onto the active shelf, thus we close the active shelf and we define a new shelf of height on the top of the previous shelf. This will be the active shelf of height and the item is placed into its left corner. Suppose that the size of the next item is . This item is placed onto a shelf of height . We can pack it onto the active shelf of height , thus we pack it onto that shelf as left as it is possible.

For the competitive ratio of the following statements are valid.

Theorem 9.17 Algorithm is -competitive. Algorithm is asymptotically -competitive.

Proof. First we prove that the algorithm is -competitive. Consider an arbitrary list of rectangles and denote it by . Let denote the sum of the heights of the shelves which are active at the end of the packing, and let be the sum of the heights of the other shelves. Let be the height of the highest active shelf ( for some ), and let be the height of the highest rectangle. Since the algorithm created a shelf with height , we have . As there is at most active shelf for each height,

Consider the shelves which are not active at the end. Consider the shelves of height for each , and denote the number of the closed shelves by . Let be one of these shelves with height . The next shelf with height contains one rectangle which would not fit onto . Therefore, the total width of the rectangles is at least . Furthermore, the height of these rectangles is at least , thus the total area of the rectangles packed onto and is at least . If we pair the shelves of height for each in this way, using the active shelf if the number of the shelves of the considered height is odd, we obtain that the total area of the rectangles assigned to the shelves of height is at least . Thus the total area of the rectangles is at least , and this yields that . On the other hand, the total height of the closed shelves is , and we obtain that .

Since is valid we proved the required inequality

Since the heights of the rectangles are bounded by , and are bounded by a constant, so we obtain the result about the asymptotic competitive ratio immediately.

Besides this algorithm some other shelf algorithms have been investigated for the solution of the problem. We can interpret the basic idea of as follows. We define classes of items belonging to types of shelves, and the rectangles assigned to the classes are packed by the classical bin packing algorithm NF . It is an evident idea to use other bin packing algorithms. The best shelf algorithm known at present time was developed by Csirik and Woeginger in 1997. That algorithm uses the harmonic bin packing algorithm to pack the rectangles assigned to the classes.

Exercises

9.4-1 Suppose that the size of the items is bounded above by . Prove that under this assumption the asymptotic competitive ratio of NF is .

9.4-2 Suppose that the size of the items is bounded above by . Prove Lemma 9.15 under this assumption.

9.4-3 Suppose that the sequence of items is given by a list , where contains items of size , contains items of size , contains items of size . Which packing patterns can be used? Which patterns belong to class ?

9.4-4 Consider the version of the strip packing problem where one can lengthen the rectangles keeping the area fixed. Consider the extension of which lengthen the rectangles before the packing to the same height as the shelf which is chosen to pack them onto. Prove that this algorithm is -competitive.