Zastosowania?
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
1
aktualizacja: H. Gaspars-Wieloch
Szeregowanie zadań:
•
Dany jest zbiór zadań Z i zbiór maszyn (pracowników, stanowisk…) M, z których kaŜda moŜe wykonać kaŜde zadanie ze zbioru Z
•
W danym momencie kaŜde z zadań moŜe być
wykonywane na co najwyŜej jednej maszynie, a kaŜda maszyna moŜe wykonywać co najwyŜej jedno zadanie
•
Zbiór zadań moŜe być niezaleŜny (jeŜeli wszystkie zadania z tego zbioru mogą być wykonywane jednocześnie) albo zaleŜny (jeŜeli określono chociaŜ jedną zaleŜność
kolejnościową)
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
2
aktualizacja: H. Gaspars-Wieloch
1
•
Zbiór zadań moŜe być podzielny (gdy wykonywanie
kaŜdego z zadań moŜe zostać przerwane w dowolnym
momencie, a następnie wznowione, być moŜe na innej maszynie) albo niepodzielny
•
KaŜde zadanie z ∈ Z jest charakteryzowane poprzez: j
o
Moment gotowości (ang. release date) rj o
Wektor czasów wykonywania [τ ]
ij
o
Wagę (priorytet) w ≥1
j
o
śądany termin zakończenia (ang. due date) 0≤ d ≤∞
j
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
3
aktualizacja: H. Gaspars-Wieloch
Szeregowanie zadań:
•
Zbiór M nazywamy zbiorem maszyn identycznych, gdy m
∀ ∈ M z
∀ ∈ Z :τ =τ
i
j
ij
j
•
Zbiór M nazywamy jednorodnym, gdy
τ j
m
∀ ∈ M z
∀ ∈ Z :τ =
i
j
ij
bi
( b oznacza współczynnik prędkości maszyny m ) i
i
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
4
aktualizacja: H. Gaspars-Wieloch
2
•
Problem polega na takim uszeregowaniu zadań
(przyporządkowaniu zadań do maszyn), aby spełnić pewne kryteria
•
Wyniki prezentujemy przy pomocy harmonogramu
Gantt’a
•
W kaŜdym uszeregowaniu moŜna określić:
o
Moment zakończenia zadania cj
o
Czas przepływu F = c – r
j
j
i
o
Opóźnienie l = c – d
j
j
j
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
5
aktualizacja: H. Gaspars-Wieloch
Szeregowanie zadań:
Najczęstsze kryteria oceny uszeregowań to:
•
Minimalizacja długości uszeregowania cmax
•
Minimalizacja średniego czasu przepływu
•
Minimalizacja maksymalnego opóźnienia
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
6
aktualizacja: H. Gaspars-Wieloch
3
α | β | γ
•
α = α α - rodzaj maszyn i liczba maszyn;
1
2
α : p – równoległe i identyczne, f – dedykowane i 1
przepływowy system obsługi; jeŜeli α nie jest podane, 2
liczba maszyn dowolna
•
β charakterystyka zadań: pmtn – zadania podzielne, prec –
ograniczenia kolejnościowe, p =1 – czasy wykonywania j
zadań są jednostkowe, r – róŜne czasy przybycia zadań do j
systemu
•
γ kryterium: C – maksymalny czas, F – średni czas max
przepływu, L
– maksymalne opóźnienie
max
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
7
aktualizacja: H. Gaspars-Wieloch
Problem p | pmtn | C
Co oznacza taki
max
zapis?
•
Maszyny równoległe i identyczne, liczba dowolna;
•
Zadania podzielne, róŜne czasy wykonania, brak
ograniczeń kolejnościowych, jednakowe czasy przybycia;
•
Kryterium – C
:
max
n
1
C
max max τ ;
τ
max =
{ j}
∑
j
m j=1
j
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
8
aktualizacja: H. Gaspars-Wieloch
4
1. Wybierz dowolne zadanie i rozpocznij jego wykonywanie na dowolnej maszynie w chwili t = 0.
2. Wybierz dowolne kolejne zadanie i rozpocznij jego wykonywanie na tej samej maszynie w chwili zakończenia poprzedniego zadania. Powtarzaj aŜ wszystkie zadania zostaną wykonane lub t = C
.
max
3. JeŜeli wykonane zostały wszystkie zadania, STOP. W
przeciwnym razie część zadania pozostałą po osiągnięciu t = C
przydziel do innej maszyny i rozpocznij
max
wykonywanie w chwili t = 0. Wróć do punktu 2.
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
9
aktualizacja: H. Gaspars-Wieloch
Przykład
p 3 | pmtn | Cmax
n = 6
τ
RozwiąŜmy inne
= [4, 5, 2, 1, 2, 1]
zadania ☺
C
= max{5;15/3}=5
max
M3
Z3
Z4
Z5
Z6
M2
Z2
Z3
M1
Z1
Z2
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
10
aktualizacja: H. Gaspars-Wieloch
5
Co oznacza taki
max
zapis?
•
2 maszyny równoległe, identyczne;
•
Zadania podzielne, róŜne czasy wykonania, dowolny
digraf kolejnościowy, jednakowe czasy przybycia;
•
Kryterium – Cmax
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
11
aktualizacja: H. Gaspars-Wieloch
Algorytm Muntza - Coffmana
1.
Wyznacz poziomy wszystkich jeszcze nie wykonanych zadań lub ich części (poziom = długość najdłuŜszej ścieŜki w digrafie łączącej dane zadanie z jednym z zadań końcowych).
2.
Przydzielaj zadania bez poprzedników o najwyŜszym poziomie ( n 1
zadań) do wolnych maszyn ( m maszyn) według zasad: 1
•
JeŜeli n > m , przydziel kaŜdemu zadaniu β = m / n mocy 1
1
1
1
wykonawczej maszyn; w przeciwnym razie przydziel kaŜdemu zadaniu maszynę;
•
JeŜeli są jeszcze wolne maszyny, to rozpatrz zadania o niŜszym poziomie;
•
Przydzielone zadania wykonuj do momentu, aŜ któreś z nich się zakończy albo kontynuacja dotychczasowego przydziału prowadziłaby do tego, Ŝe zadanie o wyŜszym poziomie byłoby wykonywane wolniej (z mniejszym β), niŜ zadanie o niŜszym poziomie
3.
W celu uzyskania uszeregowania optymalnego i dopuszczalnego zastosuj algorytm McNaughtona dla kaŜdego wykonania kroku 2.
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
12
aktualizacja: H. Gaspars-Wieloch
6
p 2 | pmtn, prec | Cmax n = 10
τ = [2, 1, 2, 1, 2, 3, 1, 1, 2, 1]
Z1(2,4)
Z2(1,5)
Z3(2,6)
Z4(1,2)
Z5(2,4)
Z6(3,5)
Z7(1,1)
Z8(1,1)
Z9(2,2)
Z10(1,1)
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
13
aktualizacja: H. Gaspars-Wieloch
Przykład
Z3
Z3
M2
Z2
M1
Z6
Z1(2,4)
Z4(1,2)
Z5(2,4)
Z6(2,4)
Z7(1,1)
Z8(1,1)
Z9(2,2)
Z10(1,1)
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
14
aktualizacja: H. Gaspars-Wieloch
7
Z3
Z3
Z1
Z1
M2
Z5
Z5
Z2
Z6
Z6
M1
Z6
Z4(1,2)
Z7(1,1)
Z8(1,1)
Z9(2,2)
Z10(1,1)
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
15
aktualizacja: H. Gaspars-Wieloch
Przykład
Z3
Z3
Z1
Z1
Z4
M2
Z5
Z5
Z2
Z9
Z6
Z6
M1
Z6
Z7(1,1)
Z8(1,1)
Z9(1,1)
Z10(1,1)
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
16
aktualizacja: H. Gaspars-Wieloch
8
Z3
Z3
Z1
Z1
Z4
Z7
M2
Z8
Z5
Z5
Z2
Z9
Z9
Z6
Z6
M1
Z6
Z10
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
17
aktualizacja: H. Gaspars-Wieloch
Przykład
RozwiąŜmy inne
zadania ☺
Z3
Z1
Z5
Z4
Z7
Z8
M2
Z2
Z6
Z5
Z6
Z9
Z9
Z
10
M1
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
18
aktualizacja: H. Gaspars-Wieloch
9
Co oznacza taki
max
zapis?
•
Jedna maszyna
•
Zadania niepodzielne, róŜne czasy wykonania, brak
ograniczeń kolejnościowych, jednakowe czasy przybycia, róŜne wymagane czasy zakończenia d ;
j
•
Kryterium – Lmax
Algorytm Jacksona
Przydzielaj zadania do maszyny w kolejności niemalejących wartości ich wymaganych terminów zakończenia.
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
19
aktualizacja: H. Gaspars-Wieloch
Przykład
1 | | Lmax
RozwiąŜmy inne
n = 4
zadania ☺
τ = [3, 4, 2, 2]
d = [5, 10, 6, 2]
Z4
Z1
Z3
Z2
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
20
aktualizacja: H. Gaspars-Wieloch
10
Co oznacza taki
j
max
zapis?
•
1 maszyna;
•
Zadania podzielne, róŜne czasy wykonania, brak
ograniczeń kolejnościowych, róŜne czasy przybycia;
•
Kryterium – Lmax
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
21
aktualizacja: H. Gaspars-Wieloch
Algorytm Liu - Leylanda
1. Spośród zadań dostępnych przydziel maszynę temu, które ma najniŜsze d . j
2. Przydzielone zadanie wykonuj aŜ się zakończy, lub stanie się dostępne zadanie o mniejszej wartości d . W tym drugim j
przypadku przerwij wykonywanie zadania.
3. JeŜeli są jeszcze dostępne zadania, wróć do kroku 1. W
przeciwnym razie STOP.
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
22
aktualizacja: H. Gaspars-Wieloch
11
1| pmtn, r | L
j
max
RozwiąŜmy inne
n = 5
zadania ☺
τ = [5, 6, 3, 2, 4]
r = [7, 2, 4, 0, 1]
d = [13, 10, 20, 25, 18]
Z
Z
Z2
Z1
Z5
Z3
Z
4
5
4
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
23
aktualizacja: H. Gaspars-Wieloch
Problem f2 | | C
Co oznacza taki
max
zapis?
•
2 maszyny; kaŜde z zadań składa się z 2 operacji, które muszą być wykonane kolejno na maszynie 1 i maszynie 2
dla wszystkich zadań w tej samej kolejności (system flow shop)
•
Zadania niepodzielne, róŜne czasy wykonania dla obu maszyn, brak ograniczeń kolejnościowych, jednakowe czasy przybycia;
•
Kryterium – Cmax
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
24
aktualizacja: H. Gaspars-Wieloch
12
Algorytm Johnsona
1. Wybierz zadania takie, Ŝe τ ≤ τ i uszereguj je w kolejności 1 j
2 j
niemalejących wartości τ (kolejność SPT – shortest 1 j
processing time).
2. Pozostałe zadania uszereguj w kolejności nierosnących wartości τ (kolejność LPT – longest processing time) 2 j
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
25
aktualizacja: H. Gaspars-Wieloch
Przykład
f 2| | Cmax
RozwiąŜmy inne
n = 5
zadania ☺
τ = [5, 4, 3, 2, 6]
1
τ = [2, 6, 3, 4, 2]
2
M1
Z4
Z3
Z2
Z1
Z5
M2
Z4
Z3
Z2
Z1
Z5
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
26
aktualizacja: H. Gaspars-Wieloch
13
Bad. oper. w logistyce
przygotowanie: M. Anholcer,
27
aktualizacja: H. Gaspars-Wieloch
14