A competitive online algorithm for a parallel job scheduling problem

Title:
A competitive online algorithm for a parallel job scheduling problem
Authors:
Havill, Jessen T.
Citation:
J. T. Havill. A competitive online algorithm for a parallel job scheduling problem. In Proceedings of the 12th IASTED International Conference on Parallel and Distributed Computing and Systems, pages 611–616, 2000.
Publisher:
Proceedings of the 12th IASTED International Conference on Parallel and Distributed Computing and Systems
DATE ISSUED:
2000
PERMANENT LINK:
http://hdl.handle.net/2374.DEN/5000; http://hdl.handle.net/2374
Type:
Article; Book chapter
Language:
en_US
Description:
We study a parallel job scheduling problem in which parallel jobs may be assigned to any number of processors in a parallel computing system. If a job of size p j is assigned to k j processors, its running time is assumed to be pj/kj+kjc, where c is a constant representing communication overhead for each processor. This model explicitly takes into account the increase in overhead arising from the use of more processors and the fact that a small job may be easily overwhelmed by overhead, and actually see its running time increase, if it is assigned to too many processors. Mao, Chen, and Watson (1999) introduced this parallel job scheduling problem and showed that the competitive ratio of a particular deterministic online scheduling algorithm is 2 when the machine has two processors. We show that, for an arbitrary number of processors, the competitive ratio of their algorithm (slightly modified) is asymptotically 4.
ISBN:
9780889863040; 0889863040
Appears in Collections:
Faculty Publications

Full metadata record

DC FieldValue Language
dc.contributor.authorHavill, Jessen T.en
dc.date.accessioned2013-01-02T16:11:53Zen
dc.date.accessioned2013-12-18T21:04:51Z-
dc.date.available2013-01-02T16:11:53Zen
dc.date.available2013-12-18T21:04:51Z-
dc.date.created2000en
dc.date.issued2000en
dc.identifier.citationJ. T. Havill. A competitive online algorithm for a parallel job scheduling problem. In Proceedings of the 12th IASTED International Conference on Parallel and Distributed Computing and Systems, pages 611–616, 2000.en_US
dc.identifier.isbn9780889863040en
dc.identifier.isbn0889863040en
dc.identifier.urihttp://hdl.handle.net/2374.DEN/5000en
dc.identifier.urihttp://hdl.handle.net/2374-
dc.descriptionWe study a parallel job scheduling problem in which parallel jobs may be assigned to any number of processors in a parallel computing system. If a job of size p j is assigned to k j processors, its running time is assumed to be pj/kj+kjc, where c is a constant representing communication overhead for each processor. This model explicitly takes into account the increase in overhead arising from the use of more processors and the fact that a small job may be easily overwhelmed by overhead, and actually see its running time increase, if it is assigned to too many processors. Mao, Chen, and Watson (1999) introduced this parallel job scheduling problem and showed that the competitive ratio of a particular deterministic online scheduling algorithm is 2 when the machine has two processors. We show that, for an arbitrary number of processors, the competitive ratio of their algorithm (slightly modified) is asymptotically 4.en_US
dc.language.isoen_USen_US
dc.publisherProceedings of the 12th IASTED International Conference on Parallel and Distributed Computing and Systemsen_US
dc.relation.ispartofFaculty Publicationsen_US
dc.titleA competitive online algorithm for a parallel job scheduling problemen_US
dc.typeArticleen_US
dc.typeBook chapteren_US
dc.contributor.institutionDenison Universityen_US
dc.date.digitized2013-01-02en
dc.contributor.repositoryDenison Resource Commonsen_US
All Items in The Five Colleges of Ohio Digital Repository are protected by copyright, with all rights reserved, unless otherwise indicated.