English

应用科学学报

• 论文 • 上一篇    下一篇

一个可拒装卸引发的排序问题

王利, 孙世杰   

  1. 上海大学 数学系, 上海200444
  • 收稿日期:2006-10-23 修回日期:2007-01-24 出版日期:2007-05-31 发布日期:2007-05-31

A Scheduling Problem with Rejection of Goods Loading and Unloading

WANG Li, SUN Shi-jie   

  1. Department of Mathematics, Shanghai University, Shanghai 200444, China
  • Received:2006-10-23 Revised:2007-01-24 Online:2007-05-31 Published:2007-05-31

被引次数

1

摘要： 从生产实际中提炼出下述可拒装卸引发的排序问题：有n条船（工件）在时刻零同时抵达同一码头（机器）等待装卸货物（加工），因而也希望在同一时刻（应交工时间）完成装卸任务。如某船的货物不能如期装卸完而延误了该船的离港，船主会向港方索赔。反之，如提前装卸完而使该船可提前投入运输，则船主会向港方发一定奖金。同时若某船货期较紧而延期罚值较大时，港方宁可付出较小费用安排该船到附近的码头去装卸货物。对这样一个可拒装卸问题，从港方来说需考虑的是是否装卸这些船以及如何适当安排所装卸船的装卸顺序以使总费用最小。文中在对该问题给出了一些性质后，对共同应交工时间不大于所有工件的最小加工时间的上述问题证得为 并构造了一伪多项式时间算法，从而证明了此时的问题为普通意义下 的，对共同应交工时间大于所有工件的最小加工时间的上述问题也证得为 的并研究了其几个子问题，指出它们或为普通意义下 的，或为多项式时间可解的。

关键词: 排序, 可拒装卸, 算法

Abstract: We consider the following scheduling problem with rejection of goods loading and unloading: n ships reach the same harbor at the time 0, and all want to finish loading and unloading at the same time. If a ship cannot finish its work before or on its due date, the ship-owner will penalize the harbor, otherwise the ship-owner will pay prize to the harbor. At the same time, if the penalty is too heavy as a ship is delayed, the harbor may arrange this ship to be loaded or unloaded at other harbor after paying some penalty. The harbor needs to consider which ships are loaded or unloaded and what is the best sequence of loading and unloading so that the total cost is minimized. After giving some properties for this scheduling problem, we show that this problem is NP-hard, present a detailed analysis, and describe some pseudo-polynomial time solvable cases and polynomial time solvable cases.

Key words: scheduling, non-execution, algorithm