Online malleable job scheduling for m ⩽ 3

Title:
Online malleable job scheduling for m ⩽ 3
Authors:
Havill, Jessen T.
Citation:
Havill, Jessen T. (2010). Online malleable job scheduling for m ⩽ 3. Information Processing Letters, 111(1), 31-35.
Publisher:
Information Processing Letters
DATE ISSUED:
2010-12
Type:
Article
PERMANENT LINK:
http://hdl.handle.net/2374.DEN/4996; http://hdl.handle.net/2374

Full metadata record

DC FieldValueLanguage
dc.contributor.authorHavill, Jessen T.en
dc.date.accessioned2013-01-02T15:58:52Zen
dc.date.accessioned2013-12-18T21:04:44Z-
dc.date.available2013-01-02T15:58:52Zen
dc.date.available2013-12-18T21:04:44Z-
dc.date.created2010-12en
dc.date.issued2010-12en
dc.identifier.citationHavill, Jessen T. (2010). Online malleable job scheduling for m ⩽ 3. Information Processing Letters, 111(1), 31-35.en_US
dc.identifier.issn00200190en
dc.identifier.urihttp://hdl.handle.net/2374.DEN/4996en
dc.identifier.urihttp://hdl.handle.net/2374-
dc.descriptionA malleable parallel job is one that may be assigned to any number of processors in a parallel computing environment. In our particular problem, we assume that the execution time of a job j with processing requirement p j is p j/k j + (k j − 1)c if the job is assigned to k j ∈ {1, 2, . . . ,m} processors, where c is a constant representing overhead and m is the number of processors. Given a sequence of jobs, an online algorithm must assign to each job, as it arrives, both a number of processors and a start time to minimize the makespan of the schedule. We provide online algorithms for m = 2 and m =3 with asymptotically optimal competitive ratios of 3/2 and 5/3, respectively. We also provide a similar online algorithm for the more general problem with job dependent overhead term c j that has optimal competitive ratio φ = (1 +√5)/2 when m = 2.en_US
dc.language.isoen_USen_US
dc.publisherInformation Processing Lettersen_US
dc.relation.ispartofFaculty Publicationsen_US
dc.titleOnline malleable job scheduling for m ⩽ 3en_US
dc.typeArticleen_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.