Due to factors such as traffic congestion, differences in driver behavior, and fluctuations in gate queuing conditions, container terminals often find it difficult to accurately obtain the arrival times and sequences of external trucks, which may lead to a mismatch between the actual container pickup sequence and the yard storage configuration. To improve yard operational efficiency and reduce truck waiting time, this study investigates the container pre-marshalling problem under partial truck arrival information. A dynamic priority determination mechanism based on truck arrival times is constructed, and a target layout rule that ensures the dispersed stacking of containers with the same priority is proposed. With the objective of minimizing rehandling operation time, a mixed-integer linear programming model is developed, and an improved A* algorithm that considers cross-bay yard crane scheduling is designed. Finally, through comparative experiments involving the mathematical model, ablation variants, and Beam Search as a baseline algorithm, the effectiveness of the proposed model and algorithm is verified, and extended computational experiments and sensitivity analyses are conducted from multiple perspectives. The results show that the proposed dual-violation heuristic can significantly reduce the search space and improve computational efficiency; compared with Beam Search, the improved A* algorithm performs better in terms of solution quality. The findings provide theoretical support and methodological guidance for optimizing yard pre-marshalling operations and yard crane scheduling decisions at container terminals.