On a Constrained Bin Packing Problem with Start-Up Space
受启动空间约束的装箱问题

A constrained bin packing problem with start-up space (SBPP) is proposed in this paper, in which an additional start-up space is needed if different items are put into a same bin. The problem has many applications such as job allocation, multiprocessor scheduling and real-world packing. A linear offline approximation algorithm C-NF is presented to solve the SBPP problem. It is proved that the C-NF algorithm has an asymptotic worst-case performance ratio of 2, which is independent of the size of start-up space.And the experimental average-case performances of C-NF are given.Also,the online property of SBPP is studied.It is pointed out that most of the classic online algorithms cannot offer definite worst-case performance ratios when applied on SBPP.And an online algorithm is proposed with a finite asymptotic worst-case performance ratio for any start-up space.