In this paper, we study the 1-dimensional on-line bin packing problem. A list of pieces, each of size between zero and unity are to be packed, in order of their arrival, into a minimum number of unit-capacity bins. We present a new linear-time algorithm, the Modified Harmonic Algorithm and show, by a novel use of weighting functions, that it has an asymptotic worst-case performance ratio less than 3 2 + 1 9 + 1 222 = 1.(615)*. We show that for a large class of linear-time on-line algorithms including the Modified Harmonic Algorithm, the performance ratio is at least 3 2 + 1 9 = 1.61*. Then we show how to successively construct classes of improved linear-time on-line algorithms. For any algorithm in any of these classes, the performance ratio is at least 3 2 + 1 12 = 1.583*. We present an improved algorithm called Modified Harmonic-2 with performance ratio 1.612 ... and present an approach to construct linear-time on-line algorithms with better performance ratios. The analysis of Modified Harmonic-2 is omitted because it is very similar to that of Modified Harmonic, but it is substantially more complicated. Our results extend to orthogonal packings in two dimensions.
ASJC Scopus subject areas
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics