文件名称：论文研究-在线A形装箱问题.pdf
文件大小：191KB
文件格式：PDF
更新时间：2022-10-10 09:29:08
论文研究
论文研究-在线A形装箱问题.pdf, 研究了一类有实际背景的新的装箱问题—— A形装箱问题 (ASBP)的在线情形 .在 ASBP中物品均为圆柱形 ,并且在每个箱子中物品均摆放成 A字形 ,即后到达的物品放在先到达的物品之上且上层物品的截面半径不超过下层物品的截面半径 ,优化目标是最小化装下所有物品所用的箱子数 .当所有物品半径都相同时 ASBP退化成经典一维装箱问题 (BP) ,故 BP为 ASBP的特殊情形 .BP的大多数启发式算法可以推广到 ASBP中 ,我们从最坏情形分析的角度讨论了两类 ASBP启发式算法 .证明了直接推广的启发式算法性能较差 ,其中一些算法的渐近最坏比甚至可以任意大 ;如果半径的种类有限 ,按半径分类的启发式算法的性能较好 ,并且一些算法的渐近最坏比和它们所基于的 BP启发式算法的渐近最坏比相等.