调和装箱算法的平均性能分析

经典一维装箱问题在多处理器调度、资源分配和日常生活中的计划、包装、调度等优化问题中有着极为重要的应用 .该文系统地分析了在待处理的物品大小相互独立的情况下 ,L ee & L ee提出的调和近似装箱算法的平均性能 ;具体给出了在均匀分布下 ,调和算法平均性能比的值 ,并用实验验证了这些结果 .

A Stochastic Analysis of the Harmonic Bin-Packing Algorithm

One-dimensional bin-packing problem has many important applications such as multiprocessor scheduling, resource allocation, real-world planning, and packing and scheduling optimization problems. The problem is known to be NP-hard, so researchers have turned to the study of approximation algorithms which attempt to find near-optimal solutions although they do not guarantee to find an optimal solution for every instance. Harmonic(HK) algorithm, which is first proposed by Lee & Lee based on the algorithm Next Fit(NF), is one of the most important approximation algorithms. It is an O(n)-time O(K)-space on line algorithm with a worst-case performance ratio of 1.69103…. In this paper, we analyze the average-case performance of the Harmonic algorithm for pieces of inter-independent distributed sizes, give the average-case performance ratio for (0,a］(a1) uniform distributed inputs and verify these results with numerical experiments. Discuss the algorithm performance for different constant a and K and point out that the algorithm performance improves for a-decreasing or K-increasing, especially when K is sufficient large, the average-case performance ratio of Harmonic algorithm is 1.28987… under (0,1］ uniform distribution while it improves to 1.15947… under (0,0.5］ uniform distribution. Through these analysis we confirm that, with an O(K) extra space cost, Harmonic algorithm is better than Next Fit algorithm not only in worst-case performance, but also in average-case performance.