A Max-Flow Approach for Improving Robustness in a Spacecraft Downlink Schedule

A. Oddi and N. Policella

In Proceedings of IWPSS-04. Fourth International Workshop for Planning and Scheduling for Space. ESA-ESOC, Darmstadt, Germany, June (WPP-228, ESA Publication Division) pp. 151-158, 2004

In the realm of scheduling problems different sources of uncertainty can invalidate the solutions. In this paper we are concerned with the generation of high quality downlink schedules in a spacecraft domain in presence of a high degree of uncertainty. In particular, we refer to a combinatorial optimization problem called MARS EXPRESS Memory Dumping Problem (MEX-MDP), which arises in the European Space Agency program MARS EXPRESS. A MEXMDP consists in the generation of dumping commands for transferring the whole set of data from the satellite to the ground. The domain is characterized by several kinds of constraints - such as, bounded on-board memory capacities, limited communication windows over the downlink channels, deadlines and ready times imposed by the principal investigators - and different sources of uncertainty - e.g., the amount of data generated at each scientific observation or the channel data rate. This work describes a reduction of the MEX-MDP to a Max-Flow problem, such that the problem has a solution when the maximum flow equates the total amount of data to dump. Based on this reduction, an iterative procedure is built to improve the robustness of a solution with respect to the utilization of the on-board memory. The underlying idea being that the lower are the peaks in memory utilization, the higher the ability of facing unexpectedly larger amount of data.