Minimizing the makespan on a single parallel batching machine

Abstract: 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 -approximation algorithm for the special case with identical release dates. Finally, we present an approximation algorithm for the general problem with worst-case ratio , where is an arbitrarily small constant. [Copyright &y& Elsevier]