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

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