Bicriteria scheduling on a series‐batching machine to minimize maximum cost and makespan

This paper studies the bicriteria problem of scheduling n jobs on a serial‐batching machine to minimize maximum cost and makespan simultaneously. A serial‐batching machine is a machine that can handle up to b jobs in a batch and jobs in a batch start and complete respectively at the same time and the processing time of a batch is equal to the sum of the processing times of jobs in the batch. When a new batch starts, a constant setup time s occurs. We confine ourselves to the unbounded model, where b ≥ n. We present a polynomial‐time algorithm for finding all Pareto optimal solutions of this bicriteria scheduling problem.