A Lagrangian heuristic for satellite range scheduling with resource constraints

Publication year: 2011
Source: Computers & Operations Research, Volume 38, Issue 11, November 2011, Pages 1572-1583

Fabrizio, Marinelli , Salvatore, Nocella , Fabrizio, Rossi , Stefano, Smriglio

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….