Abstract
This study investigates the dynamic bin packing problem which is one of the oldest classic NP-complete problems in the field of combinatorial optimization. The problem involves assigning a set of n items with size no more than the given bin capacity to equal-capacity bins so that the total size of items in each bin does not exceed the bin capacity, and items may depart from the packing at any time. The optimization objective is to minimize the maximum number of bins ever used over all time. In the perspective of practice, this problem has widely studied for the memory allocation problems. Therefore, many variants have been continually proposed over the past decades. In this study, we revisit the properties of some on-line algorithms in the dynamic bin packing problem and investigate a generalization model of the bin packing problem, called semi-online dynamic bin packing. The semi-online property provides some relaxations of on-line constraints, such as allowing to repack some items or knowing some information in advance. We develop a semi-online dynamic bin packing algorithm with a greater upper bound in some specific situations.