Online dynamic bin packing

Burcea, Mihai Online dynamic bin packing. PhD thesis, University of Liverpool.

Text BurceaMih_Oct2014_2002421.pdf - Unspecified Available under License Creative Commons Attribution No Derivatives. Download (833kB)

Abstract

In this thesis we study online algorithms for dynamic bin packing. An online algorithm is presented with input throughout time and must make irrevocable decisions without knowledge of future input. The classical bin packing problem is a combinatorial optimization problem in which a set of items must be packed into a minimum number of uniform-sized bins without exceeding their capacities. The problem has been studied since the early 1970s and many variants continue to attract researchers’ attention today. The dynamic version of the bin packing problem was introduced by Coffman, Garey and Johnson in 1983. The problem is a generalization of the bin packing problem in which items may arrive and depart dynamically. In this setting, an online algorithm for bin packing is presented with one item at a time, without knowledge of its departure time, nor arrival and departure times of future items, and must decide in which bin the item should be packed. Migration of items between bins is not allowed, however rearrangement of items within a bin is permitted. The objective of problem is to minimize the maximum number of bins used over all time. In multi-dimensional generalizations of the problem, multi-dimensional items must be packed without overlap in multi-dimensional bins of uniform size in each dimension. In this work, we study the setting where items are oriented and cannot be rotated. We first consider online one-dimensional dynamic bin packing and present a lower bound of 8/3 ∼ 2.666 on the achievable competitive ratio of any deterministic online algorithm, improving the best known 2.5-lower bound. Since the introduction of the problem by Coffman, Garey and Johnson, the progress on the problem has focused on improving the original lower bound of 2.388 to 2.428, and to the best known 2.5-lower bound. Our improvement from 2.5 to 8/3 ∼ 2.666 makes a big step forward in closing the gap between the lower bound and the upper bound, which currently stands at 2.788. Secondly we study the online two- and three-dimensional dynamic bin packing problem by designing and analyzing algorithms for special types of input. Bar-Noy et al. initiated the study of the one-dimensional unit fraction bin packing problem, a restricted version where all sizes of items are of the form 1/k, for some integer k > 0. Another related problem is for power fraction items, where sizes are of the form 1/2k, for some integer k ≥ 0. We initiate the study of online multi-dimensional dynamic bin packing of unit fraction items and power fraction items, where items have lengths unit fraction and power fraction in each dimension, respectively. While algorithms for general input are suitable for unit fraction and power fraction items, their worst-case performance guarantees are the same for special types of input. For unit fraction and power fraction items, we design and analyze online algorithms that achieve better worst-case performance guarantees compared to their classical counterparts. Our algorithms give careful consideration to unit and power fraction items, which allows us to reduce the competitive ratios for these types of inputs. Lastly we focus on obtaining lower bounds on the performance of the family of Any- Fit algorithms (Any-Fit, Best-Fit, First-Fit, Worst-Fit) for online multi-dimensional dynamic bin packing. Any-Fit algorithms are classical online algorithms initially studied for the one-dimensional version of the bin packing problem. The common rule that the algorithms use is to never pack a new item to a new bin if the item can be packed in any of the existing bins. While the family of Any-Fit algorithms is always O(1)-competitive for one-dimensional dynamic bin packing, we show that this is no longer the case for multi-dimensional dynamic bin packing when using Best-Fit and Worst-Fit, even if the input consists of power fraction items or unit fraction items. For these restricted inputs, we prove that Best-Fit and Worst-Fit have unbounded competitive ratios, while for First-Fit we provide lower bounds that are higher than the lower bounds for any online algorithm. Furthermore, for general input we show that all classical Any-Fit algorithms are not competitive for online multi-dimensional dynamic bin packing.

Item Type:	Thesis (PhD)
Additional Information:	Date: 2014-10 (completed)
Depositing User:	Symplectic Admin
Date Deposited:	19 Jan 2015 10:52
Last Modified:	17 Dec 2022 01:17
DOI:	10.17638/02005382
URI:	https://livrepository.liverpool.ac.uk/id/eprint/2005382