×

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.)
PDFBibTeX XMLCite
Full Text: DOI