Online Berth Allocation Problem Integrating Quay Cranes Assignment

The problem of berth allocation(BAP)and quay crane assignment(QCSP)are of great importance in the operation management of a container terminal.In this thesis,we integrate BAP and QCAP together and study the problem where the handling requirements of vessels,e.g.,the loading/unloading tasks for containers,arise in an online version.We aim to minimize the earliest time when all requirements are completed under the assumption that the berths are discrete and the vessels are simplified to only two types,one type occupying a single berth and the other occupying two adjacent berths.Five chapters are made.In Chapter 1,we shortly introduce the concepts of scheduling,online algorithm and competitive ratio.Then,we address the online BAP integrating QCAP,together with a definition of static/dynamic online algorithm.Chapter 2 studies the general problem with a sufficient number of berths.We first discuss the dominated schemes of the quay crane assignment,then two static online algorithms with competitive ratio 2 are designed for any even and odd number of quay cranes respectively.In Chapter 3,we present some optimal static algorithms for a small number of quay cranes.The competitive ratios are shown to be 5/4 if the quay crane number is 4,and to be 3/2 if there are 6,7 or 8 quay cranes.Chapter 4 is dedicated to the dynamic online algorithm for the case of 4 quay cranes.We show that the competitive ratio of any dynamic online algorithm is no smaller than 5/4.Hence the static algorithm without quay crane movement can work for this case as well.Finally,some concluding remarks are made in Chapter 5.