Housekeeping: Foresightful container repositioning

This paper deals with crane scheduling in a block of a container terminal equipped with twin cranes when repositioning moves turn out necessary. While one crane is working on a given schedule we aim to anticipate as many repositioning jobs as possible using the second crane without disturbing the first crane. In seaport operations, this situation is commonly called housekeeping. We formulate this problem as a MIP and show that it is strongly NP-hard. Further, we provide an exact procedure based on dynamic programming and a Greedy heuristic procedure to solve it. A comparison of both algorithms with CPLEX concludes this paper.