点击次数：

论文类型：期刊论文

发表时间：2017-02-01

发表刊物：JOURNAL OF COMBINATORIAL OPTIMIZATION

收录刊物：SCIE、EI

卷号：33

期号：2

页面范围：530-542

ISSN号：1382-6905

关键字：Bin packing; Online algorithm; Asymptotic competitive ratio

摘要：In this paper we study the online bin packing with buffer and bounded size, i.e., there are items with size within where , and there is a buffer with constant size. Each time when a new item is given, it can be stored in the buffer temporarily or packed into some bin, once it is packed in the bin, we cannot repack it. If the input is ended, the items in the buffer should be packed into bins too. In our setting, any time there is at most one bin open, i.e., that bin can accept new items, and all the other bins are closed. This problem is first studied by Zheng et al. (J Combin Optim 30(2):360-369, 2015), and they proposed a 1.4444-competitive algorithm and a lower bound 1.3333 on the competitive ratio. We improve the lower bound from 1.3333 to 1.4230, and the upper bound from 1.4444 to 1.4243.