To address the challenge of mission re-planning when a deep space probe with multiple nodes landing on small celestial bodies, a planning constraint model and a re-planning algorithm are studied. Based on the multiple nodes collaborative working mechanism and complex time constraint forms, the graph representation of system and time constraints are defined, and a layered constraint graph is constructed to describe the deep space probe system. The proposed algorithm combines the idea of binary and dynamic programming, including a layered delay satisfaction verification mechanism and a layered constraint search algorithm. A delay satisfaction verification mechanism for burst constraints is established by hierarchical storage of constraints with different granularity. For the scenarios where the overall delay cannot meet all constraints, a multi granularity constraint search algorithm is proposed based on the hierarchical matching of constraints. Simulation experiments show that the proposed algorithm can quickly generate a re-planning result with minimal time constraint loss cost to meet the real-time autonomous decision-making requirements for deep space explorations.