Optimizing two-agent single-machine parallel batch scheduling: achieving pareto efficiency in makespan and maximum cost objectives

This paper addresses a single-machine parallel batch scheduling problem involving n jobs managed by two agents. The goal is to achieve simultaneous minimization of the makespan for agent A and the maximum cost for agent B . Both agents operate independently, with agents A and B handling n A and n B jobs respectively. The parallel batch machine has the capability to concurrently handle a maximum of b jobs grouped together as a batch. The processing time for the entire batch is determined by the longest processing time among the individual jobs assigned to that particular batch. For the unbounded version ( b ≥ n ) with either incompatible or compatible job groups, an O ( n A + n B 4 )-time algorithm is presented. For the bounded version ( b < n ) with incompatible job groups, when all jobs of agent B share identical processing times, an O ( n A log n A + n B 2 )-time algorithm is presented. For the bounded version with compatible job groups, when all jobs of agent B share identical processing times, an O ( n A log n A + n A n B + n B 3 )-time algorithm is presented. The algorithms for the unbounded version with incompatible job groups and the bounded version with compatible job groups generalize or improve the previously known algorithms, while the algorithms for the unbounded version with compatible job groups and the bounded version with incompatible job groups are the first polynomial time algorithms for them.