Graph balancing: A special case of scheduling unrelated parallel machines

0318586 - MÚ 2009 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
Ebenlendr, Tomáš - Krčál, Marek - Sgall, Jiří
Graph balancing: A special case of scheduling unrelated parallel machines.
[Vyvažování grafů: Speciální případ rozvrhování nezávislých paralelních počítačů.]
Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. San Francisco: ACM-SIAM, 2008, s. 483-490. ISBN 978-0-89871-647-4.
[Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)/10./. San Francisco (US), 20.01.2008-22.01.2008]
Grant CEP: GA ČR GA201/05/0124; GA AV ČR IAA1019401
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: graph * graph balancing * scheduling
Kód oboru RIV: BA - Obecná matematika

We design a 1.75-approximation algorithm for a special case of scheduling parallel machines to minimize the makespan, namely the case where each job can be assigned to at most two machines, which the same processing time on either machine. We also show that even for this special case it is $NP$-hard to compute better than 1.5 approximation.

Článek navrhuje a analyzuje algoritmy a dolní odhady pro vyvažování grafů. Jde o speciální případ rozvrhování nezávislých paralelních počítačů.
Trvalý link: http://hdl.handle.net/11104/0167959