赋有提前或延误惩罚的单机排序问题的动态规划算法

Ｌａｗｌｅｒ和Ｌｅｎｓｔｒａ已证明：赋有延误惩罚的单机排序问题是强ＮＰ－完全问题，没有多项式时间算法。笔者曾证明＾「２」；如果附加条件ｐｉ≥ｐＪ≥ｐｉ／ωｉ〉ｐｊ／ωｊ对于所有的ｉ≠ｊ（ｉ，ｊ＝１，２…，ｎ）成立，则该问题有伪多项式时间算法。现在研究如何用动态规划方法求解这类排序问题。