Scheduling Data Transfer with Priorities and Interruptions for Space Missions

In the context of space missions, an efficient data transferstrategy is crucial to avoid onboard buffer overflow. In manymissions, such as the ESA’s Rosetta mission, the data producedby each instrument is temporarily stored in a dedicatedbuffer and then dumped to Earth during downlink windowsunder a limited bandwidth. Previous work has considered theoverlapping Memory Dumping Problem (oMDP), which consistsin assigning transfer priorities to the memory buffers andminimize the peaks memory usage. The oMDP is NP-hardand has been tackled using heuristic methods that demonstratedtheir efficiency on real instances. In this paper, we consideradditional decisions in the memory dumping plans thatare implementable in practice: data transfer from each buffercan be interrupted after a given time, once per downlink window,preventing it from dumping data until the next window.The new problem is called oMDPi (oMDP with interruptions).We obtain several structural properties and complexityresults, showing in particular that oMDPi is NP-hard for atleast two windows. While the complexity status of the singlewindow oMDPi remains open, we propose a polynomial-timeheuristic to solve it.We propose a hybrid heuristic to solve thegeneral oMDPi, embedding a flow relaxation and the singlewindow heuristic. The results on both real and realistic generatedinstances show that our heuristic achieves a significantreduction of memory peaks in a reasonable time compared toprevious works, making the new policy attractive for futurespace missions.