货物装卸中的一个排序问题

本文考虑货物装卸管理中船主和港口之间的下述相互制约关系：有n条船在时刻零同时抵达同一码头装卸货物，因而也希望在同一时刻守成装卸货物。如某船的货物不能如期装卸守而延误了该船的离港，船主会向港方索取赔偿，反之如货物提前装卸完而使该船河提前投入运输，则船主会向港方付取奖金，加上正常装卸费用，从港方来说要适当考虑n条船的一个装卸顺序，使总费用减少，对这一NP-困难的排序问题，文中给出了几个多项式可解的特殊情形，一般情况下的一个快速下界估计方法以及相应的分支定界算法。

A Sequencing Problem in Loading and Unloading Goods

This paper considers the relationship between shipowner and harbor in loading and unloading goods: n ship reach the same harbor at zero time, and also hope to finish loading and unloading goods at the same time. If a ship couldn't finish work before or at its due date, the shipowner will ask the harbor pay the penalty; otherwise, the shipowner will pay prize to the harbor. Together with the normal cost, the harbor needs to consider the best sequence of loading and unloading n ships' goods such that the total cost is minimized. Corresponding to such a NP-hard problem, this paper gives some polynomial time solvable cases, and a branch and bound algorithm with a rapid method for estimating the lower bound for general case.