Abstract: In this paper, we consider the single machine parallel-batch scheduling problem with release dates and the number of rejected jobs not exceeding a given threshold. In this problem, we are given a set of jobs and a parallel batch processing machine. Each job has its release date and processing time; for each job, it is either to be rejected or to be accepted and processed in some batch on the machine. If one job is rejected then its corresponding rejection cost should be paid. To keep a certain service level, it is required that the number of rejected jobs is not greater than a given threshold. The task is how to partition the rejected jobs and the accepted jobs with the given constraint, and determine the batches and the orders for the accepted jobs on the machine to minimize the sum of the makespan and the total rejection cost. Since the studied problem is NP-hard, we propose a pseudo-polynomial time dynamic programming exact algorithm, a 2-approximation algorithm and a fully polynomial time approximation scheme.

Key words: parallel-batch scheduling, rejection, dynamic programming, approximation algorithm