Earth Observation Satellites Scheduling Based on Decomposition Optimization Algorithm

Full Text (PDF, 248KB), PP.10-18

Views: 0 Downloads: 0


Feng Yao 1,* Jufang Li 1 Baocun Bai 1 Renjie He 1

1. College of Information Systems and Management, National University of Defense Technology, Changsha, China

* Corresponding author.


Received: 15 Jul. 2010 / Revised: 20 Aug. 2010 / Accepted: 23 Sep. 2010 / Published: 8 Nov. 2010

Index Terms

Earth Observation Satellites, decomposition, adaptive ant colony optimization, heuristic algorithm, very fast simulated annealing


A decomposition-based optimization algorithm was proposed for solving Earth Observation Satellites scheduling problem. The problem was decomposed into task assignment main problem and single satellite scheduling sub-problem. In task assignment phase, the tasks were allocated to the satellites, and each satellite would schedule the task respectively in single satellite scheduling phase. We adopted an adaptive ant colony optimization algorithm to search the optimal task assignment scheme. Adaptive parameter adjusting strategy and pheromone trail smoothing strategy were introduced to balance the exploration and the exploitation of search process. A heuristic algorithm and a very fast simulated annealing algorithm were proposed to solve the single satellite scheduling problem. The task assignment scheme was valued by integrating the observation scheduling result of multiple satellites. The result was responded to the ant colony optimization algorithm, which can guide the search process of ant colony optimization. Computation results showed that the approach was effective to the satellites observation scheduling problem.

Cite This Paper

Feng Yao,Jufang Li,Baocun Bai,Renjie He, "Earth Observation Satellites Scheduling Based on Decomposition Optimization Algorithm", IJIGSP, vol.2, no.1, pp.10-18, 2010. DOI: 10.5815/ijigsp.2010.01.02


[1]Robert A Morris, Jennifer L Dungan, John L. Bresina. An Information Infrastructure for Coordinating Earth Science Observations. In Proc. 2nd IEEE International Conference on Space Mission Challenges for Information Technology. 2006

[2]Wei-Cheng Lin, Da-Yin Liao, Chung-Yang Liu, Yong-Yao Lee. Daily Imaging Scheduling of an Earth Observation Satellite. IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART A: SYSTEMS AND HUMANS, vol. 35, pp.:213-223, 2005

[3]Bensana E, Verfaillie G, Bataillie N, Bluestein D. Exact and Approximate Methods for the Daily Management of an Earth Observing Satellite. Proceedings of SpaceOPS, Germany: Munich, 1996.

[4]XU Xue-ren, GONG Peng, HUANG Xue-zhi, Jin Yong. Study on Optimization Algorithms for Remote Sensing Date Collection Planning of Satellite. Journal of Remoter Sensing, vol. 56, pp. :962-968, 2007(In Chinese)

[5]Nicola Bianchessi, Jean-Francois Cordeau, Jacques Desrosiers, Gilbert Laporte, Vincent Raymond. A Heuristic for the Multi-Satellite, Multi-Orbit and Multi-User Management of Earth Observation Satellites. European Journal of Operational Research. vol. 177, pp. 750-762, 2005

[6]Cordeau J-F, Laporte G. Maximizing the Value of an Earth Observation Satellite Orbit. Journal of the Operational Research Society, vol. 56, pp. :962-968, 2005

[7]HE Ren-jie. Research on Imaging Reconnaissance Satellite Scheduling Problem. PhD thesis, Nation University of Defense Technology, 2004

[8]M. Lemaître, G. Verfaillie. Selecting and scheduling observations of agile satellites. Aerospace Science and Technology. 2002,(6) :367-381

[9]Wolfe W.J, Sorensen S.E. Three Scheduling Algorithms Applied to the Earth Observing Systems Domain. Management Science, vol. 46, pp. 148~168, 2000

[10]Dorigo M, Stutzle T. Ant Colony Optimization. Cambridge, MA: MIT Press, 2004

[11]Christian Blum, Ant colony optimization: Introduction and recent trends. Physics of Life Reviews, vol. 2, pp. :353–373, 2005

[12]B. Bullnheimer, R. R Hard, C. Strauss. A new rank-based version of the Ant System: A computational study. Central European Journal for Operations Research and Economics, vol. 7, pp. :25-38, 1999

[13]ZHU Qing-Bao, YANG Zhi-Jun. An Ant Colony Optimization Algorithm Based on Mutation and Dynamic Pheromone Updating. Journal of Software, vol. 12, pp. 185-192, 2004

[14]WANG Ying, XIE Jian–ying. An Adaptive Ant Colony Optimization Algorithm and Simulation. JOURNAL OF SYSTEM SIMULATION, vol. 14, pp. 31-33, 2002

[15]Stutzle T, Hoos H H. MAX-MIN ant system. Future Generation Computer Systems, vol. 16, pp. 889-914, 2000

[16]Ingber L. Very Fast Simulated Re-annealing. Math Compute Modelling, vol. 12, pp. :967-973, 1989

[17]CHEN Huagen, LI Lihua, XU Huiping, CHEN Bing. Modified Very Fast Simulated Annealing Algorithm. JOURNAL OF TONGJI UNIVERSIT (NATURAL SICENCI), vol. 34, pp. 1121-1125, 2006

[18]Analytical Graphics Inc. Satellite Tool Kit 6.0.