受启动空间约束的装箱问题

• 作者: 许胤龙 陈国良 顾晓东 黄刘生
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 装箱问题 组合优化 近似算法 最坏情况渐近性能比 平均性能比
• 年，卷（期）: 2002,（3）
• 页码范围: 390-397
• 页数: 8页
• 分类号: TP301
• 字数: 8989字
• 语种: 中文

摘要

提出了一种带有启动空间的约束装箱问题(start-up bin packing problem,简称SBPP),即不同类型的物品放入同一箱子中需要一个启动空间.该问题在工作分配、任务调度和日常生活中的包装等问题中有着广泛的应用背景.给出了一个求解SBPP的线性脱线算法C-NF,其最坏情况渐近性能比为2,与启动空间的大小无关.对该算法的平均性能进行了实验分析.另外,还分析了SBPP的在线特性,指出大量的经典在线装箱算法应用于SBPP都不存在确定的最坏情况渐近性能比,也给出了一种具有确定的最坏情况渐近性能比的在线算法.