Research On Dynamic Rescheduling Model, Algorithm And Its Applications Of Imaging Reconnaissance Satellite Scheduling Problem

The scheduling of imaging reconnaissance satellite (IRS) is to allocate satellite system resources optimally according to the user's requirement, and make the most use of the limited resources in order to satisfy multifarious imaging requirement in the future battlefields. The state of the satellite may be changed by some different disturbing factors that make the satellites invalidated in a period in its complex working environment. At the same time, the requirements may be adjusted by users to be suit to the practice. All of these changes will make the initial schedule not suitable and must be adjusted after that. The new schedule after adjustment should be minimal near to the initial one for the actual application.IRS is a kind of Earth Observing Satellite (EOS). The dynamic scheduling problem of multi earth observing satellites is still a brand new problem to all people in domestic and overseas at present, and there are few research reports about that. Based on the analysis of the characteristic of working principles and custom requests of IRS, this thesis gives the initial scheduling models and corresponding algorithms of IRS scheduling problem, and then gives the dynamic constraint satisfaction model and corresponding algorithms for two kind of emergency including some satellite resource broken down and new tasks' arriving using the idea of reactive rescheduling. At last, it provides an actual instance to show how to use the models and algorithms. The main research contents and innovations are as follows:(1) Summarizing the main constraints of scheduling of IRS and partitioning it into two stages just as pretreatment and optimization based on the analysis of characteristic of IRS. The task of pretreatment process is to filter the 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 windows for those scheduled requests. This work is an innovation of the paper.(2)Analyzing the main kinds of multi-IRS dynamic scheduling with the characteristic for each one, then giving time-line constraint conceptual model, resource-central constraint conceptual model and task-central constraint conceptual model. This work is an innovation of the paper.(3)A constraint satisfaction scheduling model for the initial scheduling problem and a greedy algorithm for it are given based on the constraints analysis and some basic hypothesis.(4)A dynamic constraint satisfaction model for multi-IRS dynamic scheduling problem considering the satellite resources may be broken down and two methods to solve the problem were given: a heuristic search algorithm. These works are the one main innovation of the paper.(5) A dynamic constraint satisfaction model of multi-IRS scheduling containing the new tasks is given, and two algorithms, namely dynamic backtrack and incremental scheduling based on local repair algorithm, are given to solve the model at the same time. These works are the one main innovation of the paper.(6) Based on the basis of the research on the models and algorithms, an instance is designed to show how to use the models and algorithms at last.