在线A形装箱问题
研究了一类有实际背景的新的装箱问题--A形装箱问题(ASBP)的在线情形.在ASBP中物品均为圆柱形,并且在每个箱子中物品均摆放成A字形,即后到达的物品放在先到达的物品之上且上层物品的截面半径不超过下层物品的截面半径,优化目标是最小化装下所有物品所用的箱子数.当所有物品半径都相同时ASBP退化成经典一维装箱问题(BP),故BP为ASBP的特殊情形.BP的大多数启发式算法可以推广到ASBP中,我们从最坏情形分析的角度讨论了两类ASBP启发式算法.证明了直接推广的启发式算法性能较差,其中一些算法的渐近最坏比甚至可以任意大;如果半径的种类有限,按半径分类的启发式算法的性能较好,并且一些算法的渐近最坏比和它们所基于的BP启发式算法的渐近最坏比相等.
作 者： 陈锋 邢文训 作者单位： 清华大学数学科学系,北京,100084 刊 名： 系统工程理论与实践 ISTIC EI PKU 英文刊名： SYSTEMS ENGINEERING——THEORY & PRACTICE 年，卷(期)： 2002 22(7) 分类号： O223 关键词： 装箱问题 算法分析 启发式算法