本文研究了加权的延迟工作和的排序问题,即极小化 $\sum _{j=1}^n{w}_j{V}_j$的批处理问题,其中 $V_j=min\{T_j,p_j\}$,~$T_j=max\{C_j-d_j,0\}$. 本文主要考虑了$B\ge n$的情形,即$1|r_j=0,B\ge n|\sum _{j=1}^n{w}_j{V}_j$, 证明了这个问题是NP-完备的.

The problem of scheduling $n$ jobs on a batching machine to minimize the weighted sum of late work is studied. We focus on the seemingly simple case $B\ge n$, and show that the problem is NP-completeness.