Hierarchical minimization of two maximum costs on a bounded serial-batching machine

School of Science, Henan University of Technology, Zhengzhou, Henan 450001, P.R. China

^* Corresponding author: hech202@163.com

Received: 27 August 2018
Accepted: 18 December 2020

Abstract

This paper studies a hierarchical optimization problem of scheduling n jobs on a serial-batching machine, in which two objective functions are maximum costs. By a hierarchical optimization problem, we mean the problem of optimizing the secondary criterion under the constraint that the primary criterion is optimized. A serial-batching machine is a machine that can handle up to b jobs in a batch and jobs in a batch start and complete respectively at the same time and the processing time of a batch is equal to the sum of the processing times of jobs in the batch. When a new batch starts, a constant setup time s occurs. We confine ourselves to the bounded model, where b < n. We present an O(n⁴)-time algorithm for this hierarchical optimization problem. For the special case where two objective functions are maximum lateness, we give an O(n³ log n)-time algorithm.