Improving Robustness of Spacecraft Downlink Schedules

In the realm of scheduling problems different sources of uncertainty can invalidate the planned solutions: unpredictability of activity behaviors, machine breakdowns, new activities to be served, and so on. 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 arose in the European Space Agency program MARS-EXPRESS. A MEX-MDP consists in the generation of dumping commands to maximize the downloads of data sets from the satellite to the ground. The domain is characterized with 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 payload requirements - and different sources of uncertainty - e.g., the amount of data generated at each scientific observation or the channel data rate. In this paper we tackle this problem by using a reduction of the MEX-MDP to a Max-Flow problem: the former problem has a solution when the maximum flow in the latter equates the total amount of data to dump. Given this reduction, we introduce a novel definition of solution robustness based on the utilization of the on-board memory, as well as an iterative procedure to improve solution quality. The key idea behind this approach is that the lower the peaks in memory utilization, the higher the ability cope with unexpectedly large amount of data.