Performance analysis and improvement for some linear on-line bin-packing algorithms. (English) Zbl 1046.90074
Summary: 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\leq 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.
MSC:
90C27 | Combinatorial optimization |
90C59 | Approximation methods and heuristics in mathematical programming |
90C08 | Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) |