Unbounded parallel‐batching scheduling with two competitive agents

We consider the scheduling problems arising when two agents, each with a family of jobs, compete to perform their respective jobs on a common unbounded parallel‐batching machine. The batching machine can process any number of jobs simultaneously in a batch. The processing time of a batch is equal to the maximum processing time of the jobs in the batch. Two main categories of batch processing based on the compatibility of job families or agents are distinguished. In the case where job families are incompatible, jobs from different families cannot be placed in the same processing batch while all jobs can be placed in the same processing batch when job families are compatible. The goal is to find a schedule for all jobs of the two agents that minimizes the objective of one agent while keeping the objective of the other agent below or at a fixed value Q. Polynomial‐time and pseudo‐polynomial‐time algorithms are provided to solve various combinations of regular objective functions for the scenario in which job families are either incompatible or compatible.