In the configuration process of import containers, external trucks who serve the same customer own the same arrival time, therefore the trucks’ arrival regularity present the characteristics of arrival in batch. The task assignment for trucks in the same batch will directly affect the operation efficiency of the corresponding yard crane, which implies the large optimization space. To solve this problem, based on the actual constraint that relocation operation can not be carried out across different bays, the yard crane scheduling is deconstructed into moving path scheduling and relocation scheduling. Accordingly, the mathematical optimization model for these two parts are formulated respectively. In order to get the optimal solution of the yard crane moving path optimization model, a polynomial time algorithm is developed and two auxiliary theorems are proved to support it. Meanwhile, a bi-level heuristic algorithm based on memory simulated annealing is developed to obtain satisfying solutions of the relocation optimization model. Experimental results show the effectiveness and robust of the optimization models and algorithms.