Optimal Scheduling Model Of Space TT&C System And Its Lagrangean Relaxation Solution Algorithms

The Space Tracking Telemetry and Command (TT&C) System optimal scheduling is to appropriately and effectively assign TT&C resource and their use time to various types of spacecrafts when given the configuration of both space and ground TT&C resource, so that TT&C requirements of all spacecrafts can be best satisfied. The Space TT&C System optimal scheduling problem is a combinatorial optimization problem with time windows and has various kinds of constraints, many involved elements and complex relations between elements. These characteristics make it difficult to describe and solve the problem. Research on model and algorithm of Space TT&C System optimal scheduling problem can support planning and decision-making of Space TT&C system and provide Space TT&C System scheduling alternatives for TT&C management department. The main research works are:(1) Research on the Space TT&C System optimal scheduling modelThe limitations of using task useable time window as decision variable for Space TT&C System optimal scheduling is analyzed, and the concept of task possible start time is proposed. The characteristics of using task possible start time as decision variable of Space TT&C System optimal scheduling is discussed. All constraints are divided into hard constraints and soft constraints according to the intensity of the constraint, and the constraints are distinctively treated in the process of Space TT&C System optimal scheduling. All hard constraints are classified into four categories according to constraints'object: time window constraint, TT&C task constraint, TT&C equipment constraint and spacecraft constraint. Both spacecraft user and TT&C equipment manager's requirements on Space TT&C System optimal scheduling are jointly considered, and the objective function of Space TT&C System optimal scheduling is proposed. Based on using task possible start time as decision variable to formally describe all kinds of hard constraints and objective function, the Space TT&C System optimal scheduling 0-1 integral programming model is constructed. The model can more adequately utilize TT&C equipment resource, and overcome the other models'disadvantage on designing optimal solution algorithm. The model provides a basis for designing solution algorithm of Space TT&C System optimal scheduling problem's upper bound and feasible solution.(2) Research on upper bound solution method of Space TT&C System optimal scheduling problemBased on the Space TT&C System optimal scheduling 0-1 integral programming model, three relaxation strategies and corresponding Space TT&C System optimal scheduling Lagrangian relaxation problem are designed and their solutions are investigated, then how to select an appropriate relaxation strategy is discussed. To obtain upper bound of Space TT&C System optimal scheduling problem, Space TT&C System optimal scheduling Lagrangian dual problem is constructed. Base on general subgradient optimization algorithm, history subgradient optimization algorithm is designed to solve Lagrangian dual problem, and it is proven that history subgradient optimization algorithm is better than general subgradient optimization algorithm on convergence. The upper bound of Space TT&C System optimal scheduling problem obtained from history subgradient optimization algorithm can evaluate the performance of other heuristics and the rationality of the current scenario's configuration.(3) Research on optimal solution method of Space TT&C System optimal scheduling problemThe purpose of Space TT&C System optimal scheduling is to obtain Space TT&C System scheduling alternatives in current scenario's configuration. When the scale of Space TT&C System optimal scheduling problem is relatively small, it is possible to obtain the optimal solution of Space TT&C System optimal scheduling problem in acceptable time. Space TT&C System optimal scheduling heuristic information obtained in the process of solving upper bound is analyzed, the branch strategy utilizing heuristic information is designed, and a branch and bound algorithm based on Lagrangian relaxation for solving Space TT&C System optimal scheduling problem is constructed.(4) Research on satisfactory solution method of Space TT&C System optimal scheduling problemWhen the scale of Space TT&C System optimal scheduling problem is large, obtaining the optimal solution in acceptable time is difficult. In view of this situation, a choosing strategy on fix variable utilizing Space TT&C System optimal scheduling heuristic information is designed, and a Lagrangian heuristic algorithm based on fix-relax strategy is designed combined with Lagrangian relaxation algorithm, then a satisfactory solution of Space TT&C System optimal scheduling problem can be obtained in acceptable time which can better satisfy the requirement of large scale Space TT&C System optimal scheduling problem.(5) Research on optimizing method of Space TT&C System scheduling alternativesBecause the soft constraints of Space TT&C System optimal scheduling is not onsidered when solving Space TT&C System scheduling alternatives, so an optimizing method of Space TT&C System scheduling alternatives according to soft constraints of Space TT&C System optimal scheduling is designed in the dissertation. When using task possible start time as decision variable of Space TT&C System optimal scheduling, additional constraint is imposed on TT&C task execution time. Therefore, a method of optimizing TT&C time of Space TT&C System scheduling alternatives by removing the increased constraint is designed. Through optimizing the Space TT&C System scheduling alternatives, the violation of soft constraints will decrease while TT&C equipment utilization rate will increase.