Title:
Generalized online malleable job scheduling on three processors
Authors:
Havill, Jessen; Kell, Nat
Publisher:
Denison University
DATE ISSUED:
19-Nov-2011
PERMANENT LINK:
http://hdl.handle.net/2374.DEN/3572; http://hdl.handle.net/2374
Type:
Article
Language:
en_US
Description:
In this paper, we study an online scheduling problem where we consider malleable jobs—jobs that can be scheduled to run on any number of processors on a parallel computer. Under the assumptions of our particular model, we show that when m, the number of processors, is three that the competitive ratio of the optimal online algorithm must be between ⅛(5+√73)≈ 1.693 and 2.123. We also give an algorithm for the model with constant overhead penalty that approaches an asymptotic competitive ratio of 4/3.
Appears in Collections:
Proceedings: 2011 Midstates Conference for Undergraduate Research in Computer Science and Mathematics

Full metadata record

DC FieldValue Language
dc.contributor.authorHavill, Jessenen
dc.contributor.authorKell, Naten
dc.coverage.spatialUSA - Ohio - Licking - Granvilleen_US
dc.date.accessioned2012-08-03T20:15:24Zen
dc.date.accessioned2013-12-18T22:12:49Zen
dc.date.available2012-08-03T20:15:24Zen
dc.date.available2013-12-18T22:12:49Zen
dc.date.created2011-11-19en
dc.date.issued2011-11-19en
dc.identifier.urihttp://hdl.handle.net/2374.DEN/3572en
dc.identifier.urihttp://hdl.handle.net/2374en
dc.descriptionIn this paper, we study an online scheduling problem where we consider malleable jobs—jobs that can be scheduled to run on any number of processors on a parallel computer. Under the assumptions of our particular model, we show that when <em>m</em>, the number of processors, is three that the competitive ratio of the optimal online algorithm must be between ⅛(5+√73)≈ 1.693 and 2.123. We also give an algorithm for the model with constant overhead penalty that approaches an asymptotic competitive ratio of 4/3.en_US
dc.language.isoen_USen_US
dc.publisherDenison Universityen_US
dc.relation.ispartofProceedings of the 2011 Midstates Conference on Undergraduate Research in Computer Science and Mathematicsen_US
dc.titleGeneralized online malleable job scheduling on three processorsen_US
dc.typeArticleen_US
dc.contributor.institutionDenison Universityen_US
dc.contributor.repositoryDenison DRCen_US
dc.publisher.digitalDenison Universityen_US
All Items in The Five Colleges of Ohio Digital Repository are protected by copyright, with all rights reserved, unless otherwise indicated.