Scheduling a constellation of agile earth observation satellites with preemption

Document Type : Research Paper


Ferdowsi University of Mashhad


In this paper, we consider a scheduling problem for a set of agile Earth observation satellites for scanning  different parts of the Earth’s surface. We assume that preemption is allowed to prevent repetitive images and develop four different preemption policies. Scheduling is done for the imaging time window and transmission time domain to the Earth stations as well. The value of each picture from different target regions and the limitations of the satellite constellation in terms of memory and energy cause high computational complexity for this problem and thus obtaining an optimum solution with a deterministic method is very time-consuming. Consequently, a genetic-based metaheuristic algorithm with a specific solution representation is developed in order to maximize the total value of the observation process by establishing heuristic rules in the initial population of this algorithm. Comparison of the results from the proposed model with the results of cases where repetition of observed areas is not ignored indicates that the proposed model can bring about a significant increase in profits in the planning horizon.


Bianchessi, N., & Righini, G. (2008). Planning and scheduling algorithms for the COSMO-SkyMed constellation,
Aerospace Science and Technology, v12(7), 535–544.
Chen, Y., Zhang, D., Zhou, M., & Zou, H. (2012). Multi-satellite Observation Scheduling Algorithm Based on Hybrid
Genetic Particle Swarm Optimization. In D. Zeng (Ed.), Advances in Information Technology and Industry
Applications (Vol. 136). Berlin, Heidelberg: Springer Berlin Heidelberg.
Florio, S. De. (2006). Performances Optimization of Remote Sensing Satellite Constellations: a Heuristic Method, In
Proceedings of the 5th international workshop on planning and scheduling for spacev,
Frank, J., Jónsson, A., & Morris, R. (2001). Planning and scheduling for fleets of earth observing satellites, In
Proceedings of Sixth Int. Symp. on Artificial Intelligence, Robotics, Automation & Space,
Gabrel, V., Moulet, A., Murat, C., & Paschos, V. T. (1997). A new single model and derived algorithms for the satellite
shot planning problem using graph theory concepts, Annals of Operations Research, 69, 115–134.
Lemaı̂tre, M., Verfaillie, G., Jouhaud, F., Lachiver, J.-M., & Bataille, N. (2002). Selecting and scheduling observations
of agile satellites, Aerospace Science and Technology, 6(5), 367–381.
Morena, L. C., James, K. V, & Beck, J. (2014). An introduction to the RADARSAT-2 mission. Canadian Journal of
Remote Sensing, 30(3), 221–234.Wang, P., & Reinelt, G. (2010). A Heuristic for an Earth Observing Satellite
Constellation Scheduling Problem with Download Considerations, Electronic Notes in Discrete Mathematics, 36,
Tangpattanakul, P., Jozefowiez, N., & Lopez, P. (2015). A multi-objective local search heuristic for scheduling Earth
observations taken by an agile satellite, European Journal of Operational Research, 245(2), 542–554.
Wang, P., Reinelt, G., Gao, P., & Tan, Y. (2011). A model, a heuristic and a decision support system to solve the
scheduling problem of an earth observing satellite constellation, Computers & Industrial Engineering, 61(2), 322–335.
Wang, J., Demeulemeester, E., & Qiu, D. (2016). A pure proactive scheduling algorithm for multiple earth observation
satellites under uncertainties of clouds, Computers and Operations Research, 74, 1-13.
Xu, R., Chen, H., Liang, X., & Wang, H. (2016). Priority-based constructive algorithms for scheduling agile earth
observation satellites with total priority maximization, Expert Systems with Applications, 51, 195-206.