一个超前有奖迟后受罚的排序问题

本文考虑货物装卸管理中船主和港口之间的下述相互制约关系；有n条船在同一时刻到达同一港口，因而也希望在同一时刻完成装卸货物。如某船的货物不能如期装卸完，船主会向港方索取赔偿，反之，如货物提前装卸完，则船主会向港方付取奖金，因此从港方来说是适当考虑n条船的一个装卸程序以使总费用最少。对这样一个NP－困难的排序问题，本文给出了一个动态规划解法，且在逆一致性条件下给出了一伪多项式时间的动态规划算法。