A two-phase scheduling method with the consideration of task clustering for earth observing satellites

作者：Wu, Guohua^*; Liu, Jin; Ma, Manhao; Qiu, Dishan

来源：Computers & Operations Research, 2013, 40(7): 1884-1894.

DOI：10.1016/j.cor.2013.02.009

• Satellite scheduling
• Task clustering
• Clique partition
• Ant colony optimization
• Local search

Satellite observation scheduling plays a significant role in improving the efficiency of satellite observation systems. Although extensive scheduling algorithms have been proposed for the satellite observation scheduling problem (SOSP), the task clustering strategy has not been taken into account up to now. This paper presents a novel two-phase based scheduling method with the consideration of task clustering for solving SOSP. This method comprises two phases: a task clustering phase and a task scheduling phase. In the task clustering phase, we construct a task clustering graph model and use an improved minimum clique partition algorithm to obtain cluster-tasks. In the task scheduling phase, based on overall tasks and obtained cluster-tasks, we construct an acyclic directed graph model and utilize a hybrid ant colony optimization coming with a mechanism of local search, called ACO-LS, to produce optimal or near optimal schedules. Extensive experimental simulations demonstrate the efficiency of the proposed scheduling method.

• 出版日期2013-7
• 单位中国人民解放军国防科学技术大学