Research On Agile Satellite Scheduling Problem Based On Mixed-Initiative

Agile satellite is a new generation earth observing satellite. Agile satellite increasesdramastically the earth observing modes and agilities, which makes the scheduling problemmuch more combinatorial and complex. Agile satellite scheduling problem is over-constrained,with scarce resources allocated to numerous user requests.Traditional satellite schedules are made manually by schedulers. The dramasticallyincreasing user requests and complex observing modes of agile satellite leave no room for puremanual scheduling. Automated scheduling promises to reduce the number of conflicts, butcannot incorporate the scheduler’s domain expertise and preference. Thus the automaticallygenerated schedule seldom meets the human scheduler’s satisfaction. Mixed-Initiative (MI)scheduling is a promising way to interleave the contribution of human scheduler and systemautomation.By reviewing the related work, we investigated the application of MI in agile satellitescheduling. The main contribution of our work includes:(1) An agile satellite MI scheduling system architechture was presented. The twocomponents of the architechture are interactive display interface and scheduler. Interactivedisplay indicates the “human initiative”. We analyse and summarise the six adjustment requestsof human scheduler, which determines where and how much the human scheduler can apply theirdomain expertise and preference. The scheduler is responsible for the “system initiative”. Inorder to facilitate providing tips for human adjusting and quick schedule refinement, thescheduler maintains a flexible schedule. The MI architechture is based on the two-stagescheduling strategy: the first stage for generating initial flexible schedule, the second stage forMI schedule adjustment.(2) A heuristic constructive algorithm was designed for generating flexible schedule. A taskneed heuristic and a resource contention heuristic were proposed, for making task selection andtime slot selection decision respectively. Then the flexible schedule is constructive byincorporating the heuristic search and constraint propagation. The validity of the algorithm wastestified through computational experiment.(3) Two solving techniques were presented for the MI schedule adjustment stage. Sixadjustment requests can be in nature classified into two parts: move activity within the windowand activity insertion. A minimal perturbation algorithm was proposed to find a new schedulethat is the closest to the reference schedule. A slack-based heuristic is added to the acitivityinsertion search procedure, to maintain a high level flexibility for the refined flexible schedule. (4) A MI agile satellite scheduling software was developed based on the above research fruit.The design and realization of the resource mixed-initiative scheduling sub-system was presentedin detail. An empirical study was described to prove the validaty of the proposed architechtureand algorithms.