Abstract:

This paper studies an online over-list model of berth and quay crane integrated allocation problem, and it focuses on the case with lookahead ability such that on the release of any request, an online player can foresee the next k(k \geq 2) requests. The objective is to minimize the maximum completion time of a request, i.e., the makespan. It is assumed that there are two different sized requests, a hybrid berth consisting of three discrete berths and four quay cranes. We first prove several lower bounds of competitive ratio for k \geq 2, and then present an optimal 7/6-competitive algorithm for the case with k=2. Numerical results further demonstrate that the proposed algorithm behaves well in average performance.

Key words: scheduling, online algorithm, competitive ratio, container port, lookahead