Optimization Online


A Lagrangian Heuristic for Satellite Range Scheduling with Resource Constraints

Fabrizio Marinelli (marinelli***at***di.univaq.it)
Salvatore Nocella (nocella***at***di.univaq.it)
Fabrizio Rossi (rossi***at***di.univaq.it)
Stefano Smriglio (smriglio***at***di.univaq.it)

Abstract: The task of scheduling communications between satellites and ground control stations is getting more and more critical since an increasing number of satellites must be controlled by a small set of stations. In such a congested scenario, the current practice, in which experts build hand-made schedules, often leaves a large number of communication requests unserved. We report on our experience in the design of an optimization-based support tool at the European Space Agency (ESA). We propose a tight time-indexed formulation of the problem able to include several complex technological constraints. A non-standard Lagrangian heuristic is then devised which provides near-optimal solutions of a set of large-scale test problems arising in the forthcoming GALILEO constellation. The heuristic shows also numerical stability and robustness adequate for practical implementation and the resulting tool is currently under testing at ESA.

Keywords: Satellite Constellation, Multiprocessor Task Scheduling, Time-indexed Formulation , Lagrangian Relaxation, Conflict Graph, Set Packing

Category 1: Applications -- OR and Management Sciences

Category 2: Integer Programming (0-1 Programming )

Citation: Computers and Operations Research, (2011), doi:10.1016/j.cor.2011.01.016


Entry Submitted: 04/20/2006
Entry Accepted: 04/20/2006
Entry Last Modified: 02/08/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society