Bin packing problems with rejection penalties and their dual problems

作     者：Dosa, Gyorgy He, Yong 

作者机构：Univ Veszprem Dept Math H-8201 Veszprem Hungary Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China 

出 版 物：《INFORMATION AND COMPUTATION》 (信息与计算)

年 卷 期：2006年第204卷第5期

页      面：795-815页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：bin packing bin covering approximation algorithm on-line off-line 

摘      要：In this paper we consider the following problems: we are given a set or n items {u(1),., u(n)} and a number of unit-capacity bins. Each item u(i) has a size w(i) is an element of (0,1] and a penalty p(i)= 0. An item can be either rejected, in which case we pay its penalty, or put into one bin under the constraint that the total size of the items in the bin is no greater than 1. No item can be spread into more than one bin. The objective is to minimize the total number of used bins plus the total penalty paid for the rejected items. We call the problem bin packing with rejection penalties, and denote it as BPR. For the on-line BPR problem, we present an algorithm with an absolute competitive ratio of 2.618 while the lower bound is 2.343, and an algorithm with an asymptotic competitive ratio arbitrarily close to 1.75 while the lower bound is 1.540. For the off-line BPR problem, we present an algorithm with an absolute worst-case ratio of 2 while the lower bound is 1.5, and an algorithm with an asymptotic worst-case ratio of 1.5. We also study a closely related bin covering version of the problem. In this case pi means some amount of profit. If an item is rejected, we get its profit, or it can be put into a bin in such a way that the total size of the items in the bin is no smaller than 1. The objective is to maximize the number of covered bins plus the total profit of all rejected items. We call this problem bin covering with rejection (BCR). For the on-line BCR problem, we show that no algorithm can have absolute competitive ratio greater than 0, and present an algorithm with asymptotic competitive ratio 1/2, which is the best possible. For the off-line BCR problem, we also present an algorithm with an absolute worst-case ratio of 1/2 which matches the lower bound. (C) 2006 Elsevier Inc. All rights reserved.