A Scheduling Problem with Earliness Award and Tardiness Penalty
W Hunyan · Or Transactions · 2002
This paper considers such a sequencing problem which comes from the relationship between captain and harbor in loading and unloading goods: n ships arrive at the one 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 couldn't 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 a NP-hard problem, this paper gives a dynamic programming and developes a pseudo-polynomial dynamic programming algorithm under inverse agreeable ratio condition.