Multi-satellite ground-based access (MSGBA) has more and more requirements in the space industry, and the preparation time (PT) is required by the ground-based devices used in some MSGBA missions. As the mission scale grows, the PT requirements and the coupling of constraints make the planning of MSGBA complicated and difficult to solve. A heuristic genetic algorithm (GA) based on the constraint propagation is proposed to solve the MSGBA planning problem considering the PT constraint. The decoding process of the GA is designed that the allowable values of the undecoded genes are dynamically defined by the values of the genes already being decoded. This design would improve the algorithm’s ability to satisfy constraints. The proposed algorithm is validated by solving MSGBA problems with different scales. The results show that the performance of the proposed method is similar to the standard GA for small scale problems. For the large scale problems, the standard GA cannot converge, but the proposed method still shows a good performance.