We study a variant of online bin packing problem, in which there are two types of bins: (1, 1) and (2, R), i.e., unit size bin with cost 1 and size 2 bin with cost R > 1, the objective is to minimize the total cost occurred when all the items are packed into the two types of bins. It is not difficult to see that the offline version of the problem is equivalent to the classical bin packing problem when R > 3. In this paper, we focus on the case R ≤ 3, and propose online algorithms and obtain lower bounds for the problem.
展开▼
