2025/03/30 by Li, Shuguang, Wen, Zhenxin, Wei, Jing
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2503.23273
This paper studies the bicriteria problem of scheduling n jobs on a serial-batch machine to minimize makespan and maximum cost simultaneously. A serial-batch machine can process up to b jobs as a batch, where b is known as the batch capacity. When a new batch starts, a constant setup time is required for the machine. Within each batch, the jobs are processed sequentially, and thus the processing time of a batch equals the sum of the processing times of its jobs. All the jobs in a batch have the same completion time, namely, the completion time of the batch. The main result is an O(n3)-time algorithm which can generate all Pareto optimal points for the bounded model (b