货物装卸中带共同宽容期的排序问题

考虑货物装卸管理中船主和港口之间存在的如下相互制约关系：有n条货船于零时刻同时抵达码头，因而也希望在同一时段［d,D］内完成装卸货物.如某船的货物在D时刻后才装卸完，则船主会向港方索取赔偿；反之，如货物在d前完成装卸，则船主会向港方给付一定奖金.因此从港方来讲要适当考虑n条货船的装卸顺序，使得总费用最少.对于这一NP困难的排序问题，本文给出了两个动态规划解法及其多项式可解的特例，并给出了一个分枝定界算法.

Scheduling of Goods Loading and Unloading within Common Due Window

This paper studies the following relationship between shipowner and harbor in loading and unloading goods: n ships arrive at the same harbor at time zero.It is hoped to finish loading and unloading goods within the same due window .If a ship finishes its work after D,the ship owner will penalize the harbor.If a ship finishes its work before d,the ship owner will reward the harbor.Thus the harbor needs to arrange the loading and unloading sequence in an optimal manner for these ships so that the total cost is minimized.To deal with such an NP-hard problem,the paper proposes two dynamic programming algorithms,a branch and bound algorithm with a polynomial solvable case.