**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.