Seminarium: Systemy Rozproszone
29. marca 2007, godzina 12:15, sala 3120
Marcin Kulka <mk209212@students.mimuw.edu.pl>


Minimalizacja czasu wykonania wielu wzajemnie powiązanych ze sobą zadań w systemie rozproszonym


Dane jest wiele zadań, które trzeba wykonać. Zadania są ze sobą powiązane, to znaczy możliwość rozpoczęcia danego zadania zależy od pomyślnego ukończenia innych zadań. Zależności między zadaniami możemy zamodelować za pomocą acyklicznego grafu skierowanego. Ponadto mamy do dyspozycji pewną liczbę maszyn. Dla każdego zadania i każdej maszyny określone jest prawdopodobieństwo, pomyślnego ukończenia tego zadania na tej maszynie. Wiemy, że istnieje przynajmniej jedna maszyna, dla której prawdopodobieństwo ukończenia danego zadania jest niezerowe. Dla uproszczenia przyjmujemy, że czas wykonania dowolnego zadania wszędzie jest taki sam.

Naszym zadaniem jest znalezienie takiego sposobu przydzielenia zadań do maszyn, żeby zminimalizować oczekiwany czas wykonania wszystkich zadań. Okazuje się, że dla stałej liczby maszyn i stałej szerokości grafu zależności między zadaniami jest to wykonalne. W pozostałych przypadkach problem jest NP-zupełny. Pozostaje więc szukania algorytmów aproksymacyjnych.

Plan referatu:

Serdecznie zapraszam!
Marcin Kulka