An Automatic Planning and Scheduling System for the Mars Express Uplink Scheduling Problem

• Published in: IEEE transactions on human-machine systems 2011-11, Vol.41 (6), p.942-954
• Main Authors: Donati, A., Policella, N., Rabenau, E., Righini, G., Tresoldi, E.
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Algorithmics. Computability. Computer arithmetics; Algorithms; Applied sciences; Computer science; control theory; systems; Exact sciences and technology; Heuristic algorithms; Heuristics; Inventory control, production control. Distribution; Mars; Maximization; Operational research and scientific management; Operational research. Management science; optimization; planning and scheduling; Robustness; Schedules; Scheduling; Scheduling algorithm; Scheduling, sequencing; Segments; Software; Software engineering; Space missions; Studies; Theoretical computing; Windows (intervals)
• ISSN: 1094-6977; 2168-2291; 1558-2442; 2168-2305
• DOI: 10.1109/TSMCC.2011.2114880

This paper describes the algorithms used in a planning and scheduling software tool developed for the European Space Agency in the framework of the Mars Express mission. The planning and scheduling algorithm computes a feasible schedule for the transmission of telecommands (TCs) from the ground segment to the space segment, complying with a number of technical constraints. Owing to the distance between Mars and Earth, it is important that the robustness of the schedule is taken into account because repair operations may be very time consuming or even impossible. For this reason, besides the maximization of the number of TCs transmitted from Earth to Mars, the scheduler is also designed to maximize the number of full confirmations and secondary time windows, which are two special characteristics of the Mars Express schedule explicitly designed for the sake of robustness. Besides the maximization of robustness, the scheduling algorithm that can run with different settings can be used to optimize some secondary figures of merit, such as the average saturation of the memory devices of the space segment and the usage of the time windows available for communication. Computational results on real instances are presented.