Algorithms for parallel machine scheduling: a case study of the tracking and data relay satellite system |
| |
Authors: | S Rojanasoonthon J F Bard S D Reddy |
| |
Institution: | 1.Graduate Program in Operations Research, University of Texas,Austin,USA;2.Computer Sciences Corporation, New Carrollton,USA |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|