Generalized Last Open-End Bin Packing Problem
摘要
In this paper, we study the online version of generalized last open-end bin packing problem. In this problem items arrive sequentially and need to be packed into a bin with a load strictly less than 1. If no such bin exists a new one needs to be opened. We introduce a unit overload cost c. Each bin has a unit capacity and unit cost. If the total size of the items packed into the bin is greater than 1, an overload cost is needed for the overloaded portion, and the objective changes from packing all arriving items as required using the minimized number of bins to minimizing the total cost of all bins used. In this paper, we use an algorithm based on the First Fit strategy for this problem, and proved that the asymptotic competitive ratio of this algorithm is at most \(\frac{2}{1 + c}\) when \(0 \le c \le 1\) and at most \(\frac{2c}{1 + c}\) when \(c > 1\) .