Scheduling the contact between the navigation satellites and ground unlink stations and navigation data uplink process is of important significance to keep the accuracy of the navigation data on board. After analyzing the navigation data uplink process of the satellite navigation system, a multi-objective mix-integer model was devised, considering the technological constraints in uplink process. Because of the complexity of the model, a two-phase heuristic algorithm based on rules is devised. A set of test scenarios were devised consulting the COMPASS of China, the GPS Satellite Navigation Systems. The mathematical model and algorithm proved effectively for the uplink task schedule process. Several factors that influence the completion of the uplink tasks were obtained by analyzing the computational results. 