The buffer minimization problem for multiprocessor scheduling with conflicts

Marek Chrobak; János Csirik; Csanad Imreh; John Noga; Jirí Sgall; Gerhard J. Woeginger

doi:10.1007/3-540-48224-5_70

The buffer minimization problem for multiprocessor scheduling with conflicts

Marek Chrobak, János Csirik, Csanad Imreh, John Noga, Jirí Sgall, Gerhard J. Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

24 Citations (Scopus)

Abstract

We consider the problem of scheduling a sequence of tasks in a multi-processor system with conflicts. Conflicting processors cannot process tasks at the same time. At certain times new tasks arrive in the system, where each task specifies the amount of work (processing time) added to each processor’s workload. Each processor stores this workload in its input buffer. Our objective is to schedule task execution, obeying the conflict constraints, and minimizing the maximum buffer size of all processors. In the off-line case, we prove that, unless P = NP, the problem does not have a polynomial-time algorithm with a polynomial approximation ratio. In the on-line case, we provide the following results: (i) a competitive algorithm for general graphs, (ii) tight bounds on the competitive ratios for cliques and complete k-partite graphs, and (iii) a (Δ/2 + 1)-competitive algorithm for trees, where Δ is the diameter. We also provide some results for small graphs with up to 4 vertices.

Original language	English
Title of host publication	Automata, Languages and Programming
Subtitle of host publication	28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings
Editors	Fernando Orejas, Paul G. Spivakis, Jan van Leeuwen
Place of Publication	Berlin
Publisher	Springer
Pages	862-874
ISBN (Electronic)	978-3-540-48224-6
ISBN (Print)	978-3-540-42287-7
DOIs	https://doi.org/10.1007/3-540-48224-5_70
Publication status	Published - 2001
Event	28th International Colloquium on Automata, Languages, and Programming, ICALP 2001 - Crete, Greece Duration: 8 Jul 2001 → 12 Jul 2001 Conference number: 28

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2076
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	28th International Colloquium on Automata, Languages, and Programming, ICALP 2001
Abbreviated title	ICALP
Country/Territory	Greece
City	Crete
Period	8/07/01 → 12/07/01

Keywords

METIS-202687

Access to Document

10.1007/3-540-48224-5_70

Cite this

Chrobak, M., Csirik, J., Imreh, C., Noga, J., Sgall, J., & Woeginger, G. J. (2001). The buffer minimization problem for multiprocessor scheduling with conflicts. In F. Orejas, P. G. Spivakis, & J. van Leeuwen (Eds.), Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings (pp. 862-874). (Lecture Notes in Computer Science; Vol. 2076). Springer. https://doi.org/10.1007/3-540-48224-5_70

Chrobak, Marek ; Csirik, János ; Imreh, Csanad et al. / The buffer minimization problem for multiprocessor scheduling with conflicts. Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings. editor / Fernando Orejas ; Paul G. Spivakis ; Jan van Leeuwen. Berlin : Springer, 2001. pp. 862-874 (Lecture Notes in Computer Science).

@inproceedings{481d997b9c3047a9a3c6556d3f8eed7a,

title = "The buffer minimization problem for multiprocessor scheduling with conflicts",

abstract = "We consider the problem of scheduling a sequence of tasks in a multi-processor system with conflicts. Conflicting processors cannot process tasks at the same time. At certain times new tasks arrive in the system, where each task specifies the amount of work (processing time) added to each processor{\textquoteright}s workload. Each processor stores this workload in its input buffer. Our objective is to schedule task execution, obeying the conflict constraints, and minimizing the maximum buffer size of all processors. In the off-line case, we prove that, unless P = NP, the problem does not have a polynomial-time algorithm with a polynomial approximation ratio. In the on-line case, we provide the following results: (i) a competitive algorithm for general graphs, (ii) tight bounds on the competitive ratios for cliques and complete k-partite graphs, and (iii) a (Δ/2 + 1)-competitive algorithm for trees, where Δ is the diameter. We also provide some results for small graphs with up to 4 vertices.",

keywords = "METIS-202687",

author = "Marek Chrobak and J{\'a}nos Csirik and Csanad Imreh and John Noga and Jir{\'i} Sgall and Woeginger, {Gerhard J.}",

year = "2001",

doi = "10.1007/3-540-48224-5_70",

language = "English",

isbn = "978-3-540-42287-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "862--874",

editor = "Fernando Orejas and Spivakis, {Paul G.} and {van Leeuwen}, Jan",

booktitle = "Automata, Languages and Programming",

note = "28th International Colloquium on Automata, Languages, and Programming, ICALP 2001, ICALP ; Conference date: 08-07-2001 Through 12-07-2001",

}

Chrobak, M, Csirik, J, Imreh, C, Noga, J, Sgall, J & Woeginger, GJ 2001, The buffer minimization problem for multiprocessor scheduling with conflicts. in F Orejas, PG Spivakis & J van Leeuwen (eds), Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings. Lecture Notes in Computer Science, vol. 2076, Springer, Berlin, pp. 862-874, 28th International Colloquium on Automata, Languages, and Programming, ICALP 2001, Crete, Greece, 8/07/01. https://doi.org/10.1007/3-540-48224-5_70

The buffer minimization problem for multiprocessor scheduling with conflicts. / Chrobak, Marek; Csirik, János; Imreh, Csanad et al.

Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings. ed. / Fernando Orejas; Paul G. Spivakis; Jan van Leeuwen. Berlin : Springer, 2001. p. 862-874 (Lecture Notes in Computer Science; Vol. 2076).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - The buffer minimization problem for multiprocessor scheduling with conflicts

AU - Chrobak, Marek

AU - Csirik, János

AU - Imreh, Csanad

AU - Noga, John

AU - Sgall, Jirí

AU - Woeginger, Gerhard J.

N1 - Conference code: 28

PY - 2001

Y1 - 2001

N2 - We consider the problem of scheduling a sequence of tasks in a multi-processor system with conflicts. Conflicting processors cannot process tasks at the same time. At certain times new tasks arrive in the system, where each task specifies the amount of work (processing time) added to each processor’s workload. Each processor stores this workload in its input buffer. Our objective is to schedule task execution, obeying the conflict constraints, and minimizing the maximum buffer size of all processors. In the off-line case, we prove that, unless P = NP, the problem does not have a polynomial-time algorithm with a polynomial approximation ratio. In the on-line case, we provide the following results: (i) a competitive algorithm for general graphs, (ii) tight bounds on the competitive ratios for cliques and complete k-partite graphs, and (iii) a (Δ/2 + 1)-competitive algorithm for trees, where Δ is the diameter. We also provide some results for small graphs with up to 4 vertices.

AB - We consider the problem of scheduling a sequence of tasks in a multi-processor system with conflicts. Conflicting processors cannot process tasks at the same time. At certain times new tasks arrive in the system, where each task specifies the amount of work (processing time) added to each processor’s workload. Each processor stores this workload in its input buffer. Our objective is to schedule task execution, obeying the conflict constraints, and minimizing the maximum buffer size of all processors. In the off-line case, we prove that, unless P = NP, the problem does not have a polynomial-time algorithm with a polynomial approximation ratio. In the on-line case, we provide the following results: (i) a competitive algorithm for general graphs, (ii) tight bounds on the competitive ratios for cliques and complete k-partite graphs, and (iii) a (Δ/2 + 1)-competitive algorithm for trees, where Δ is the diameter. We also provide some results for small graphs with up to 4 vertices.

KW - METIS-202687

U2 - 10.1007/3-540-48224-5_70

DO - 10.1007/3-540-48224-5_70

M3 - Conference contribution

SN - 978-3-540-42287-7

T3 - Lecture Notes in Computer Science

SP - 862

EP - 874

BT - Automata, Languages and Programming

A2 - Orejas, Fernando

A2 - Spivakis, Paul G.

A2 - van Leeuwen, Jan

PB - Springer

CY - Berlin

T2 - 28th International Colloquium on Automata, Languages, and Programming, ICALP 2001

Y2 - 8 July 2001 through 12 July 2001

ER -

Chrobak M, Csirik J, Imreh C, Noga J, Sgall J, Woeginger GJ. The buffer minimization problem for multiprocessor scheduling with conflicts. In Orejas F, Spivakis PG, van Leeuwen J, editors, Automata, Languages and Programming: 28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings. Berlin: Springer. 2001. p. 862-874. (Lecture Notes in Computer Science). doi: 10.1007/3-540-48224-5_70

The buffer minimization problem for multiprocessor scheduling with conflicts

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this