Algorithms for parallel machine scheduling: a case study of the tracking and data relay satellite system

Algorithms for parallel machine scheduling: a case study of the tracking and data relay satellite system

0.00 Avg rating0 Votes
Article ID: iaor20041557
Country: United Kingdom
Volume: 54
Issue: 8
Start Page Number: 806
End Page Number: 821
Publication Date: Aug 2003
Journal: Journal of the Operational Research Society
Authors: , ,
Keywords: space, programming: integer
Abstract:

This paper presents two algorithms for scheduling a set of jobs with multiple priorities on non-homogeneous, parallel machines. The application of interest involves the tracking and data relay satellite system run by the US National Aeronautics and Space Administration. This system acts as a relay platform for Earth-orbiting vehicles that wish to communicate periodically with ground stations. The problem is introduced and then compared to other more common scheduling and routing problems. Next, a mixed-integer linear programming formulation is given but was found to be too difficult to solve for instances of realistic size. This led to the development of a dynamic programming-like heuristic and a greedy randomized adaptive search procedure. Each is described in some detail and then compared using data from a typical busy day scenario.

Reviews

Required fields are marked *. Your email address will not be published.