The buffer minimization problem for multiprocessor scheduling with conflicts

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

26 Citations (Scopus)
12 Downloads (Pure)


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 languageEnglish
Title of host publicationAutomata, Languages and Programming
Subtitle of host publication28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings
EditorsFernando Orejas, Paul G. Spivakis, Jan van Leeuwen
Place of PublicationBerlin
ISBN (Electronic)978-3-540-48224-6
ISBN (Print)978-3-540-42287-7
Publication statusPublished - 2001
Event28th International Colloquium on Automata, Languages, and Programming, ICALP 2001 - Crete, Greece
Duration: 8 Jul 200112 Jul 2001
Conference number: 28

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference28th International Colloquium on Automata, Languages, and Programming, ICALP 2001
Abbreviated titleICALP


  • METIS-202687


Dive into the research topics of 'The buffer minimization problem for multiprocessor scheduling with conflicts'. Together they form a unique fingerprint.

Cite this