An improved algorithm on unbounded parallel-batching scheduling to minimize maximum cost and makespan

¹ School of Science, Henan University of Technology, Zhengzhou, Henan, 450001, P.R. China
² Faculty of International Studies, Henan Normal University, Xinxiang, Henan, 453007, P.R. China

^* Corresponding author: hech202@163.com

Received: 20 July 2022
Accepted: 10 January 2023

Abstract

This paper studies the bicriteria problem of scheduling n jobs on a parallel-batching machine to minimize maximum cost and makespan simultaneously. A parallel-batching machine is a machine that can handle up to b jobs in a batch. The jobs in a batch start and complete respectively at the same time and the processing time of a batch is equal to the largest processing time of jobs in the batch. We consider the unbounded case. For the above bicriteria scheduling problem, we present an O(n³)-time algorithm, which improved the best known O(n⁴)-time algorithm, and the time complexity is the same as the special case in which maximum cost is maximum lateness. Meanwhile, our algorithm can also solve the single-criterion unbounded parallel-batching scheduling problem to minimize maximum cost in O(n³) time, which improved the best known O(n⁴)-time algorithm.