Static-task scheduling incorporating precedence constraints and deadlines in a heterogeneous-computing environment / Michael D Niedert
Abstract
Distributed systems have grown in popularity due to the rapid increase in networking of personal computers. A mixture of computers consisting of different architectures can be more powerful, reliable, and scalable than a single supercomputer. The problem of optimally scheduling jobs on a cluster of heterogeneous machines to minimize the time at which the last machine finishes is NP-complete. Nonetheless, the choice of a heuristic algorithm greatly affects the speed of solution. This work evaluates a greedy algorithm, an A* algorithm, and a simulated annealing algorithm applied to the heterogeneous scheduling problem with deadline and dependency constraints. Tradeoffs of speed and schedule quality were noted between the algorithms. The greedy algorithm produced results quicker than the A* and simulated annealing algorithms, but with a lower schedule quality. Because of these offsetting performance criteria, an analysis was conducted to determine which algorithms should be used for which input cases.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Investigation of effect of different run-time distributions on SmartNet performance
Armstrong, Robert Kyle (Monterey, California. Naval Postgraduate School, 1997-09);This thesis investigates, using in-line simulation, the effect of non-deterministic runtime distributions on the performance of SmartNet's schedule execution using the Opportunistic Load Balancing (OLB) Algorithm, the ... -
Depth analysis of Midway Atoll using Quickbird multi-spectral imaging over variable substrates
Camacho, Mark A. (Monterey California. Naval Postgraduate School, 2006-09);Shallow water bathymetry is important for both safe navigation and natural resource management purposes. Extracting depth information from spectral imagery allows identification of benthic features and characterization of ... -
Solving dynamic battlespace movement problems using dynamic distributed computer networks
Bradford, Robert D., III (Monterey, California. Naval Postgraduate School, 2000-06-01);This thesis develops an architecture for dynamic distributed military operations research. This architecture assumes that a network of heterogeneous computing devices connects forces throughout the battlespace. Both the ...