Scheduling an unbounded batch machine to minimize maximum lateness

We consider the problem of scheduling n jobs with release times on an unbounded batch machine to minimize the maximum lateness. An unbounded batch machine is a machine that can process up to b (b ≥ n) jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is the time required for processing the longest job in the batch. We present a linear time approximation scheme for this problem.