Crane scheduling in container terminals is known as a difficult optimization problem that has become even more challenging in recent years with the proliferation of multi-gantry automated stacking cranes. In this paper we present an efficient algorithm solving a subproblem arising in this context, namely deciding the priority of cranes after transportation tasks have been assigned. We tackle this problem for both, twin crane setting and crossover crane setting, and develop graphical models and strongly polynomial algorithms accordingly. A series of experiments is carried out where it is shown that the method can produce optimum solutions within exceptionally small run times.