Static-task scheduling incorporating precedence constraints and deadlines in a heterogeneous-computing environment / Michael D Niedert
Loading...
Authors
Niedert, Michael D.
Subjects
Advisors
Rowe, Neil
Date of Issue
2000-06
Date
June, 2000
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
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.
Type
Thesis
Description
Series/Report No
Department
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
xii, 83 p.;28 cm.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.