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