Parallel-machine parallel-batching scheduling with family jobs and release dates to minimize makespan
We consider the scheduling of n family jobs with release dates on m identical parallel batching machines. Each batching machine can process up to b jobs simultaneously as a batch. In the bounded model, b < n, and in the unbounded model, b=a. Jobs from different families cannot be placed in the same batch. The objective is to minimize the maximum completion time (makespan). When the number of families is a constant, for both bounded model and unbounded model, we present polynomial-time approximation schemes (PTAS).
batching family parallel machine approximation algorithm worst case ratio