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

A Sequencing Problem in Loading and Unloading Goods

作　　者：吴春燕[1] 孙世杰[1] 

机构地区：[1]上海大学数学系,上海200436

出　　处：《运筹学学报》2000年第4期1-11,共11页Operations Research Transactions

基　　金：This project is supported by NGFC(Grant No.19771057).

摘　　要：本文考虑货物装卸管理中船主和港口之间的下述相互制约关系：有ｎ条船在时刻零同时抵达同一码头装卸货物，因而也希望在同一时刻完成装卸货物．如某船的货物不能如期装卸完而延误了该船的离港，船主会向港方索取赔偿，反之如货物提前装卸完而使该船可提前投入运输，则船主会向港方付取奖金，加上正常装卸费用．从港方来说要适当考虑ｎ条船的一个装卸顺序，使总费用减少．对这一ＮＰ－困难的排序问题，文中给出了几个多项式可解的特殊情形，一般情况下的一个快速下界估计方法以及相应的分支定界算法．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 casest and a branch and bound algorithm with a rapid method for estimating the lower bound for general case.

关 键 词：排序 赔偿 奖金 算法 

分 类 号：U695.21[交通运输工程—港口、海岸及近海工程] O223[交通运输工程—船舶与海洋工程]