Research On Imaging Reconnaissance Satellite Scheduling Problem

The mission of scheduling imaging reconnaissance satellite (IRS) is to allocate satellite system resources optimally, and make the most of the limited resources in order to satisfy multifarious imaging requests from customers in the future battlefields. IRS is a kind of earth observing satellite. The scheduling problem of multi earth observing satellites is still a brand new problem to people at present, and there are few research reports about the multi observing satellite scheduling problem from the point view of integrating model, algorithm and software system. Thereby, it is a significative job to do research on IRS scheduling problem, which will not only promote the theoretic advances in the multi observing satellite scheduling problem domain, but also lay the foundation for future real life satellite application. Based on the analysis of the characteristic of principles and custom requests of IRS, this thesis gives the scheduling models and corresponding algorithms of IRS scheduling problem, and beyond this, a software system is also presented in the paper. The main contents and fruits of this thesis are outlined as follows:Firstly, on the basis of analysis of characteristic of IRS, we summarize main constraints existing in scheduling of IRS, and divided the scheduling process into two main steps: pretreatment and optimization. The task of pretreatment is to filter satellite system resources according to custom requests, and give the available resources for accomplishing requests. Whereas, the objective of optimization is to decide which request will be scheduled, and allocate resources and time slots for those scheduled requests. By adopting the pretreatment process, the requests which have no time slots or available resources will be discarded prior to optimization process, and the computational time will reduce accordingly.Secondly, based on the summarized scheduling constraints and some reasonable assumptions, we put forward two models of IRS scheduling problem: mixed integer programming (MIP) model and constraint satisfaction problem (CSP) model, and also give the corresponding algorithms of the model: tabu search and column generation, respectively. Within the tabu search algorithm, we define a backward time slack for each task, which measures how far a task can be shifted backward in time without violating other tasks' constraints. On the basis of the computation of backward time slack, the initial solution algorithm and several special neighborhood structures are also presented. In the column generation algorithm, we decompose multi satellite scheduling problem into a set partition master problem and a single satellite scheduling sub problem. The overall model is then solved by solving the master and sub problem iteratively. For solving the sub problem, we transform it into a shortest path problem with timewindow constraint, and give the corresponding algorithm. The algorithm is suit for general graph which contrains negative cost cycles.Thirdly, on the basis of the research on the model and algorithm, we design and develop IRS scheduling software system. Comparable with other overseas similar system, our software system can manage satellite resource visually, analyse available resources for each tasks automatically, filter the impossible tasks in advance, and also give the reasons for each failure task. Besides all above, our system also provides diversiform charts for visualizing the ultimate schedule results, and simulates the reconnaissance tasks via commercial software STK's 3D simulation module, which makes analyzing the scenario more easily to users.