Show simple item record

dc.contributor.advisorRowe, Neil
dc.contributor.authorNiedert, Michael D.
dc.dateJune, 2000
dc.date.accessioned2012-08-09T19:28:30Z
dc.date.available2012-08-09T19:28:30Z
dc.date.issued2000-06
dc.identifier.urihttp://hdl.handle.net/10945/9303
dc.identifier.urihttp://handle.dtic.mil/100.2/ADA380969
dc.description.abstractDistributed 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.en_US
dc.format.extentxii, 83 p.;28 cm.en_US
dc.language.isoen_US
dc.publisherMonterey, California. Naval Postgraduate Schoolen_US
dc.rightsApproved for public release, distribution unlimited.en_US
dc.titleStatic-task scheduling incorporating precedence constraints and deadlines in a heterogeneous-computing environment / Michael D. Niedert.en_US
dc.typeThesisen_US
dc.contributor.corporateNaval Postgraduate School (U.S.)
dc.description.serviceU.S. Navy (U.S.N.) author.en_US
etd.thesisdegree.nameM.S. in Computer Scienceen_US
etd.thesisdegree.levelMastersen_US
etd.thesisdegree.disciplineComputer Scienceen_US
etd.thesisdegree.grantorNaval Postgraduate Schoolen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record