Graph balancing: A special case of scheduling unrelated parallel machines

0318586 - MÚ 2009 RIV US eng C - Conference Paper (international conference)
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]
R&D Projects: GA ČR GA201/05/0124; GA AV ČR IAA1019401
Institutional research plan: CEZ:AV0Z10190503
Keywords : graph * graph balancing * scheduling
Subject RIV: BA - General Mathematics

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čů.
Permanent Link: http://hdl.handle.net/11104/0167959