Wykład #5
Sterowanie procesami dyskretnymi
Prowadzący:
Prowadzący:
Prowadzący:
Prowadzący:
Dr Paweł Lajmert
Dr Paweł Lajmert
Pokój: 105A
Pokój: 105A
Dyżur: Wtorek 1015
Dyżur: Wtorek 1015
Wykład #5 - 1
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Problemy szeregowania zadań
Problemy szeregowania zadań
Deterministyczne szeregowanie zadań zajmuje się
szeregowaniem
szeregowaniem (układaniem harmonogramów)
zadań
zadań (programów, czynności, prac) na maszynach
(procesorach, obrabiarkach, stanowiskach obsługi).
Szukamy harmonogramu wykonania dla danego
Szukamy harmonogramu wykonania dla danego
zbioru zadań w określonych warunkach, tak by
zminimalizować przyjęte kryterium oceny (koszt)
uszeregowania, np. czas produkcji.
Model deterministyczny:
Model deterministyczny: parametry systemu i
zadań są od początku znane.
Wykład #5 - 2
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Geneza i motywacje praktyczne:
Geneza i motywacje praktyczne:
harmonogramowanie produkcji
przemysłowej,
planowanie projektów,
organizacja pracy,
plany zajęć szkolnych, spotkań i
plany zajęć szkolnych, spotkań i
konferencji,
przetwarzanie procesów w
wielozadaniowych systemach
operacyjnych,
organizacja obliczeń rozproszonych.
Wykład #5 - 3
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Przykład.
Przykład. Pięć zadań o czasach wykonania p1,...,p5=6,9,4,1,4 należy
uszeregować na trzech maszynach tak, by zakończyły się one możliwie jak
najszybciej.
Reprezentacja graficzna harmonogramu - diagram Gantta.
diagram Gantta
Zasada poprawności harmonogramu:
Zasada poprawności harmonogramu:
żadne zadanie nie może być jednocześnie wykonywane przez różne
maszyny,
żaden procesor nie pracuje równocześnie nad różnymi zadaniami.
Wykład #5 - 4
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Wykres Ganta
Wykres Ganta
Opracowany przez siebie wykres H. L. Gantt po raz pierwszy
H. L. Gantt
zastosował do przedstawienia planu produkcji w roku 1917. Na
typowym wykresie Gantta wiersze zawierają stanowiska
pracy, natomiast kolumny oznaczają jednostki czasu.
Układ zdarzeń na wykresie przedstawiany jest najczęściej w
wersji planowanej przed rozpoczęciem działania oraz
planowanej
rzeczywistej
rzeczywistej nanoszonej na wykres wraz z upływem czasu. Za
pomocą wykresu Gantta można nie tylko planować i
kontrolować wykonanie planu, ale także poprzez zastosowanie
odpowiedniego systemu oznaczeń uwzględniać zmienność
przebiegu wykonania zadania.
Wykład #5 - 5
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Wykres Ganta
Wykres Ganta
Wykres Gantta
Wykres Gantta jest graficznym sposobem planowania i
kontroli. Planowanie i koordynowanie przebiegu różnych
czynności w przekroju czasowym odgrywa istotną rolę w
tworzeniu i funkcjonowaniu organizacji. Wykresy Gantta służą
Wykresy Gantta
do planowania działań wielopodmiotowych zarówno
zespołowych, jak i grupowych. Przedstawiają następstwo
zespołowych, jak i grupowych. Przedstawiają następstwo
kolejnych zdarzeń, uwzględniając również zadania
wykonywane równo-
legle. Dzięki tej tech-
nice można także
kontrolować realiza-
cję zaplanowanego
przedsięwzięcia.
Wykład #5 - 6
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Wykład #5 - 7
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Technika ta obejmuje następujące etapy:
Technika ta obejmuje następujące etapy:
I etap: rozłożenie przedsięwzięcia na cele etapowe
lub cele cząstkowe,
II etap: ustalenie czasu trwania przedsięwzięcia i
określenie czasów realizacji celów etapowych i
cząstkowych,
cząstkowych,
III etap: ustalenie kolejności realizacji celów
etapowych i cząstkowych oraz wyznaczenie terminów
ich rozpoczęcia i zakończenia,
IV etap: określenie miejsca, w którym cele te mają
być zrealizowane,
V etap: wyrażenie w postaci graficznej wszystkich
dokonanych czynności.
Wykład #5 - 8
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Zastosowanie
Zastosowanie
Wykresy Gantta
Wykresy Gantta znajdują zastosowanie uniwersalne we wszystkich
dziedzinach działalności ludzi. Jak każda metoda również i ta posiada
metoda
swoje wady i zalety. Główną zaletą wykresów Gantta jest możliwość
bieżącej kontroli realizowanego przedsięwzięcia i dokonywania
odpowiednich korekt. Do wad należy zaliczyć m.in.:
brak szczegółowych informacji dotyczących poszczególnych
brak szczegółowych informacji dotyczących poszczególnych
zadań,
pokazuje jedynie kolejność zadań,
nie pokazuje najkrótszej drogi do ukończenia prac,
nie obrazuje najlepszego wykorzystania zasobów.
Wykres Gantta
Wykres Gantta umożliwia kierownikowi podjęcie zobowiązań
opartych na planowanych terminach zakończenia, pozyskanie
dodatkowych zasobów dla skrócenia niektórych terminów.
Wykład #5 - 9
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Rodzaje powiązań między zadaniami
Rodzaje powiązań między zadaniami
W wykresie Gantta możliwe są różne zależności
wykresie Gantta
pomiędzy zadaniami:
FS (finish to start) - po zakończeniu czynności A
FS (finish to start)
rozpoczyna się czynność B,
SS (start to start) - zadanie B może się zacząć, gdy
SS (start to start) - zadanie B może się zacząć, gdy
SS (start to start)
SS (start to start)
zacznie się zadanie A,
FF (finish to finish) - zadanie B może się skończyć
FF (finish to finish)
dopiero po zakończeniu zadania A,
SF (start to finish) - zadanie A nie może się zakończyć
SF (start to finish)
przed rozpoczęciem zadania B (na zakładkę).
Wykład #5 - 10
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Sposoby obsługi zadań
Sposoby obsługi zadań
Procesory/maszyny równoległe (każda maszyna może obsłużyć
każde zadanie):
" maszyny identyczne  wszystkie są jednakowo szybkie,
maszyny identyczne
" maszyny jednorodne  mają różne szybkości, ale stosunki czasów
maszyny jednorodne
wykonania zadań są niezależne od maszyn,
" maszyny dowolne  prędkości zależą od wykonywanych zadań.
maszyny dowolne
Uszeregowanie na maszynach równoległych.
Wykład #5 - 11
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Procesory/Maszyny dedykowane
Procesory/Maszyny dedykowane
zadania są podzielone na operacje (zadanie Zj
zadania operacje
zawiera operacje Oij do wykonania na maszynach Mi,
o długościach czasowych pij). Zadanie kończy się
wraz z wykonaniem swej najpóz
niejszej operacji,
dopuszcza się sytuację, gdy zadanie nie wykorzystuje
dopuszcza się sytuację, gdy zadanie nie wykorzystuje
wszystkich maszyn (operacje puste),
żadne dwie operacje tego samego zadania nie mogą
wykonywać się równocześnie,
żaden procesor nie może równocześnie pracować nad
różnymi operacjami.
Wykład #5 - 12
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Trzy główne typy systemów obsługi dla maszyn
Trzy główne typy systemów obsługi dla maszyn
dedykowanych:
dedykowanych:
system przepływowy (flow shop)  operacje
system przepływowy
każdego zadania są wykonywane przez procesory w
tej samej kolejności wyznaczonej przez numery
maszyn,
maszyn,
system otwarty (open shop)  kolejność wykonania
system otwarty
operacji w obrębie zadań jest dowolna,
system gniazdowy (job shop)  dla każdego zadania
system gniazdowy
mamy dane przyporządkowanie maszyn operacjom
oraz wymaganą kolejność.
Wykład #5 - 13
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Przykład.
Przykład.
Taśma produkcyjna.(Roboty[M]-Detale[Z])
M1 M2 M3
M1 M2 M3
Z1
3 2 1
3 2 1
Z2
3 2 2
3 2 2
Z3
1 1 2
1 1 2
1 1 2
1 1 2
Taśma produkcyjna  system przepływowy.
system przepływowy.
Wykład #5 - 14
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
M1 M2 M3
M1 M2 M3
Przykład. C.d.
Przykład. C.d.
Z1
3 2 1
3 2 1
Taśma produkcyjna.(Roboty[M]-
Z2
3 2 2
3 2 2
Detale[Z])
Z3
1 1 2
1 1 2
Procesory dedykowane - system przepływowy (kolejność
Procesory dedykowane - system przepływowy (kolejność
operacji musi być zgodna z numeracją maszyn).
operacji musi być zgodna z numeracją maszyn).
Wykład #5 - 14
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Przykład.
Przykład.
Jednodniowy plan zajęć szkolnych. (Nauczyciele[M]-Klasy[Z])
M1 M2 M3
M1 M2 M3
Z1 3 2 1
Z1
Z2 3 2 2
Z2
Z3 1 1 2
Z3 1 1 2
Z3
Z3
Procesory dedykowane - system
Procesory dedykowane - system
otwarty (kolejność operacji
otwarty (kolejność operacji
dowolna).
dowolna).
Wykład #5 - 15
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Parametry zadań:
Parametry zadań:
Dane są: zbiór n zadań Z={Z1,...,Zn} oraz m maszyn (procesorów)
M={M1,...,Mm}.
Zadanie Zj :
Zadanie Zj :
Czas wykonywania. Dla maszyn identycznych jest on niezależny od
Czas wykonywania maszyn identycznych
maszyny i wynosi pj. Maszyny jednorodne Mi charakteryzują się
Maszyny jednorodne
współczynnikami szybkości bi, wtedy czas dla Mi to pj/bi. Dla maszyn
współczynnikami szybkości bi, wtedy czas dla Mi to pj/bi. Dla maszyn
dowolnych mamy czasy pij zależne od zadań i procesorów.
Moment przybycia (release time) rj . Czas, od którego zadanie może
Moment przybycia
zostać podjęte. Wartość domyślna - zero.
Termin zakończenia dj . Opcjonalny parametr. Występuje w dwóch
Termin zakończenia dj .
wariantach. Może oznaczać czas, od którego nalicza się spóz
nienie
(due date), lub termin, którego przekroczyć nie wolno (deadline).
Waga wj  opcjonalny parametr, określający ważność zadania przy
Waga wj
naliczaniu kosztu harmonogramu. Domyślnie zadania są jednakowej
wagi i wtedy wj=1.
Wykład #5 - 16
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Zadania zależne:
Zadania zależne:
W zbiorze zadań Z można wprowadzić ograniczenia
ograniczenia
kolejnościowe
kolejnościowe w postaci dowolnej relacji częściowego porządku.
Wówczas Ziwykonywać dopiero po zakończeniu Zi (dlaczego? np. Zj korzysta
z wyników pracy Zi).
Jeśli ograniczenia te nie występują, mówimy o zadaniach
Jeśli ograniczenia te nie występują, mówimy o zadaniach
zadaniach
zadaniach
niezależnych
niezależnych (tak się przyjmuje domyślnie) w przeciwnym razie
są one zależne.
zależne
Relację zwykle podaje się w postaci acyklicznego digrafu o
acyklicznego digrafu
wierzchołkach z Z (droga z Zi do Zj oznacza, że Ziprzechodnimi, lub bez (tylko relacje nakrywania  diagram
Hassego).
Wykład #5 - 17
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Zadania mogą być:
Zadania mogą być:
niepodzielne  przerwy w wykonaniu są niedopuszczalne
niepodzielne
(domyślnie)
podzielne  wykonanie można przerwać i podjąć ponownie, w
podzielne
przypadku maszyn równoległych nawet na innym procesorze.
Uszeregowanie zadań podzielnych na maszynach równoległych.
Uszeregowanie zadań podzielnych na maszynach równoległych.
Wykład #5 - 18
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Zasady poprawności harmonogramu:
Zasady poprawności harmonogramu:
w każdej chwili procesor może wykonywać co najwyżej jedno
zadanie,
w każdej chwili zadanie może być obsługiwane przez co najwyżej
jeden procesor,
zadanie Zj wykonuje się w całości w przedziale czasu (rj,INF),
zadanie Zj wykonuje się w całości w przedziale czasu (rj,INF),
w całości
w całości
spełnione są ograniczenia kolejnościowe,
w przypadku zadań niepodzielnych każde zadanie wykonuje się
nieprzerwanie w pewnym domknięto otwartym przedziale
czasowym, dla zadań podzielnych czasy wykonania tworzą
skończoną sumę rozłącznych przedziałów.
Wykład #5 - 19
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Kryteria kosztu harmonogramu
Kryteria kosztu harmonogramu
Położenie zadania Zi w gotowym harmonogramie:
Położenie Zi
moment zakończenia Ci (ang. completion time),
moment zakończenia Ci
czas przepływu przez system (flow time) Fi=Ci ri,
czas przepływu Fi=Ci ri,
opóz
nienie (lateness) Li = Ci di,
opóz
nienie Li = Ci di,
spóz
nienie (tardiness) Ti = max{Ci di,0},
spóz
nienie Ti = max{Ci di,0},
i i i
i i i
 znacznik spóz
nienia Ui = w(Ci>di), a więc odpowiedz
(0/1
 znacznik spóz
nienia U = w(Ci>di), (0/1
 znacznik spóz
nienia U = w(C >d ), a (0/1
 znacznik spóz
nienia Ui = w(C >d ), więc odpowiedz
(0/1
czyli Nie/Tak)
czyli Nie/Tak) na pytanie  czy zadanie się spóz
niło?
Najczęściej stosowane:
Najczęściej stosowane:
długość uszeregowania Cmax=max{Cj : j=1,...,n},
długość uszeregowania Cmax=max{Cj : j=1,...,n},
całkowity (łączny) czas zakończenia zadania SCj = Si=1,...,n Ci,
całkowity (łączny) czas zakończenia zadania SCj = Si=1,...,n Ci,
Wykład #5 - 20
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Oparte na wymaganych terminach zakończenia:
Oparte na wymaganych terminach zakończenia:
maksymalne opóz
nienie Lmax=max{Lj : j=1,...,n},
maksymalne opóz
nienie Lmax=max{Lj : j=1,...,n},
maksymalne spóz
nienie Tmax=max{Tj : j=1,...,n},
maksymalne spóz
nienie Tmax=max{Tj : j=1,...,n},
całkowite spóz
nienie STj = Si=1,...,n Ti,
całkowite spóz
nienie STj = Si=1,...,n Ti,
liczba spóz
nionych zadań SUj = Si=1,...,n Ui,
liczba spóz
nionych zadań SUj = Si=1,...,n Ui,
można wprowadzać wagi zadań, np. łączne ważone spóz
nienie
można wprowadzać wagi zadań łączne ważone spóz
nienie
wagi zadań, np. łączne ważone spóz
nienie
wagi zadań łączne ważone spóz
nienie
SwjTj = Si=1,...,n * wiTi.
SwjTj = Si=1,...,n * wiTi.
Niektóre kryteria są sobie równoważne:
Niektóre kryteria są sobie równoważne:
SLi = SCi  Sdi, F= (SCi)/n  (Sri)/n.
Wykład #5 - 21
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Minimalizacja długości harmonogramu. Maszyny równoległe.
Minimalizacja długości harmonogramu. Maszyny równoległe.
Procesory identyczne, zadania niezależne.
Zadania podzielne
Zadania podzielne P|pmtn|Cmax.
Algorytm McNaughtona
Algorytm McNaughtona Złożoność O(n)
1. Wylicz optymalną długość Cmax*=max{Sj=1,...,n pj/m, max j=1,...,n pj},
2. Szereguj kolejno zadania na maszynie, po osiągnięciu Cmax* przerwij
zadanie i (jeśli się nie zakończyło) kontynuuj je na następnym
procesorze począwszy od chwili 0.
Przykład. m=3, n=5, p1,...,p5=4,5,2,1,2.
Si=1,...,5 pi=14, max pi=5,
Si=1,...,5 pi=14, max pi=5,
Cmax*=max{14/3,5} = 4.
Cmax*=max{14/3,5} = 4.
Wykład #5 - 22
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Algorytm Liu O(n2), EDD(Earliest Due Date),
Algorytm Liu O(n2), oparty na regule EDD(Earliest Due Date) działający
nawet przy:
1. Spośród dostępnych zadań przydziel maszynę temu, które ma
najmniejszy wymagany termin zakończenia,
2. Jeśli zadanie zostało zakończone, lub przybyło nowe  wróć do 1 (w
drugim przypadku przerywamy zadanie).
drugim przypadku przerywamy zadanie).
Reguła EDD (Earliest Due Date)
Reguła EDD stosowana jest do szeregowania zadań na jednej maszynie
o czasach przybycia ustalonych na 0.
Reguła EDD porządkuje sekwencje zadań według niemalejących
wymaganych terminów zakończenia dj.
Wykład #5 - 23
POLITECHNIKA A
ÓDZKA
Instytut Obrabiarek i Technologii Budowy Maszyn
Wykład #5 - 24