×

zbMATH — the first resource for mathematics

Evaluation of struggle strategy in genetic algorithms for ground stations scheduling problem. (English) Zbl 1311.90056
Summary: Ground station scheduling problem arises in spacecraft operations and aims to allocate ground stations to spacecraft to make possible the communication between operations teams and spacecraft systems. The problem belongs to the family of satellite scheduling for the specific case of mapping communications to ground stations. The allocation of a ground station to a mission (e.g. telemetry, tracking information, etc.) has a high cost, and automation of the process provides many benefits not only in terms of management, but in economic terms as well. The problem is known for its high complexity as it is an over-constrained problem. In this paper, we present the resolution of the problem through struggle genetic algorithms – a version of GAs that distinguishes for its efficiency in maintaining the diversity of the population during genetic evolution. We present some computational results obtained with struggle GA using the STK simulation toolkit, which showed the efficiency of the method in solving the problem.

MSC:
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
Software:
STK
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Badaloni, S.; Falda, M.; Giacomin, M., Solving temporal over-constrained problems using fuzzy techniques, J. Intell. Fuzzy Systems, 18, 3, 255-265, (2007) · Zbl 1152.90518
[2] L. Barbulescu, A. Howe, J. Watson, L. Whitley, Satellite range scheduling: A comparison of genetic, heuristic and local search, in: Parallel Problem Solving from Nature - PPSN, VII, 2002, pp. 611-620.
[3] Barbulescu, L.; Watson, J.-P.; Whitley A, L. D., Scheduling space-ground communications for the air force satellite control network, J. Sched., 7, 1, 7-34, (2004) · Zbl 1306.90046
[4] L. Barbulescu, A.E. Howe, L.D. Whitley, M. Roberts, Trading places: How to schedule more in a multi-resource oversubscribed scheduling problem, in: Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling (ICAPS-2004), 2004, pp. 227-234.
[5] Barbulescu, L.; Howe, A. E.; Whitley, D., AFSCN scheduling: how the problem and solution have evolved, Math. Comput. Modelling, 43, 9-10, 1023-1037, (2006) · Zbl 1170.90385
[6] S. Damiani, H. Dreihahn, J. Noll, M. Niézette, G.P. Calzolari, A planning and scheduling system to allocate ESA ground station network services, in: The Intʼl Conference on Automated Planning and Scheduling, USA, 2007.
[7] ESA Science & Technology, http://www.esa.int/.
[8] T. Grueninger, Multimodal optimization using genetic algorithms, Technical Report, Department of Mechanical Engineering, MIT, Cambridge, MA, 1997.
[9] Pemberton, J. C.; Galiber, F., A constraint-based approach to satellite scheduling, (Freuder, Eugene C.; Wallace, Richard J., DIMACS Workshop on Constraint Programming and Large Scale Discrete Optimization, (2000), American Mathematical Society Boston, MA, USA), 101-114 · Zbl 0983.90023
[10] A. Sarkheyli, B.G. Vaghei, A. Bagheri, New tabu search heuristic in scheduling earth observation satellites, in: Proceedings of 2nd International Conference on Software Technology and Engineering (ICSTE), 2010, pp. V2-199-V2-203.
[11] Scherer, W. T.; Rotman, F., Combinatorial optimization techniques for spacecraft scheduling automation, Ann. Oper. Res., 50, 1, 525-556, (1994) · Zbl 0812.90108
[12] Satellite Tool Kit, http://www.agi.com/products/by-product-type/applications/stk/.
[13] Zufferey, N.; Amstutz, P.; Giaccari, P., Graph colouring approaches for a satellite range scheduling problem, J. Sched., 11, 4, 263-277, (2008) · Zbl 1168.90481
[14] J. Sun, F. Xhafa, A genetic algorithm for ground station scheduling, in: International Conference on Complex, Intelligent and Software Intensive Systems, CISIS 2011, Korea, June 30-July 2, 2011, pp. 138-145.
[15] F. Xhafa, J. Sun, A. Barolli, M. Takizawa, K. Uchida, Evaluation of genetic algorithms for single ground station scheduling problem, in: IEEE 26th International Conference on Advanced Information Networking and Applications, AINA-2012, Japan, March 26-29, 2012, pp. 299-306.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.