In response to the challenges posed by increasing container throughput and the trend towards larger vessels in automated container terminal operations, the integrated optimization of export container storage space allocation and yard crane scheduling has emerged as a critical research focus for enhancing yard efficiency. A longitudinally configured automated container terminal operating under a dynamic dual-crane relay mode was investigated. A multi-objective collaborative optimization model was developed with the aims of minimizing both the number of rehandling operations and the maximum completion time of yard cranes. To solve this model, a hybrid heuristic algorithm was designed that integrates NSGA-Ⅱ (non-dominated sorting genetic algorithm Ⅱ) with VNS (variable neighborhood search). The NSGA-Ⅱ performed global search while VNS enhanced local optimization through multiple neighborhood structures, thereby strengthening local search capabilities. Results from numerical experiments demonstrated that the completion time achieved by the hybrid algorithm was reduced by 4.4% to 10.9% compared to that obtained using traditional NSGA-Ⅱ methods. Through this proposed approach, an effective coordinated solution for export container storage space allocation and yard crane operation sequencing was generated, successfully achieving objectives related to reducing rehandling operations and shortening yard crane completion times.