×

Multi satellites scheduling algorithm based on task merging mechanism. (English) Zbl 1410.90097

Summary: Earth observation satellites are platforms equipped with optical instruments that orbit the earth to take photographs of specific areas at users’ requests. Compared with huge user requests, satellites are still scanty resources. For some task, the satellite has to roll its camera to take the desired image. However, many satellites are rigidly restricted on maneuverability. As a result, the performances of satellites are greatly confined. Therefore, we need a scientific observation plan to weaken the constraints arising from satellites’ poor slew ability. To solve the problem we present a multi satellites scheduling algorithm based on task merging mechanism. The algorithm partitions the problem into two sub-problems: task assignment and task merging. In task assignment, we propose an adaptive ant colony optimization algorithm to select specific time window for each task, creating a task list for each satellite. In task merging, we propose the concept of task combination and develop a dynamic programming algorithm to find the best merging plan for each satellite. The two sub-problems are logically coupled; a valid observation plan will be got after much iteration. Finally, a series of test examples are given out, which demonstrate our algorithm to be effective.

MSC:

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68T05 Learning and adaptive systems in artificial intelligence
90C39 Dynamic programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

STK
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bianchessi, N.; Cordeau, J.-F.; Desrosiers, J.; Laporte, G.; Raymond, V., A heuristic for the multi-satellite, multi-orbit and multi-user management of Earth observation satellites, Eur. J. Oper. Res., 177, 750-762, (2007) · Zbl 1102.90327
[2] W. Pei, T. Yuejin, Joint scheduling of heterogeneous earth observing satellite for different stakeholders, in: SpaceOps 2008 Conference, Heidelberg, Germany, 2008.
[3] Y. Li, M. Xu, R. Wang, Scheduling observations of agile satellites with combined genetic algorithm, in: Third International Conference on Natural Computation, 2007.
[4] Hongyan, H.; Chongde, W.; Xiaoyong, W., Analysis on slewing effects of satellite and CCD camera’s parameters, Spacecraft Recovery Remote Sens., 24, 14-18, (2003), (in Chinese)
[5] Lin, W.-C.; Liao, D.-Y.; Liu, C.-Y.; Lee, Y.-Y., Daily imaging scheduling of an Earth observation satellite, IEEE Trans. Syst. Man Cybern. Part A Syst. Humans, 35, 213-223, (2005)
[6] Cordeau, J.-F.; Laporte, G., Maximizing the value of an Earth observation satellite orbit, J. Oper. Res. Soc., 56, 962-968, (2005) · Zbl 1274.86025
[7] Globus, A.; Crawford, J.; Lohn, J.; Morris, R., Earth observing fleets using evolutionary algorithms: problem description and approach, (Proceedings of the 3rd International NASA Workshop on Planning and Scheduling for Space, (2002), NASA Houston, Texas)
[8] Wolfe, W. J.; Sorenser, S. E., Three scheduling algorithms applied to the Earth observing systems domain, Manage. Sci., 46, 148-168, (2000) · Zbl 1231.90286
[9] Galvao, R. D.; Espejo, L. G.A.; Boffey, B., A comparison of Lagrangian and surrogate relaxations for the maximal covering location problem, Eur. J. Oper. Res., 24, 377-389, (2000) · Zbl 0967.90068
[10] L. Xiaolu, B. Baocun, C. Yingwu, L. Jufang, Dynamic programming algorithm for satellite orbit task merging problem, in: 60th International Astronautical Congress, Daejeon, Republic of Korea, 2009.
[11] Dorigo, M.; Stützle, T., Ant colony optimization, (2004), MIT Press Cambridge · Zbl 1092.90066
[12] Blum, Christian, Ant colony optimization: introduction and recent trends, Phys. Life Rev., 2, 353-373, (2005)
[13] Bullnheimer, B.; Hard, R. R.; Strauss, C., A new rank-based version of the ant system: a computational study, Cent. Eur. J. Oper. Res. Econ., 7, 25-38, (1999) · Zbl 0941.90063
[14] Qing-Bao, Z.; Zhi-Jun, Y., An ant colony optimization algorithm based on mutation and dynamic pheromone updating, J. Software, 12, 185-192, (2004) · Zbl 1107.68088
[15] Stützle, T.; Hoos, Holger H., MAX-MIN ant system, Future Gener. Comput. Syst., 16, 8, 889-914, (2000)
[16] Solomon, M. M., Algorithms for vehicle routing and scheduling problems with time window constraints, Oper. Res., 35, 254-265, (1987) · Zbl 0625.90047
[17] Analytical Graphics Inc., Satellite Tool Kit 6.0., <http://www.agi.com>.
[18] Baocun, B.; Yingwu, C.; Renjie, H.; Qiming, R., Multi·satellite scheduling toward spot and polygon observing requests, J. Astronaut., 30, 754-759, (2009)
[19] Dorigo, M.; Gambardella, L. M., Ant colony system: a cooperative learning approach to the travelling salesman problem, IEEE Trans. Evol., 1, 53-66, (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.