We study the scheduling of quay cranes with non-crossing constraints. New lower bounds on the optimal solutions are provided. A new algorithm is designed and analysed for m quay cranes. Discussions on several previous algorithms and the computational experiments are made. An approximation algorithm for two quay cranes with different speeds are presented.