Online bin packing with delay and holding costs

详细信息    查看全文

• 作者：Lauri Ahlroth ; ^{lauri.ahlroth@aalto.fi} ; André ; Schumacher ^{andre.schumacher@aalto.fi} ; Pekka Orponen ^{pekka.orponen@aalto.fi}
• 关键词：Competitive analysis ; Online algorithm ; Bin packing ; Rent-to-buy
• 刊名：Operations Research Letters
• 出版年：2013
• 出版时间：January, 2013
• 年：2013
• 卷：41
• 期：1
• 页码：1-6
• 全文大小：230 K

文摘

We consider online bin packing where in addition to the opening cost of each bin, the arriving items collect delay costs until their assigned bins are released (closed), and the open bins themselves collect holding costs. Besides being of practical interest, this problem generalises several previously unrelated online optimisation problems. We provide a general online algorithm for this problem with competitive ratio 7, with improvements for the special cases of zero delay or holding costs and size-proportional item delay costs.