In deep space missions, scientific data generated by onboard instruments must be temporarily stored in local memory buffers before being downlinked to Earth during limited 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 a dditional 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.

International audience

Constraint Programming has been widely, and very successfully, applied to scheduling problems. However, the focus has been on uninterruptible tasks, and preemptive scheduling problems are typically harder for existing constraint solvers. Indeed, one usually needs to represent all potential task interruptions thus introducing many variables and symmetrical or dominated choices. In this paper, building on mostly known results, we observe that a large class of preemptive disjunctive scheduling problems do not require an explicit model of task interruptions. We then introduce a new constraint programming approach for this class of problems that significantly outperforms state-of-the-art dedicated approaches in our experimental results.

International audience

Long range space missions, such as Rosetta, require robust plans of data-acquisition activities and of the resulting data transfers. In this paper we revisit the problem of assigning priorities to data transfers in order to maximize safety margin of onboard memory. We propose a fast sweep algorithm to verify the feasibility of a given priority assignment and we introduce an efficient exact algorithm to assign priorities on a single downlink window. We prove that the problem is NP-hard for several windows, and we propose several randomized heuristics to tackle the general case. Our experimental results show that the proposed approaches are able to improve the plans computed for the real mission by the previously existing method, while the sweep algorithm yields drastic accelerations.

International audience

International audience

Some scheduling problems present the peculiarity to be solvable in polynomial time and to have a huge number of optimal solutions. In the disturbed environment of a production manufacturing system, where the forecasted schedule is going to change because of unexpected events or uncertainties, it can be interesting not only to know one or several optimal sequences, but the characteristics of `good' sequences. In this paper, we focus on the characterization of all the ρ-approximated sequences, which are solutions of a scheduling problem with a performance not worse than a given distance from the value of the optimal solution. With the support of the lattice of permutations, we define the characteristics of the optimal sequences for some particular scheduling problems. We present a method which is able, for some specific scheduling problems, to give the characteristics of all the ρ-approximated sequences. A computational experience is carried out to evaluate the performance of the proposed method.

This paper addresses the solving of mixed Task Scheduling and Resource Allocation Problems in an integrated way using a backtracking algorithm. Several ordering heuristics are proposed to improve the efficiency of this algorithm. Experiments show the impact of these heuristics on the quality of the first solution obtained. We also compare our integrated approach with a sequential solving of scheduling and allocation problems.