| Angelo Oddi |
a.oddi@istc.cnr.it |
| Nicola Policella |
policella@istc.cnr.it |
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 quality downlink schedules in a spacecraft domain where an high degree of uncertainty can be met. 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 investigators - and different sources of uncertainty - e.g., the amount of data generated at each scientific observation or the channel data rate. The 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 idea behind such a point is that the lower are the peaks in memory utilization, the higher the ability of facing unexpectedly larger amount of data.
pdf file
