Prelegent: Dr Bartłomiej Przybylski (Pracownia Algorytmiki)
Data i godzina: 23 czerwca 2020 r., g. 12:30
Streszczenie: W pierwszej części seminarium zaprezentuję efekty początkowych prac nad biblioteką do numerycznego wspomagania rozwiązywania problemów szeregowania zadań — Scheduling.jl. W drugiej części seminarium skupię się na wynikach dotyczących jedno- i wielomaszynowych problemów szeregowania zadań, w których zmienne czasy wykonywania zadań zależą nie tylko od pozycji zadania w uszeregowaniu, ale także – w dowolny sposób – od samego zadania i maszyny, do której zadanie zostało przydzielone. Dla takiej mieszanej zależności oraz wybranych funkcji celu (maksymalny czas zakończenia i łączny czas zakończenia) przedstawię pełną klasyfikację złożoności obliczeniowej. Przypomnę także wyniki dotyczące analogicznych problemów, w których zadania muszą być wykonywane w określonej kolejności (ograniczenia w postaci łańcucha), a także rozpocznę dyskusję na temat analizy problemów, w których ograniczenia kolejnościowe są opisane bardziej złożonymi grafami.