A Max-Flow Approach for Improving Robustness in a Spacecraft Downlink Schedule
Angelo Oddi, Nicola Policella · 2004
Abstract. 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 qual-ity 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 MEX-MDP 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 investiga-tors- 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 uti-lization 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. 1