Performance Analysis and Improvement for Some Linear On-Line Bin-Packing Algorithms

摘要

The study on one-dimensional bin packing problem may bring about many important applications such as multiprocessor scheduling, resource allocating, real-world planning and packing. Harmonic algorithms (including H_K, RH etc.) for bin packing have been famous for their linear-time and on-line properties for a long time. This paper profoundly analyzes the average-case performance of harmonic algorithms for pieces of i.i.d.sizes, provides the average-case performance ratio of H_K under (0,d] (d ≤ 1) uniform distribution and the average-case performance ratio of RH under (0,1] uniform distribution. We also finished the discussion of the worst-case performance ratio of RH. Moreover, we propose a new improved version of RH that obtains better worst-and average-case performance ratios.