摘要: 本文我们考虑了无关机上的平行分批排序问题.对于批容量无限的平行批排序模型,目标是极小化总完工时间,我们对$p_{ij}\leq p_{ik}$ $(i=1, \cdots, m; 1\leq j\neq k\leq n)$这种一致性的情况设计了多项式的动态规划算法.对于批容量有限的平行批排序模型,我们讨论了$p_{ij}=p_{i}$ $(i=1, \cdots, m; j=1,\cdots, n)$这种情况, 当不考虑工件可被拒绝时,对极小化加权总完工时间的排序,我们给出了其最优算法;当考虑工件可被拒绝时,对极小化被接收工件的加权总完工时间加上被拒绝工件的总拒绝费用的排序,我们设计了一拟多项时间算法.