Prelegent: Dr Krzysztof Turowski (Uniwersytet Jagielloński w Krakowie)
Data i godzina: 13 grudnia 2022 r., g. 10:30
Streszczenie: Problem szeregowania zadań z grafem ograniczeń, wprowadzony przez Hansa Bodlaendera, Klausa Jansena i Gerharda Woegingera w 1994 roku, polega na przydziale zadań do maszyn z dodatkowym warunkiem, aby zadania sąsiadujące w grafie ograniczeń nie zostały przydzielone do wykonania na tej samej maszynie. W referacie zostaną przedstawione problemy oraz rezultaty otrzymane dla szczególnego przypadku, gdy graf ograniczeń jest grafem pełnym k-dzielnym dla różnego rodzaju maszyn (identycznych, jednorodnych, dowolnych), typów zadań (jednostkowe, dowolnej długości), kryteriów (maksymalny i średni czas zakończenia zadania), a także w różnym ujęciu liczby partycji w grafie (jako część instancji vs. parametr problemu). Zaprezentowane zostaną dowody i różnorodne techniki użyte do ich wyprowadzenia (m.in. programowanie dynamiczne, programowanie liniowe), a także szereg problemów otwartych, które nadal oczekują na rozwiązanie.