Bounds for scheduling jobs on grid processors

Joan Boyar; Faith Ellen

doi:10.1007/978-3-642-40273-9_2

Bounds for scheduling jobs on grid processors

Joan Boyar, Faith Ellen

Department of Mathematics and Computer Science

University of Toronto

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

27 Downloads (Pure)

Abstract

In the Grid Scheduling problem, there is a set of jobs each with a positive integral memory requirement. Processors arrive in an online manner and each is assigned a maximal subset of the remaining jobs such that the sum of the memory requirements of those jobs does not exceed the processor’s memory capacity. The goal is to assign all the jobs to processors so as to minimize the sum of the memory capacities of the processors that are assigned at least one job. Previously, a lower bound of 5/4 on the competitive ratio of this problem was achieved using
jobs of size S and 2S − 1. For this case, we obtain matching upper and lower bounds, which vary depending on the ratio of the number of small jobs to the number of large jobs.

Original language	English
Title of host publication	Space-Efficient Data Structures, Streams, and Algorithms : Papers in Honor of J. Ian Munro, on the Occasion of His 66th Birthday
Editors	A. Brodnik, A. Lopez-Ortiz, V. Raman, A. Viola
Publisher	Springer
Publication date	2013
Pages	12-26
ISBN (Print)	978-3-642-40272-2
ISBN (Electronic)	978-3-642-40273-9
DOIs	https://doi.org/10.1007/978-3-642-40273-9_2
Publication status	Published - 2013
Event	Conference on Space Efficient Data Structures, Streams and Algorithms - University of Waterloo, Waterloo, Canada Duration: 15. Aug 2013 → 16. Aug 2013

Conference

Conference	Conference on Space Efficient Data Structures, Streams and Algorithms
Location	University of Waterloo
Country/Territory	Canada
City	Waterloo
Period	15/08/2013 → 16/08/2013

Series	Lecture Notes in Computer Science
Volume	8066
ISSN	0302-9743

Documents & Links

10.1007/978-3-642-40273-9_2

Bounds for scheduling jobs on grid processorsAccepted manuscript, 165 KBLicence: Unspecified

Conference on Space Efficient Data Structures, Streams and Algorithms
Boyar, J. (Participant)
15. Aug 2013 → 16. Aug 2013
Activity: Attending an event › Organisation or participation in workshops, courses or seminars

Cite this

@inproceedings{272a49a87d9d439e82ec07039851e227,

title = "Bounds for scheduling jobs on grid processors",

abstract = "In the Grid Scheduling problem, there is a set of jobs each with a positive integral memory requirement. Processors arrive in an online manner and each is assigned a maximal subset of the remaining jobs such that the sum of the memory requirements of those jobs does not exceed the processor{\textquoteright}s memory capacity. The goal is to assign all the jobs to processors so as to minimize the sum of the memory capacities of the processors that are assigned at least one job. Previously, a lower bound of 5/4 on the competitive ratio of this problem was achieved usingjobs of size S and 2S − 1. For this case, we obtain matching upper and lower bounds, which vary depending on the ratio of the number of small jobs to the number of large jobs.",

keywords = "online algorithms, scheduling, Grid scheduling",

author = "Joan Boyar and Faith Ellen",

year = "2013",

doi = "10.1007/978-3-642-40273-9_2",

language = "English",

isbn = "978-3-642-40272-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "12--26",

editor = "A. Brodnik and A. Lopez-Ortiz and V. Raman and A. Viola",

booktitle = "Space-Efficient Data Structures, Streams, and Algorithms",

address = "Germany",

note = "Conference on Space Efficient Data Structures, Streams and Algorithms ; Conference date: 15-08-2013 Through 16-08-2013",

}

Boyar, J & Ellen, F 2013, Bounds for scheduling jobs on grid processors. in A Brodnik, A Lopez-Ortiz, V Raman & A Viola (eds), Space-Efficient Data Structures, Streams, and Algorithms: Papers in Honor of J. Ian Munro, on the Occasion of His 66th Birthday. Springer, Lecture Notes in Computer Science, vol. 8066, pp. 12-26, Conference on Space Efficient Data Structures, Streams and Algorithms, Waterloo, Canada, 15/08/2013. https://doi.org/10.1007/978-3-642-40273-9_2

Bounds for scheduling jobs on grid processors. / Boyar, Joan; Ellen, Faith.
Space-Efficient Data Structures, Streams, and Algorithms: Papers in Honor of J. Ian Munro, on the Occasion of His 66th Birthday. ed. / A. Brodnik; A. Lopez-Ortiz; V. Raman; A. Viola. Springer, 2013. p. 12-26 (Lecture Notes in Computer Science, Vol. 8066).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Bounds for scheduling jobs on grid processors

AU - Boyar, Joan

AU - Ellen, Faith

PY - 2013

Y1 - 2013

N2 - In the Grid Scheduling problem, there is a set of jobs each with a positive integral memory requirement. Processors arrive in an online manner and each is assigned a maximal subset of the remaining jobs such that the sum of the memory requirements of those jobs does not exceed the processor’s memory capacity. The goal is to assign all the jobs to processors so as to minimize the sum of the memory capacities of the processors that are assigned at least one job. Previously, a lower bound of 5/4 on the competitive ratio of this problem was achieved usingjobs of size S and 2S − 1. For this case, we obtain matching upper and lower bounds, which vary depending on the ratio of the number of small jobs to the number of large jobs.

AB - In the Grid Scheduling problem, there is a set of jobs each with a positive integral memory requirement. Processors arrive in an online manner and each is assigned a maximal subset of the remaining jobs such that the sum of the memory requirements of those jobs does not exceed the processor’s memory capacity. The goal is to assign all the jobs to processors so as to minimize the sum of the memory capacities of the processors that are assigned at least one job. Previously, a lower bound of 5/4 on the competitive ratio of this problem was achieved usingjobs of size S and 2S − 1. For this case, we obtain matching upper and lower bounds, which vary depending on the ratio of the number of small jobs to the number of large jobs.

KW - online algorithms

KW - scheduling

KW - Grid scheduling

U2 - 10.1007/978-3-642-40273-9_2

DO - 10.1007/978-3-642-40273-9_2

M3 - Article in proceedings

SN - 978-3-642-40272-2

T3 - Lecture Notes in Computer Science

SP - 12

EP - 26

BT - Space-Efficient Data Structures, Streams, and Algorithms

A2 - Brodnik, A.

A2 - Lopez-Ortiz, A.

A2 - Raman, V.

A2 - Viola, A.

PB - Springer

T2 - Conference on Space Efficient Data Structures, Streams and Algorithms

Y2 - 15 August 2013 through 16 August 2013

ER -

Bounds for scheduling jobs on grid processors

Abstract

Conference

Documents & Links

Fingerprint

Related activities

Conference on Space Efficient Data Structures, Streams and Algorithms

Cite this