A note on unbounded parallel-batch scheduling

作者：Geng Zhichao; Yuan Jinjiang^*

来源：Information Processing Letters, 2015, 115(12): 969-974.

DOI：10.1016/j.ipl.2015.07.002

• Analysis of algorithm
• Parallel-batch scheduling
• Maximum cost
• Strongly polynomial time
• Pareto optimization

This paper revisits the scheduling problem on an unbounded parallel batch machine for minimizing a maximum cost f(max). It was reported in the literature that the decision version of the problem is solvable in O (n(2) + n log 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 fmax 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 (n(4))-time algorithm for the Pareto optimization problem for minimizing C-max and f(max), where Cam is the maximum completion time of jobs. Consequently, the problem for minimizing fmax can also be solved in O (n(4)) time.

• 出版日期2015-12
• 单位郑州大学