A greedy strategy genetic algorithm (GS-GA) based mission planning method is designed for two types of on-orbit service missions: on-orbit fuel refueling and space debris removal. Firstly, the hybrid optimal control (HOC) model of on-orbit service mission planning is established, the discrete state space and continuous dynamic system are designed. And the optimization objectives are analyzed to construct the HOC mathematical description. Secondly, for the combinatorial optimization problem, GS-GA is proposed, which makes the solution space closer to the optimal solution and improves the accuracy of the algorithm. Finally, practical simulation scenarios are given to verify the algorithm’s feasibility and accuracy.