Prelegent: dr Bartłomiej Przybylski (Zakład Algorytmiki i Metod Numerycznych)
Miejsce: Sala seminaryjna B1-7/8
Data i godzina: 26 listopada 2019 r., g. 12:30
Streszczenie: Problemy szeregowania zadań jednostkowych stanowią przedmiot zainteresowania badaczy nie tylko ze względu na szerokie zastosowania praktyczne, ale także ze względu na interesujące własności teoretyczne. Obszar ten, choć na pozór szeroko zbadany, kryje wciąż pytania, na które odpowiedzi nie znamy. Przez ostatnie lata zastanawiano się nad tym, czy istnieje wielomianowy algorytm pozwalający rozwiązać optymalizacyjny problem wielomaszynowego szeregowania zadań jednostkowych z ograniczeniami w postaci drzewa typu in-tree, ze średnim czasem zakończenia jako kryterium oceny uszeregowania. Intrygującą naturę tego pytania pogłębiał fakt, że od lat znamy wielomianowe algorytmy rozwiązujące niemal wszystkie problemy o podobnej charakterystyce. W czasie seminarium zaprezentujemy i skomentujemy opublikowany w lutym br. dowód NP-zupełności wspomnianego wyżej problemu.