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

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