在线A形装箱问题:模型及算法研究

摘要

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