The Unbounded Parallel-Batching Bicriteria Scheduling with Two-Component Jobs

This paper studies a bicriteria scheduling problem on a parallel-batching machine to minimize maximum cost and makespan simultaneously. Each job has two components: standard component and specific component. Standard components are processed in batches. Specific components are processed individually. The processing order of two components of a job has no constraint. A job is completed only when its two components are completed. For the simultaneous optimization scheduling problem, we design an \(O(n^{4})\) $O(n^4)$ -time algorithm.