经典的排序问题要求工件都必须进行加工, 然而在实际中有时候由于一些特殊的原因可以考虑工件不加工,例如, 加工时间非常大, 或加工所需费用非常高, 于是就不加工这一工件, 而是通过支付一定的费用后送到外边“ 外加工” 或购买更合算, 这类问题称为工件可拒绝排序问题。需要研究的任务是怎样选择工件在机器上进行加工或拒绝, 并且如何安排被接受加工工件的加工次序使给定的目标函数值最优。本文研究了工件可拒绝排序中, 目标函数是有限的总惩罚费用( 总惩罚费用约束下) 极小化加权总完工时间, 工件到达时间都相同的同型机问题, 设计了伪多项式时间的动态规划算法, 并给出了相应的FPTAS算法。