Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan

This paper studies the bicriteria problem of scheduling n jobs on a batching machine to minimize maximum lateness and makespan simultaneously. A parallel-batching machine is a machine that can handle up to b jobs in a batch. The jobs in a batch start and complete at the same time, respectively, and the processing time of a batch is equal to the largest processing time of jobs in the batch. We analyse the unbounded model, where b≥n. We present a polynomial-time algorithm for finding all Pareto optimal solutions of this bicriteria scheduling problem.