Tytuł:

Algorytmy optymalizacyjne dla problemu szeregowania zadań ze sprzężeniami czasowymi

Tytuł odmienny:

Optimization algorithms for the scheduling problem with time couplings

Autor:

Idzikowski, Radosław

Współtwórca:

Bożejko, Wojciech. Promotor

Temat i słowa kluczowe:

optymalizacja ; szeregowanie zadań ; sprzężenia czasowe ; algorytmy

Abstrakt:

Rozprawa dotyczy problemów szeregowania zadań ze sprzężeniami czasowymi. Pod pojęciem sprzężeń czasowych rozumiane są dodatkowe relacje między operacjami. W szczególności dotyczy to operacji przyporządkowanych do różnych zadań, ale wykonywanych na tej samej maszynie – np. ograniczony czas przestoju maszyny pomięzy kolejno wykonywanymi operacjami. W pracy na przykładzie problemu przepływowego szeregowania zadań zaproponowano uogólniony model uwzględniania sprężeń czasowych. Za pomocą tego modelu można przedstawić ograniczenia znane już w literaturze, między innymi takie jak ograniczenie „bez przestojów” lub „z ograniczonym przestojem”, a także nowe z „minimalnym” oraz „maksymalnym” przestojem maszyny. Dla różnych wariantów problemów przepływowych, w tym z przezbrojeniami, zaproponowano modele matematyczne oraz grafowe. Następnie wykazano szereg własności, w tym eliminacyjnych, dla omawianych problemów, oraz zaproponowano różne algorytmy optymalizacyjne wykorzystujące udowodnione własności. Praca została podzielona na trzy części. Część pierwsza zawiera wprowadzenie do teorii szeregowania zadań wraz z obszernym przeglądem literatury. Część druga jest poświecona problemom przepływowym szeregowania zadań ze sprzężeniami czasowymi. Dla omawianych problemów zaproponowano szereg dedykowanych algorytmów poczynając od metod liczenia funkcji celu, poprzez algorytmy wykrywajace bloki, a kończąc na algorytmach optymalizacyjnych dla rozpatrywanych problemów. Omówiono i zaimplementowano algorytmy klasyczne, oraz uwzględniające najnowsze trendy w problematyce szeregowania zadań i innych problemach optymalizacji dyskretnej. W rozprawie wykorzystano następujące algorytmy oraz metody: Metoda Podziału i Ograniczeń, Programowanie Dynamiczne, Całkowitoliczbowe Programowanie Liniowe, Przeszukiwanie Snopowe, Przeszukiwanie z Zabronieniami, Sztuczna Kolonia Pszczół, Algorytm Genetyczny oraz algorytmy dedykowane, w tym konstrukcyjne. Poza analizą teoretyczną przeprowadzono również badania eksperymentalne dla badanych problemów z wykorzystaniem wymienionych powyżej algorytmów. Ostatnia część dysertacji została poświecona praktycznym zastosowaniom zaproponowanych metod szeregowania zadań. Przedstawiono praktyczny problem szeregowania przezbrojeń na przykładzie produkcji urządzeń AGD. Następnie skupiono się na innych problemach optymalizacji dyskretnej, w tym na problemie marszrutyzacji pojazdów. Uzyskane rezultaty teoretyczne zostały wykorzystane w konstrukcji dedykowanych metod i aplikacji wspomagających zarządzanie flotą pojazdów w przedsiębiorstwach operujących w różnych branżach.

Wydawca:

Politechnika Wrocławska

Miejsce wydania:

Wrocław

Data wydania:

2021

Typ zasobu:

rozprawa doktorska

Źródło:

<sygn. PWr 398224> ; kliknij tutaj, żeby przejść

Język:

pol

Powiązania:

Politechnika Wrocławska. Wydział Elektroniki

Prawa:

Wszystkie prawa zastrzeżone (Copyright)

Prawa dostępu:

Dla wszystkich w zakresie dozwolonego użytku

Właściciel praw:

Własność autora

Lokalizacja oryginału:

Politechnika Wrocławska