Abstract:

We study a scheduling problem with incompatible job families and rejection on a parallel-batching machine, where the objective is to minimize the makespan of all accepted jobs plus the total penalty of all rejected jobs. We provide a polynomial-time algorithm for the case where all jobs have identical release dates and a pseudo-polynomial-time algorithm for the case where the number of distinct elease dates is fixed. We also present a 2-approximation algorithm and a polynomial-time approximation scheme for the general problem.

Key words: Parallel-batching scheduling,  Incompatible job families,  Rejection Approximation algorithm