本文研究了在单台串行批处理机上同时最小化完工时间和最大成本的双目标调度问题。串行批处理机可以将最多$b$个工件组成一个批次进行加工，其中$b$被称为批容量。当开始一个新的批次时，机器需要固定长度的准备时间。在每个批次内，工件按顺序加工，因此批次的加工时间等于该批次中所有工件加工时间之和。批次中所有工件的完成时间相同，即批次的完成时间。主要结果是一个$O(n^3)$时间复杂度的算法，可以在批容量小于工件总数（有界模型）且不存在优先关系的情况下生成所有Pareto最优解。该算法也可以经过修改后在$O(n^3)$时间内解决批容量大于或等于工件总数（无界模型）且存在严格优先关系的情况。这一结果改进了之前针对有界和无界两种模型的最佳已知运行时间$O(n^4)$。

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(n^3)$-time algorithm which can generate all Pareto optimal points for the bounded model ($b<n$) without precedence relation. The algorithm can be modified to solve the unbounded model ($b\ge n$) with strict precedence relation in $O(n^3)$ time as well. The results improve the previously best known running time of $O(n^4)$ for both the bounded and unbounded models.