A note on unbounded parallel-batch scheduling

• Unbounded parallel-batch scheduling.
• Minimizing the maximum scheduling cost.
• Strongly polynomial-time algorithm.
• Pareto optimization scheduling.

This paper revisits the scheduling problem on an unbounded parallel batch machine for minimizing a maximum cost fmaxfmax. It was reported in the literature that the decision version of the problem is solvable in O(n2+nlog⁡P)O(n2+nlog⁡P) time, where n is the number of jobs and P   is the total processing time of jobs. This implies that the optimization version for minimizing fmaxfmax can be solved in weakly polynomial time. But a strongly polynomial-time algorithm has not been provided for this problem. In this paper, we present an O(n4)O(n4)-time algorithm for the Pareto optimization problem for minimizing CmaxCmax and fmaxfmax, where CmaxCmax is the maximum completion time of jobs. Consequently, the problem for minimizing fmaxfmax can also be solved in O(n4)O(n4) time.