Parallel-machine batch scheduling to minimize the maximum lateness and the number of tardy jobs

There is a set of jobs available to process in batches on a set of identical parallel machines. A sequence-independent setup time is incurred whenever a batch is formed on any machine. The jobs in the same batch are continuously processed after the setup. The processing length of a batch is the sum of the setup time and the processing times of the jobs it contains. Under the batch availability constraint, the completion time of a job is defined as the time when the batch it belongs to is totally completed. With each job, a due date is specified for its completion. In this paper, we first consider the problem to schedule as well as group the jobs so that the maximum lateness is minimized. The second problem is to minimize the number of tardy jobs. We first design dynamic programming algorithms for finding optimal solutions to the two problems. Then, we design several heuristics and conduct computational experiments to study their relative performance.