Optimizing Routing and Backlogs for Job Flows in a Distributed Computing Environment
Citation:
David Montana, John Zinky, "Optimizing Routing and Backlogs for Job Flows in a Distributed Computing Environment"
Book Chapter in:
Metaheuristics for Scheduling in Distributed Computing Environments, pp 39-59, Springer Press, 2008.
Formats:
book
pdf
DOI 10.1007/978-3-540-69277-5_2
Abstract
We address the problem of optimizing the flow of compute jobs through a distributed system of compute servers. The goal is to determine the best policy for how to route jobs to different compute clusters as well as to decide which jobs to backlog until a future time. We use an approach that is a hybrid of dynamic programming and a genetic algorithm. Dynamic programming determines the routing and backlog decisions about individual flows of homogeneous jobs, while a genetic algorithm optimizes the order in which the different flows are fed to the dynamic programming algorithm. We demonstrate the effectiveness of this approach on sample problems, some designed to yield a known correct answer and others designed to test the scaling.
