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

Institut for Matematik og Datalogi

University of Toronto

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › peer review

32 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.

Originalsprog	Engelsk
Titel	Space-Efficient Data Structures, Streams, and Algorithms : Papers in Honor of J. Ian Munro, on the Occasion of His 66th Birthday
Redaktører	A. Brodnik, A. Lopez-Ortiz, V. Raman, A. Viola
Forlag	Springer
Publikationsdato	2013
Sider	12-26
ISBN (Trykt)	978-3-642-40272-2
ISBN (Elektronisk)	978-3-642-40273-9
DOI	https://doi.org/10.1007/978-3-642-40273-9_2
Status	Udgivet - 2013
Begivenhed	Conference on Space Efficient Data Structures, Streams and Algorithms - University of Waterloo, Waterloo, Canada Varighed: 15. aug. 2013 → 16. aug. 2013

Konference

Konference	Conference on Space Efficient Data Structures, Streams and Algorithms
Lokation	University of Waterloo
Land/Område	Canada
By	Waterloo
Periode	15/08/2013 → 16/08/2013

Navn	Lecture Notes in Computer Science
Vol/bind	8066
ISSN	0302-9743

Emneord

online algorithms
scheduling
Grid scheduling

Dokumenter og links

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

Bounds for scheduling jobs on grid processorsAccepteret manuskript, 165 KBLicens: Ikke-specificeret

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

1 Organisering af eller deltagelse i workshop, kursus, seminar eller lignende

Conference on Space Efficient Data Structures, Streams and Algorithms
Boyar, J. (Deltager)
15. aug. 2013 → 16. aug. 2013
Aktivitet: Deltagelse i faglig begivenhed › Organisering af eller deltagelse i workshop, kursus, seminar eller lignende

Citationsformater

@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. i A Brodnik, A Lopez-Ortiz, V Raman & A Viola (red), 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, bind 8066, s. 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. red. / A. Brodnik; A. Lopez-Ortiz; V. Raman; A. Viola. Springer, 2013. s. 12-26 (Lecture Notes in Computer Science, Bind 8066).

Publikation: Kapitel i bog/rapport/konference-proceeding › Konferencebidrag i proceedings › Forskning › 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

Konference

Emneord

Dokumenter og links

SDU link

Fingeraftryk

Relaterede aktiviteter

Conference on Space Efficient Data Structures, Streams and Algorithms

Citationsformater