English

上海大学学报(自然科学版)

• 通信与信息工程 • 上一篇    下一篇

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

陆焱萍，孙世杰，谭芳   

  1. 上海大学 理学院，上海 200444
  • 收稿日期:2005-04-12 修回日期:1900-01-01 出版日期:1900-01-01 发布日期:1900-01-01
  • 通讯作者: 孙世杰

Scheduling of Goods Loading and Unloading within Common Due Window

LU Yan-ping,SUN Shi-jie,TAN Fang   

  1. School of Sciences, Shanghai University, Shanghai 200444， China
  • Received:2005-04-12 Revised:1900-01-01 Online:1900-01-01 Published:1900-01-01
  • Contact: SUN Shi-jie

被引次数

2

摘要：

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

关键词: 惩罚, 共同宽容交货期, 奖励, 排序, 算法

Abstract:

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 ［d,D］. 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 wit

h such an NPhard problem, the paper proposes two dynamic programming algorithm

s, a branch and bound algorithm with a polynomial solvable case.

Key words: algorithm, award, common due window, penalty, scheduling

© 2019 上海大学学报(自然科学版)编辑部
办公地址：上海市宝山区南陈路333号上海大学东区3#楼221室电话：021-66135508　 传真：021-66132736　 E-mail： xuebao@mail.shu.edu.cn
通信地址：上海市上大路99号上海大学126信箱 邮编：200444
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn