Title:

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

Title in english:

Optimization algorithms for the scheduling problem with time couplings

Creator:

Idzikowski, Radosław

Contributor:

Bożejko, Wojciech. Promotor

Subject and Keywords:

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.

Publisher:

Politechnika Wrocławska

Place of publication:

Wrocław

Date:

2021

Resource Type:

rozprawa doktorska

Source:

<sygn. PWr 398224> ; click here to follow the link

Language:

pol

Relation:

Politechnika Wrocławska. Wydział Elektroniki

Rights:

Wszystkie prawa zastrzeżone (Copyright)

Access Rights:

Dla wszystkich w zakresie dozwolonego użytku

Rights Owner:

Własność autora

Location:

Politechnika Wrocławska