w7, ARS

Nie obrażaj więc mojej inteligencji poprzez czynione na pokaz zaniżanie własnej.

Algorytmy decyzyjne i teoria złożoności wykład 7.

Szeregowanie zadańProblemy szeregowania zadańSformułowanie problemu: Dany jest zbiór zadań oraz zbiór zasobów służących do wykonania tych zadań. Należy wykonać wszystkie zadania z podanego zbioru w taki sposób, aby ekstremalizowane było określone kryterium jakości. Przykłady zadań- procesy montażu / obróbki detali w przemyśle maszynowym- czynności inwestycyjne w budownictwie- obsługa zgłoszenia- przejazd odcinkiem drogi- obliczenia komputerowe Przykłady zasobów- maszyny różnego typu- siła robocza- energia- paliwo- nakłady finansowe- surowce- systemy produkcyjne- kanały obsługi Maszyny Maszyny to szczególny rodzaj zasobów: - stanowią typ zasobów niezbędny dla wszystkich zadań - każde zadanie może być wykonywane w danej chwili przez co najwyżej jedną maszynęOgraniczeń tych nie muszą spełniać pozostałe zasoby. Zadania Zadanie składa się z mniejszych jednostek, tzw. operacji (w szczególności zadanie może składać się z jednej operacji).Zadanie Jj = {O1j, O2j, ..., Okj}Zbiór zadań J = {J1, J2, ..., Jn} Charakterystyka zadań - parametryoj – liczba operacji w zadaniupij – czas wykonywania operacji Oij (i–tej operacji zadania Jj ) rj – moment gotowości do wykonaniadj – pożądany czas zakończenia zadania (due date) _
dj – termin krytyczny zakończenia zadania (deadline)skj – czas przezbrojenia pomiędzy zadaniem Jk a Jjwj - waga (priorytet) Charakterystyka zadań Zadania ze względu na możliwość przerywania dzieli się na: - zadania niepodzielne (nieprzerywalne), czyli takie, których wykonywanie nie może być przerywane - zadana podzielne (przerywalne), jeżeli przerywanie wykonywania zadania jest dopuszczalne Charakterystyka zbioru zadań Cały zbiór zadań J scharakteryzowany jest poprzez liczbę tych zadań n. W zbiorze zadań mogą być określone ograniczenia kolejnościowe – rozróżniane są pod tym kątem dwa rodzaje zbiorów zadań: - zadania niezależne, pomiędzy którymi nie występują relacje częściowego porządku - zadania zależne, gdy występuje przynajmniej jedna taka relacja Charakterystyka zasobówZasoby klasyfikowane są pod wieloma względami. Przede wszystkim dzieli się je na: - dyskretne, czyli podzielne w sposób nieciągły (np. maszyny w systemie produkcyjnym, siła robocza) - podzielne w sposób ciągły (np. paliwo, energia) Można też wyróżnić zasoby: - przywłaszczalne (jeżeli możliwe jest odebranie konkretnej jednostki takiego zasobu operacji aktualnie wykonywanej i przydzielenie jej gdzie indziej) - nieprzywłaszczalne Wyróżnia się trzy podstawowe kategorie: - zasoby odnawialne (ograniczona jest liczba jednostek zasobu dostępnych w danej chwili), np. procesor, maszyna, robot, siła robocza - zasoby nieodnawialne (ograniczona jest globalna ilość całkowitego zużycia zasobu), np. surowce, nakłady finansowe, energia - zasoby podwójnie ograniczone (ograniczona jest dostępność w danej chwili i zużycie łączne), np. rozdział mocy z ograniczeniem zużycia całkowitego Charakterystyka zasobów - parametry Każdy zasób scharakteryzowany jest poprzez następujące parametry: - dostępność (czasowe przedziały dostępności) - ilość - koszt - dopuszczalne obciążenie jednostki zasobu (najczęściej przyjmuje się, że liczba operacji/zadań, które mogą być jednocześnie wykonywane przy użyciu tej jednostki jest równa jedności) Charakterystyka zbioru zasobów Cały zbiór zasobów jest określony poprzez podanie: - rodzajów elementów (jednostek zasobu) - ogólnej liczby jednostek zasobu każdego rodzaju Charakterystyka maszynZe względu na spełniane funkcje maszyny dzieli się na: - równoległe (uniwersalne) – spełniające te same funkcje - dedykowane (wyspecjalizowane) – różniące się spełnianymi funkcjami Istnieją trzy rodzaje maszyn równoległych: - identyczne – każda z maszyn pracuje z taką samą prędkością - jednorodne – maszyny różnią się prędkością, ale ich prędkość jest stała i nie zależy od wykonywanego zadania - dowolne (niezależne) – czas wykonywania poszczególnych zadań na maszynach jest różny W przypadku maszyn dedykowanych rozróżniane są następujące systemy obsługi zadań: - przepływowy (flow-shop) - ogólny / gniazdowy (job-shop) - otwarty (open-shop)

System przepływowy W systemie przepływowym każde zadanie musi przejść przez wszystkie maszyny w ściśle określonym porządku (każde zadanie składa się zatem z m operacji).

Przykład:

p1 = (2,2,4), p2 = (3,1,1), p3 = (2,3,2)

System gniazdowy W systemie gniazdowym (ogólnym) kolejność maszyn mających wykonać operacje jest różna, ale ściśle określona dla każdego zadania (zadania mogą mieć różną ilość operacji).

Przykład:

v1 = (2,1), v2 = (1,3,2), v3 = (1,2,3)

p1 = (3,1), p2 = (1,3,3), p3 = (4,2,2)

System otwarty W systemie otwartym wytworzenie każdego wyrobu wymaga operacji na wszystkich maszynach, ale kolejność ich wykonywania jest dowolna i nieustalona. Uszeregowanie Rozwiązaniem problemu szeregowania zadań jest uszeregowanie, czyli ustalona kolejność wykonywania operacji na poszczególnych maszynach. Natomiast zbudowanie harmonogramu to wyznaczenie momentów, w których rozpoczyna się realizacja tych operacji. W problemach, w których rozpatrywane są zasoby dodatkowe, należy również określić ich przydział. W danym uszeregowaniu dla każdego zadania Jj można określić: vij – sposób wykonania i-tej operacji zadania Jj (przydział do maszyn)sij – termin rozpoczęcia wykonywania i-tej operacji zadania JjSj – termin rozpoczęcia wykonywania zadania Cj – termin zakończenia wykonywania zadaniaLj – nieterminowość zakończenia zadaniaEj – przyspieszenie rozpoczęcia zadaniaFj – czas przepływu zadania przez system Wj – czas przestoju zadania przy przepływie przez
system Najczęściej spotykane kryteria: Cmax – czas zakończenia wykonania wszyst kich zadań (długość uszeregowania) Lmax – maksymalna nieterminowośćTmax – maksymalne opóźnieniecmax – maksymalny koszt wykonania zadaniaSwjCj – suma ważonych czasów zakończenia wykonania zadańSwjTj – suma ważonych opóźnieńScj – całkowity koszt wykonania zadań Klasyfikacja a|b|ga - opisuje zbiór maszyn M i tym samym określa typ zagadnieniab - opisuje zbiór zadań oraz dodatkowe specyficzne ograniczenia zagadnieniag - określa kryterium optymalizacji (czyli funkcję celu) Symbol a Symbol a jest złożeniem dwóch symboli a1a2. a1 - charakteryzuje rodzaj maszyna2 - określa liczbę maszyn w zbiorze M(Jeśli liczba ta nie jest określona z góry to używa się również symbolu pustego (Ø) mającego sens dowolnej liczby maszyn w systemie) Symbol a1P – identyczne maszyny równoległeQ – jednorodne maszyny równoległeR – niezależne maszyny równoległe F – system przepływowy (flow shop) FP – system przepływowy permutacyjnyO – system otwarty (open shop)J – system gniazdowy (job-shop) Ø (symbol pusty) – zbiór M zawiera 1 maszynę Symbol b b może zawierać dowolny podzbiór symboli:setup – występują przezbrojenia batch - porcjowanieno wait - bez czekaniapmtn – zadania można przerywaćprec - istnieje narzucony częściowy porządek technolo-giczny wykonywania zadań (tree, outree, intree)rj - zadania mają różne terminy zgłoszeń inne...(Znaczenie symboli jest dość często modyfikowane, wprowadzane są nowe)...