Article ID: | iaor20041590 |
Country: | China |
Volume: | 6 |
Issue: | 4 |
Start Page Number: | 31 |
End Page Number: | 36 |
Publication Date: | Nov 2002 |
Journal: | OR Transactions |
Authors: | Sun Shijie, Wu Chunyan, Song Zhengfang |
Keywords: | programming: dynamic |
This paper considers such a sequencing problem which comes from the relationship between captain and harbor in loading and unloading goods. Ships arrive at the harbor at the same time, and also hope to finish their loading and unloading goods at the same time. For a given ship, if the harbor could not finish its loading and unloading goods before or at its due date, the harbor will be fined by the captain; otherwise the captain will reward the harbor. Thus the harbor needs to arrange the loading and unloading sequence optimally for these ships such that the total cost is minimized. Corresponding to such an NP-hard problem, this paper gives a dynamic programming and develops a pseudo-polynomial dynamic programming algorithm.