Szeregowanie zadań
|
Pobieranie 31,6 Kb.
|
- Charakterystyka zadań - parametry
- Charakterystyka zbioru zadań
- Charakterystyka zasobów - parametry
- Charakterystyka zbioru zasobów
- Klasyfikacja | |
- Problem przepływowy - flow shop
- Problem ogólny (gniazdowy) - job shop
- Algorytm dla problemu J2 | o j 2 | C max
|
Badania Operacyjne, wykład 6. 2007-12-15 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 Przykłady zasobów- maszyny różnego typu - siła robocza - energia - paliwo
- nakłady finansowe - surowce - systemy produkcyjne MaszynyMaszyny 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. ZadaniaZadanie 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ń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
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)
- przywłaszczalne (jeżeli możliwe jest odebranie konkretnej jednostki takiego zasobu operacji aktualnie wykonywanej i przydzielenie jej gdzie indziej) - nieprzywłaszczalne
- 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 - parametryKaż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ówCał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
- 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). 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). System otwarty W systemie otwartym wytworzenie każdego wyrobu wymaga operacji na wszystkich maszynach, ale kolejność ich wykonywania jest dowolna i nieustalona. UszeregowanieRozwią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 Jj Sj – termin rozpoczęcia wykonywania zadania Cj – termin zakończenia wykonywania zadania Lj – nieterminowość zakończenia zadania Ej – przyspieszenie rozpoczęcia zadania Fj – 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óźnienie cmax – maksymalny koszt wykonania zadania wjCj – suma ważonych czasów zakończenia wykonania zadań wjTj – suma ważonych opóźnień cj – całkowity koszt wykonania zadań Klasyfikacja || - opisuje zbiór maszyn M i tym samym określa typ zagadnienia - opisuje zbiór zadań oraz dodatkowe specyficzne ograniczenia zagadnienia - określa kryterium optymalizacji (czyli funkcję celu)
Symbol jest złożeniem dwóch symboli 12. 1 - charakteryzuje rodzaj maszyn 2 - 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 pusty) – zbiór M zawiera 1 maszynę Symbol może zawierać dowolny podzbiór symboli: setup – występują przezbrojenia batch - porcjowanie no wait - bez czekania pmtn – 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ń Symbol Symbol przyjmuje wartość jednej z symbolicznych postaci funkcji celu (kryterium). Przykład: F3|rj|Cmax Problem przepływowy - flow shopTw. Johnsona (1954r.) Jeżeli w problemie F2||Cmax (dwumaszynowy problem przepływowy z kryterium minimalizacji czasu wykonania wszystkich zadań): min { p1i, p2j } min { p2i, p1j } to w uszeregowaniu optymalnym zadanie Ji jest wcześniej niż zadanie Jj Algorytm JohnsonaKrok 1 : Zbuduj dwa zbiory: N1 i N2. N1 = {Jj: p1j < p2j } N2 = {Jj: p1j p2j } (zbiór N1 zawiera zadania, których czas pierwszej operacji jest mniejszy niż drugiej, zbiór N2 - pozostałe) Krok 2 : Uporządkuj zbiory: N1 - wg niemalejącej kolejności p1j N2 - wg nierosnącej kolejności p2j Krok 3 : Utwórz uszeregowanie optymalne łącząc uporządkowane zbiory N1 i N2 (najpierw wszystkie zadania z N1, potem zadania z N2) Problem ogólny (gniazdowy) - job shopProblem J2 | oj 2 | Cmax - w problemie występują 2 maszyny - każde zadanie składa się z jednej lub dwóch operacji - kolejność wykonywania operacji danego zadania na poszczególnych maszynach jest określona - minimalizowany jest czas wykonywania wszystkich zadań Algorytm dla problemu J2 | oj 2 | CmaxKrok 1: Podziel zadania na podzbiory: I1 (jedna operacja wykonywana na maszynie M1) I1,2 (pierwsza operacja na M1, druga na M2) I2 (jedna operacja wykonywana na maszynie M2) I2,1 (pierwsza operacja na M2, druga na M1) Krok 2: Uporządkuj zadania w zbiorach I1,2 i I2,1 algorytmem Johnsona (w I1 i I2 kolejność dowolna) Krok 3: Przydziel zadania do maszyny M1 w kolejności: (I1,2, I1, I2,1) , a do M2 : (I2,1 , I2, I1,2) |