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: | Bard J.F., Rojanasoonthon S., Reddy S.D. |
Keywords: | space, programming: integer |
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.