Minimizing the makespan on a single parallel batching machine

In this paper, we consider the problem of scheduling with release dates and rejection on a single parallel batching machine, where the jobs have non-identical sizes. Our objective is to minimize the makespan of the accepted jobs plus the total penalty of the rejected jobs. First, we give a polynomial time approximation scheme (PTAS) for the case where jobs can be split. Then, we propose a 2-approximation algorithm for the special case with identical release dates. Finally, we present an approximation algorithm for the general problem with worst-case ratio 2+ϵ, where ϵ>0 is an arbitrarily small constant.