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

摘要：

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

关键词：排序、惩罚、奖励、算法

所属期刊栏目：6

分类号：O22(运筹学)

在线出版日期：2004-08-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：31-36