Competitive online scheduling of perfectly malleable jobs with setup times

Title:
Competitive online scheduling of perfectly malleable jobs with setup times
Authors:
Havill, Jessen T.; Mao, Weizhen
Citation:
Havill, J. T., & Mao, W. (2008). Competitive online scheduling of perfectly malleable jobs with setup times. European Journal of Operational Research, 187(3), 1126-1142.
Publisher:
European Journal of Operational Research
DATE ISSUED:
Jun-2008
PERMANENT LINK:
http://hdl.handle.net/2374.DEN/4997; http://hdl.handle.net/2374
Type:
Article
Language:
en_US
Description:
We study how to efficiently schedule online perfectly malleable parallel jobs with arbitrary arrival times on m 2 processors. We take into account both the linear speedup of such jobs and their setup time, i.e., the time to create, dispatch, and destroy multiple processes. Specifically, we define the execution time of a job with length pj running on kj processors to be pj/kj+(kj−1)c, where c > 0 is a constant setup time associated with each processor that is used to parallelize the computation. This formulation accurately models data parallelism in scientific computations and realistically asserts a relationship between job length and the maximum useful degree of parallelism. When the goal is to minimize makespan, we show that the online algorithm that simply assigns kj so that the execution time of each job is minimized and starts jobs as early as possible has competitive ratio 4(m − 1)/m for even m 2 and 4m/(m + 1) for odd m 3. This algorithm is much simpler than previous offline algorithms for scheduling malleable jobs that require more than a constant number of passes through the job list.
ISSN:
03772217
Appears in Collections:
Faculty Publications

Full metadata record

DC FieldValueLanguage
dc.contributor.authorHavill, Jessen T.en
dc.contributor.authorMao, Weizhenen
dc.date.accessioned2013-01-02T16:01:48Zen
dc.date.accessioned2013-12-18T21:04:46Z-
dc.date.available2013-01-02T16:01:48Zen
dc.date.available2013-12-18T21:04:46Z-
dc.date.created2008-06en
dc.date.issued2008-06en
dc.identifier.citationHavill, J. T., & Mao, W. (2008). Competitive online scheduling of perfectly malleable jobs with setup times. European Journal of Operational Research, 187(3), 1126-1142.en_US
dc.identifier.issn03772217en
dc.identifier.urihttp://hdl.handle.net/2374.DEN/4997en
dc.identifier.urihttp://hdl.handle.net/2374-
dc.descriptionWe study how to efficiently schedule online perfectly malleable parallel jobs with arbitrary arrival times on m 2 processors. We take into account both the linear speedup of such jobs and their setup time, i.e., the time to create, dispatch, and destroy multiple processes. Specifically, we define the execution time of a job with length pj running on kj processors to be pj/kj+(kj−1)c, where c > 0 is a constant setup time associated with each processor that is used to parallelize the computation. This formulation accurately models data parallelism in scientific computations and realistically asserts a relationship between job length and the maximum useful degree of parallelism. When the goal is to minimize makespan, we show that the online algorithm that simply assigns kj so that the execution time of each job is minimized and starts jobs as early as possible has competitive ratio 4(m − 1)/m for even m 2 and 4m/(m + 1) for odd m 3. This algorithm is much simpler than previous offline algorithms for scheduling malleable jobs that require more than a constant number of passes through the job list.en_US
dc.language.isoen_USen_US
dc.publisherEuropean Journal of Operational Researchen_US
dc.relation.ispartofFaculty Publicationsen_US
dc.titleCompetitive online scheduling of perfectly malleable jobs with setup timesen_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.