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

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

A Scheduling Problem with Earliness Award and Tardiness Penalty

This paper considers such a sequencing problem which comes from the relationship between captain and harbor in loading and unloading goods: n ships arrive at the one harbor at the same time, and also hope to finish their loading and unloading goods at the same time. For a given ship, if the harbor couldn't finish its loading and unloading goods before or at its due date, the harbor will be fined by the captain; otherwise the captain will reward the harbor. Thus the harbor needs to arrange the loading and unloading sequence optimally for these ships such that the total cost is minimized. Corresponding to such a NP-hard problem, this paper gives a dynamic programming and developes a pseudo-polynomial dynamic programming algorithm under inverse agreeable ratio condition.