DZIEKAN i RADA WYDZIAŁU INFORMATYKI, ELEKTRONIKI I TELEKOMUNIKACJI AKADEMII GÓRNICZO-HUTNICZEJ im. ST. STASZICA W KRAKOWIE |
---|
zapraszają na publiczą dyskusję nad rozprawą doktorską mgr. inż. Wiesława Popielarskiego |
ALGORYTMY STADNE W OPTYMALIZACJI PROBLEMU PRZEPLYWOWEGO SZEREGOWANIA ZADAŃ |
Dyskusja odbędzie się 05 maja 2014 roku o godz. 10:00 w sali 1.20 ul. Kawiory 21, pawilon D-17 |
PROMOTOR: Prof. zw. dr hab. inż. Bogusław Filipowicz, Akademia Górniczo-Hutnicza w Krakowie |
RECENZENCI: Prof. zw. dr hab. inż. Zdzisław Hippe, Wyższa Szkoła Zarządzania i Informatyki w Rzeszowie |
Dr hab. inż. Grzegorz Dobrowolski, Akademia Górniczo-Hutnicza w Krakowie |
Z rozprawą doktorską i opiniami recenzentów można się zapoznać w Czytelni Biblioteki Głównej AGH, al. Mickiewicza 30 |
mgr inż. Wiesław Popielarski
Promotor: prof. dr hab. inż. Bogusław Filipowicz (AGH) Dyscyplina: Informatyka
Rola zagadnień szeregowania zadań we współczesnym świecie jest nie do przecenienia. Praktycznie w każdej dziedzinie życia można pośrednio lub bezpośrednio spotkać się z problemem, który sprowadza się do optymalizacji szeregowania zadań.
W pracy zostały poruszone zagadnienia szeregowania zadań dla modeli wieloprocesorowych rozwiązane za pomocą algorytmów stochastycznych inspirowanych przez naturę (pszczeli oraz kukułki).
Rozwiązanie zaimplementowano w języku Scala, natomiast przetwarzanie równoległe zrealizowano za pomocą modelu aktorów.
– Teza rozprawy:– Jako tezę niniejszej rozprawy doktorskiej autor przedstawia następujące twierdzenie:
Zagadnienie szeregowania zadań dla modelu przepływowego (flow shop) wielomaszynowego, będącego problemem należącym do klasy NP-zupełnej, jest podatne na efektywne zrównoleglenie, jeżeli zastosuje się do jego rozwiązania algorytm stochastyczny, w szczególnosci stadny oraz że istnieje sposób badania efektywnosci takiego algorytmu.
Przedstawione poniżej rozwiązanie problemu przepływowego szeregowania zadań za pomocą zrównoleglonych algorytmów stadnych zawiera w sobie potencjał adaptacji do znajdowania wartości bliskich optymalnej nie tylko dla problemu Fm|prmu|Cmax, ale również każdego innego problemu szeregowania zadań. W przyszłości mogą się one stać konkurencyjnymi dla obecnie znanych heurystyk.
Niewątpliwym osiągnięciem jest przedstawiona analiza liczby iteracji i spodziewanej dokładności znalezionych wartości optymalnych za pomocą nierówności Chernoffa oraz sprzężonych łańcuchów Markowa.
Dodatkowo zaletą pracy jest opracowanie definicji sąsiedztwa w przestrzeni kombinatorycznej dla algorytmów pszczelego oraz kukułki.