Szeregowanie zadań



Pobieranie 31,6 Kb.
Data23.01.2018
Rozmiar31,6 Kb.

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

- 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ń - parametry


oj – liczba operacji w zadaniu

pij – czas wykonywania operacji Oij (itej operacji zadania Jj )

rj – moment gotowości do wykonania

dj – pożądany czas zakończenia zadania (due date)

_
dj – termin krytyczny zakończenia zadania (deadline)

skj – czas przezbrojenia pomiędzy zadaniem Jk a Jj

wj - 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ów


Zasoby 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 maszyn


Ze 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).


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.



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 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

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 1

Pidentyczne maszyny równoległe

Q – jednorodne maszyny równoległe

R – niezależne maszyny równoległe

F – system przepływowy (flow shop)

FP – system przepływowy permutacyjny

O – system otwarty (open shop)

J – system gniazdowy (job-shop)

Ø (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 shop


Tw. 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 Johnsona


Krok 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 shop


Problem 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 | Cmax


Krok 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)



©operacji.org 2017
wyślij wiadomość

    Strona główna