The buffer minimization problem for multiprocessor scheduling with conflicts

0175119 - MU-W 20025170 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Sgall, Jiří - Chrobák, M. - Csirik, J. - Imreh, C. - Noga, J. - Woeginger, G. J.
The buffer minimization problem for multiprocessor scheduling with conflicts.
Proceedings of the 28th International Colloquium on Automata, Languages, and Programming. Berlin: SpringerVerlag, 2001, s. 862-874.
[International Colloquium on Automata, Languages, and Programming/28./. Crete (GR), 08.07.2001-12.07.2001]
Grant CEP: GA AV ČR IAA1019901; GA ČR GA201/97/P038; GA MŠMT LN00A056
Klíčová slova: online algorithms%scheduling%conflict graph
Kód oboru RIV: BA - Obecná matematika

Our objective is to schedule task execution, obeying the conflict constraints, and minimizing the maximum buffer size of all processors. 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 $(Delta/2+1)$-competitive algorithm for trees, where $Delta$ is the diameter.
Trvalý link: http://hdl.handle.net/11104/0072108