Abstract: Autonomous electromagnetic detection satellite (AEDS) is a type of earth observation satellites. The information collected by AEDS is very important in some application domain, such as industry, science and military. Considering the specific requirements and constraints of AEDS, this article established an ordered flexible topology directed acyclic graph onboard scheduling model, designed a scheduling algorithm based on graph label updating, and then analyzed the completeness and time complexity of the algorithm. Because of its high time complexity, the article introduced the concept of approximately dominant paths to our model. On this basis, we proposed an approximation algorithm which is improved from the original algorithm. Then, the time complexity and performance ratios of the approximation algorithm are analyzed. Finally, experiments are conducted to validate the proposed scheduling algorithms and demonstrate their practicability. The results show that the proposed approach can solve the AEDS onboard planning and scheduling problem effectively.

Key words: autonomous electromagnetic detection satellite, planning and scheduling, flexible topology directed acyclic graph model, label updating algorithm, performance ratio for approximation algorithm analysis