Two Quay Crane Scheduling Problems With Non-crossing Constraints

Quay crane scheduling is one of the most important operations in a container termi-nal.It directly determines the terminal's efficiency and competitiveness.Quay crane scheduling(QCS in short)with non-crossing constraints has been studied through many OR methods in the literature.In this thesis,we introduce two more realistic scenarios to QCS.One is the safety margins between quay cranes.The other is the partial non-crossing constraints.To minimize the overall time of loading/unloading containers to/from a series of discrete holds,we design polynomial time approximation algorithms with performance guarantees.Four chapters are made.In Chapter 1,we give a brief introduction to scheduling and algorithms,as well as the quay crane scheduling models.We compare the difference between QCS and the classical parallel machine scheduling.Chapter 2 studies the scheduling of m quay cranes with non-crossing constraints and safety margins.Usually a safety margin is defined as the smallest number of holds between adjacent working quay cranes in the literature.We consider the case when the safety margin is equal to 1,for which a(2-2/m+1)-approximation algorithm is provided.One may observe that the algorithm can apply to any fixed safety margin.In Chapter 3,one quay crane in the m-quay-crane system is replaced by a gantry crane which can cross over quay cranes.We show that with this gantry crane,there exists a better partition-based algorithm with worst case ratio 2-2/m.Therefore,it indicates that relaxing the non-crossing constraints does benefit in improving algorithms' performance.Finally,we make conclusion in Chapter 4.