In this work we propose a decomposition approach to solve the quay crane scheduling problem. This is an important maritime transportation problem faced in container terminals where quay cranes are used to handle cargo. The objective is to determine a sequence of loading and unloading operations for each crane in order to minimize the completion time. We solve a mixed integer programming formulation for the quay crane scheduling problem, decomposing it into a vehicle routing problem and a corresponding scheduling problem. The routing sub-problem is solved by minimizing the longest crane completion time without taking crane interference into account. This solution provides a lower bound for the makespan of the whole problem and is sent to the scheduling sub-problem, where a completion time for each task and the makespan are determined. This scheme resembles Benders' decomposition and, in particular, the scheme underlying combinatorial Benders' cuts. We evaluate the proposed approach by solving instances from the literature and comparing the results with other available methods.