The bin packing problem requires packing a set of objects into a finite number of bins of fixed capacity in a way that minimizes the number of bins used. We consider the online version of the problem where items arrive over tine and a decision has to be made as soon as an element is available. Online algorithms can be analyzed in terms of competitiveness, a measure of performance that compares the solution obtained online with the optimal offline solution for the same problem, where the lowest possible competitiveness is best. Online processing is difficult due to the fact that unpredictable item sizes may appear. A number of online algorithms such First-Fit, Next-Fit, Best-Fit, Worst Fit and Harmonic have been proposed and studied in the literature. In this thesis we examine how well these algorithms perform in practice. Our results that practical performance is differs substantially from the worst case online measure.
展开▼
