【摘要】本文研究单机排序问题，其中工件加工时间具有简单线性恶化函数．同时，所有工件均具有一个给定共同交货期．目标函数为最小化提前有奖延误受罚之和．在逆一致性条件下，给出了求解该排序问题的一个伪多项式时间动态规划算法．同时借助于几何舍入技巧，对求解这类排序问题给出了一个充分多项式时间的近似算法（ＦＰＴＡＳ）。