求解online packing problem的F-B绝对近似算法

来源：计算机工程与应用杂志2017年第11期北京时间：

作者：黄 海1，李松斌2，3

单位：1.莆田学院 信息工程学院，福建 莆田 351100 ；2.中国科学院 声学研究所 南海研究站，海口　570105；3.中国科学院 声学研究所 国家网络新媒体工程技术研究中心，北京　100190

摘要：FF算法由于其在线特性在处理在线装箱问题得到广泛使用，但它无法预测后面达到物品造成装箱率低，提出一种预留一定比例的各类未装满箱体的装箱算法。首先对未装满箱体分类并给出相应的数据结构，接着设计一种绑定配对策略来预留各类未装满箱体数目，并引入间隔函数控制新箱体的启用，最后基于FF算法结合预留策略对物品进行装箱来保证装箱的绝对近似比。提出了一种预留绑定配对策略为后续输入物品提供预测空间，特别的是F-B算法能得到5/3的绝对近似比。

关键词：在线装箱问题,预留箱体,绝对近似比,配对绑定