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

School of Computer Science and Technology, Shandong Technology and Business University, 264005 Yantai, P.R. China

^* Corresponding author: sgliytu@hotmail.com

Received: 21 January 2024
Accepted: 2 July 2025

Abstract

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⁴)-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²)-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_An_B + n_B³)-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.