【摘要】 A形装箱问题是由生产实际引发的一个新的数学模型 ,它是经典一维装箱问题的一种变形——每样物品有高度和半径两个参数。把装箱问题的经典算法推广到在线 A形装箱问题 ,并分别从最坏情形分析与数值模拟两方面对算法进行了比较 ,得到了不同而且有趣的结果。证明了 :FirstFit算法的渐近竞争比为 2 ,而其它在线启发式算法如 NextFit,Worst Fit,Best Fit(BF) ,Almost Worst Fit,Harmon-ic的渐近竞争比皆为无界 ;通过数值模拟 ,在平均意义下BF的性质最好。更多还原

【Abstract】 This paper presents a new model, the A Shaped Bin Packing Problem (ASBP), for industrial manufacturing systems. It is a variant of the classical one dimensional bin packing problem in which each item has two parameters, height and diameter. The classic algorithms for the bin packing problem were extended to the on line ASBP. Comparisons of the worst case analysis and simulation lead to interesting results. The asymptotic competitive ratios in the worst case version of on line heuristics such as Next Fit, Worst Fit, Best Fit (BF), Almost Worst Fit and Harmonic are all infinite, whereas the competitive ratio of First Fit is 2. The BF had the best average.更多还原