Citation
Constraint-Based Random Search for Solving Spacecraft Downlink Scheduling Problems. In Selected papers from the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), pages 133-160, Springer, 2005.
Selected
Abstract
This paper introduces a combinatorial optimisation problem called the Mars Express Memory Dumping Problem (Mex-Mdp), which arises in the European Space Agency programme Mars Express. The domain is characterized by complex constraints concerning bounded on-board memory capacities, limited communication windows over the downlink channels, deadlines and ready times imposed by the scientists using the spacecraft instruments. This paper lays out the problem and analyses its computational complexity showing that Mex-Mdp is NP-hard. Then the problem is modelled as a Constraint Satisfaction Problem and two different heuristic strategies for its solution are presented: a core greedy constraint-based procedure and an iterative sampling strategy based on random search. The algorithms are evaluated both against a benchmark set created on the basis of ESA documentation and a lower bound of the minimised objective function. Experimental results show the overall effectiveness of the approach.
There is no pdf available for this paper. You might like to try to obtain the original source (see the doi, for example)
doi
The doi for this publication is 10.1007/0-387-27744-7_7 You can link directly to the original paper, via the doi, from here
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INBOOK{2005-133-160-SI, chapter = {Selected papers from the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA)},
pages = {133--160},
title = {Constraint-Based Random Search for Solving Spacecraft Downlink Scheduling Problems},
publisher = {Springer},
year = {2005},
editor = {G. Kendall and E. Burke and S. Petrovic and M. Gendreau},
author = {A. Oddi and N. Policella and A. Cesta and G. Cortellessa},
note = {Selected},
abstract = {This paper introduces a combinatorial optimisation problem called the Mars Express Memory Dumping Problem (Mex-Mdp), which arises in the European Space Agency programme Mars Express. The domain is characterized by complex constraints concerning bounded on-board memory capacities, limited communication windows over the downlink channels, deadlines and ready times imposed by the scientists using the spacecraft instruments. This paper lays out the problem and analyses its computational complexity showing that Mex-Mdp is NP-hard. Then the problem is modelled as a Constraint Satisfaction Problem and two different heuristic strategies for its solution are presented: a core greedy constraint-based procedure and an iterative sampling strategy based on random search. The algorithms are evaluated both against a benchmark set created on the basis of ESA documentation and a lower bound of the minimised objective function. Experimental results show the overall effectiveness of the approach.},
doi = {10.1007/0-387-27744-7_7},
owner = {gxk},
timestamp = {2012.05.29} }