Bin packing problem with rejection and kernels

We consider the bin packing problem with rejection and kernels as follows:given a list of items,some of them are kernels,each with a capacity and penalty,and unlimited bins with equal capacity.An item can be either rejected when it isn't kernel,in which case we pay its penalty,or put in one of the bins.An item can't be rejected when it is kernel.A bin can pack only one kernel.The objective is to minimize the sum of the number of the used bins and the penalties of all rejected items.This is a new combinational optimization problem which has many applications such as multi-processor scheduling and management information on web servers,etc.An offline approximation algorithm is presented to solve this problem.It is proved that the algorithm has an asymptotic worst-case performance ratio of 2,finally the experimental results are given.