Abstract: In online packing problem, FF algorithm is widely used for the online property. But it can not predict the result of the latter to achieve the packing rate is low. A new algorithm is proposed for online packing problem with absolute ratio. First, unfilled boxes are classified and given the corresponding data structure. Then, a binding pairing strategy is designed to reserve the number of unclaimed boxes and introduce the interval function to control the opening of the new box. Finally,  an approximation algorithm based on the FF algorithm combined with the reservation strategy is proposed. In particular, it proposes a reservation binding pairing strategy to provide predictive space for subsequent input items, and the F-B algorithm can obtain 5/3 approximation ratio.

Key words: online packing problem, reserved bin, absolute ratio, match-binding

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

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