首次考虑了目标函数为极小化最大延误与被拒绝工件的惩罚费用之和的单机无界平行批排序问题。证明了问题1|B≥n,rej|Tmax+TCP为NP-困难的,针对该问题给出了基于动态规划的伪多项式时间算法。
In this paper, the authors consider the single unbounded parallel batch scbeduling problem which minimizes the objective function for the maximum delay and the workpiece is rejected and the penalty costs for the first time. The authors show that this problem is NP-hard and provide a pseudo-polynomial-time algorithm based on dynamic programming.