This work addresses the Quay Crane Scheduling Problem under availability constraints, whose main goal is to determine the work schedules of the quay cranes allocated to a container vessel in order to carry out its transhipment operations (loading and unloading operations). An Estimation of Distribution Algorithm with shaking procedure is proposed to solve it. The position of the tasks and the operative areas of quay cranes are considered in the initialization step in order to reach high-quality regions of the search space. Computational experiments show that this method improves previous state-of-art approaches.