Scheduling Data Transfers in Space Missions with Priorities and Interruptions

In deep space missions, scientific data generated by onboard instruments must be temporarily stored in local memory buffers before being downlinked to Earth during lim- ited communication windows. Efficient scheduling of these data transfers is essential to prevent buffer overflows and data loss, particularly in the presence of uncertainties. Previous work has considered the overlapping Memory Dumping Problem (oMDP), which consists in assigning transfer priorities to the memory buffers and minimize the peaks memory usage, which reduces the risk of overflow. In this paper, we consider additional decisions in the transfer plans that are implementable in practice: data transfer from each buffer can be interrupted after a given time, once per downlink window, preventing it from dumping data until the next window, but redistributing the unused bandwidth to the other buffers. The new problem is called oMDPi (oMDP with interruptions). We obtain new complexity results, showing that oMDPi is NP-complete for at least two windows. While the complexity status of the single window oMDPi remains open, we propose a polynomial-time heuristic to solve it. We propose a hybrid heuristic to solve the general oMDPi, embedding a flow relaxation and a single window heuristic. The results on both real and realistic generated instances show that our heuristic achieves a significant reduction of memory peaks in a reasonable time compared to previous works, making the new policy attractive for future space missions.