一种松弛的尺寸可变装箱问题及其在线算法

• 作者: 李波 石冰心
• 来源期刊: 华中科技大学学报（自然科学版）
• 学科: 数学
• 关键词: 装箱问题 在线算法 最坏情形性能 一般情形性能
• 年，卷（期）: 2005,（2）
• 页码范围: 28-30
• 页数: 3页
• 分类号: O221.7
• 字数: 2866字
• 语种: 中文
• DOI: 10.3321/j.issn:1671-4512.2005.02.010

摘要

给定物品系列,不同尺寸的箱子依次到达,要求将所有物品装入到箱子中以实现从第一个箱子到最后一个被使用的箱子为止的所有箱子总尺寸最小化.为此给出了6种在线算法,并对这些算法在两种箱子尺寸约束条件下的最坏情形性能和一般情形性能分别进行了研究.理论分析表明最坏情形下6种算法的渐进竞争比在常规约束不小于2,在松弛的约束条件下为无穷;仿真试验表明一般情形下FFD(First Fit Decreasing) 算法最优.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李波	华中科技大学电子与信息工程系	79	771	16.0	23.0
2	石冰心	华中科技大学电子与信息工程系	48	348	9.0	17.0