Constraint-Based Random Search for Solving Spacecraft Downlink Scheduling Problems

Angelo Oddi (), Nicola Policella (), Amedeo Cesta () and Gabriella Cortellessa ()
Additional contact information
Angelo Oddi: ISTC-CNR Italian National Research Council
Nicola Policella: ISTC-CNR Italian National Research Council
Amedeo Cesta: ISTC-CNR Italian National Research Council
Gabriella Cortellessa: ISTC-CNR Italian National Research Council

A chapter in Multidisciplinary Scheduling: Theory and Applications, 2005, pp 133-160 from Springer

Abstract: 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.

Keywords: constraint reasoning; random sampling; greedy heuristic search (search for similar items in EconPapers)
Date: 2005
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-0-387-27744-8_7

Ordering information: This item can be ordered from
http://www.springer.com/9780387277448

DOI: 10.1007/0-387-27744-7_7

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().