The data exchange between ground stations and satellite constellations is becoming a challenging task, as more and more communication requests must be daily scheduled on a few, expensive stations located all around the Earth. Most of the scheduling procedures adopted in practice cannot cope with such complexity, and the development of optimization-based tools is strongly spurred. We show that the problem can be formulated as a multiprocessor task scheduling problem in which each job (communication) requires a time dependent pair of resources (ground station and satellite) to be processed, and the objective consists of maximizing the total revenue of on-time jobs. A time-indexed {0,1}-linear programming formulation is then introduced able to include all the complex technological constraints of current constellations. Unfortunately, relevant real-world scenarios yield integer programs with hundreds of thousands variables and a few million constraints, which cannot be tackled by standard integer programming (either exact or heuristic) techniques. To overcome this difficulty, we developed a Lagrangian version of the Fix-and-Relax MIP heuristic. It is based on a Lagrangian relaxation of the problem which is shown to be equivalent to a sequence of maximum weighted independent set problems on interval graphs. The heuristic has been implemented in a tool used by the Italian reference operator for the GALILEO constellation, providing near optimal solutions to relevant large scale test problems.

A Lagrangian Heuristic for Satellite Range Scheduling with Resource Constraints

ROSSI, FABRIZIO;SMRIGLIO, STEFANO
2011

Abstract

The data exchange between ground stations and satellite constellations is becoming a challenging task, as more and more communication requests must be daily scheduled on a few, expensive stations located all around the Earth. Most of the scheduling procedures adopted in practice cannot cope with such complexity, and the development of optimization-based tools is strongly spurred. We show that the problem can be formulated as a multiprocessor task scheduling problem in which each job (communication) requires a time dependent pair of resources (ground station and satellite) to be processed, and the objective consists of maximizing the total revenue of on-time jobs. A time-indexed {0,1}-linear programming formulation is then introduced able to include all the complex technological constraints of current constellations. Unfortunately, relevant real-world scenarios yield integer programs with hundreds of thousands variables and a few million constraints, which cannot be tackled by standard integer programming (either exact or heuristic) techniques. To overcome this difficulty, we developed a Lagrangian version of the Fix-and-Relax MIP heuristic. It is based on a Lagrangian relaxation of the problem which is shown to be equivalent to a sequence of maximum weighted independent set problems on interval graphs. The heuristic has been implemented in a tool used by the Italian reference operator for the GALILEO constellation, providing near optimal solutions to relevant large scale test problems.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11697/12758
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 141
  • ???jsp.display-item.citation.isi??? 98
social impact