Quay Cranes Scheduling Problem With Non-crossing Constraints

In the modern logistics industry, marine transportation is the main transportational way, which has become the pillar of international trade and the key power promoting trade globalization. According to China’s industrial information network news, around 70 percent of total international trade and around 90 percent of domestic trade by volume is carried by shipping. With the rapid development of domestic economy and its growing influence, China is up to the top position on global seaports container throughput.The competition among the world’s major ports is becoming more and more intensive.Therefore, how to improve the efficiency of port operation, especially, how to reduce the loading or unloading time of the terminal crane is distinctly important.In this thesis, we study the quay crane scheduling problem with noncrossing constraints. By scheduling the quay cranes at the container port to load or unload containers,our objective is to minimize the makespan of a container vessel. In this thesis, the approximation algorithms and the corresponding worst case analysis are given for this problem.The thesis is divided into four chapters.In Chapter 1, we first define the scheduling problems and introduce the concepts of computational complexity, approximation algorithms and the worst case ratios. Then, we give a formal description for the quay cranes scheduling with noncrossing constraints, as well as a mathematical programming model for the problem.Chapter 2 studies the m quay cranes scheduling problem. A new lower bound respect to the noncrossing constraints is provided, with which we can prove that the worst case ratio of the designed algorithm SPA is (2-2/m+1). By comparing the worst case ratios and the time complexity of all existed partition based algorithms, we show that SPA is the best possible one. Finally, the numerical experiments are carried out to evaluate the average performance of the algorithms.In Chapter 3, the scheduling problem of two quay cranes with different processing speeds is studied. For this problem, we first present a tighter analysis for an existed algorithm in the literature. Then an improved algorithm is proposed, which has worst case ratio of (s+1)2/1+s+s2, where s≥1 is the speed ratio of the two quay cranes.Finally, we make conclusions for the thesis and discuss the further research directions.