The Scheduling Problem Of Different Speed Cranes On The Container Terminal

In the container terminal,the vessel full of containers moor at the port,and parallel to the track where the cranes runs.Quay cranes are important equipments for loading or unloading containers.The container vessel is divided longitudinally between head（left）and tail（right）into holds.In order to ensure the operation of the cranes safely,they must strictly follow the non-crossing constraints during operation.There are many standards to evaluate the effectiveness of ports.The most important is the makespan of container vessels.It depends on the scheduling scheme of cranes to a large extent.Cranes may have different processing capabilities as they update continuously.This paper mainly studies the scheduling problem about three and m uniform quay cranes loading or unloading containers with non-crossing constraints.The objective is to minimize the makespan of a container vessel,which is the latest completion time among all handling holds of the vessel.This is of great significance for improving the turnover efficiency of vessels on the terminals.The structure of the paper is as follows:In the first chapter,we introduced related concepts of scheduling problems,research back-ground and current status of crane scheduling problems.We also show the main results and inno-vation points of this paper.In the second chapter,we study the scheduling problems of three cranes loading or unloading containers.The goal is to minimize the turnover efficiency of container vessel.It is assumed that the speeds of cranes are s₁,s₂,s₃ respectively（the sizes of s1,s2,s3 are uncertain）.First we prove that the problem is strong NP-hard,then we propose an approximation algorithm,and calculate that the worst performance ratio of the algorithm is 1+(（s₁+s₂+s₃）/（2s₁+s₂+s₃）.In the third chapter,we study the scheduling problems of m cranes loading or unloading containers.The goal is to minimize the turnover efficiency of container vessel too.It is assumed that the speeds of cranes are s₁,s₂,···,s_m respectively,where s₁≥1,s₂=···=s_m=1.First,an approximation algorithm is proposed to split the container ship from left to right into two parts,the left part is arranged to the crane Q₁,and the rest is arranged to the Q₂,···,Q_m according to the SPA,the algorithm proposed by Zhang An et al.And then we analysis the algorithm and calculate that the worst performance ratio of the algorithm is 2.The last chapter is the summary of the full article and an outlook for future research directions.