New quay cranes (QCs) have been designed to increase terminal productivity by lifting more containers simultaneously. But QC productivity relies on efficient cooperation with the vehicles carrying the containers. This paper investigates the synchronization scheduling problem between the automated guided vehicles and these new QCs. The problem is formulated as a mixed integer linear programming model. Because of the problem's complexity, a heuristic dispatch rule is proposed for practical purposes. Then, to balance the computation time and the quality of the solution, a neighborhood search method is designed by investigating the working sequences of automated guided vehicles. Numerical experiments show that both heuristics obtain good solutions within extremely short times and that the neighborhood search method generally performs better in relation to the objective value.