Zmodyfikowany algorytm Liu
1|pmtn,prec,r
j
|L
max
Robert Janeczek
Zmodyfikowany algorytm Liu
1|pmtn,prec,r
j
|L
max
Robert Janeczek
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
Dla jednej maszyny
1|pmtn,prec,r
j
|L
max
zmodyfikowany
algorytm Liu O(n
2
):
1. określ
zmodyfikowane terminy zakończenia
zadań:
d
j
*=min{d
j
, min{d
i
:Z
j
Z
i
}}
2.
szereguj
według
EDD
dla
nowych
d
j
*
z
wywłaszczaniem zadania, gdy pojawia się nowe, wolne, z
mniejszym zmodyfikowanym terminem zakończenia,
3. powtarzaj 2 aż do uszeregowania wszystkich zadań.
Zadania zależne
Zadania podzielne
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
Dla jednej maszyny
1|pmtn,prec,r
j
|L
max
zmodyfikowany
algorytm Liu O(n
2
):
1. określ
zmodyfikowane terminy zakończenia
zadań:
d
j
*=min{d
j
, min{d
i
:Z
j
Z
i
}}
Czyli: najmniejsza wartość d
i
spośród przypisanych
do
danego zadania i na nie oczekujących
2.
szereguj
według
EDD
dla
nowych
d
j
*
z
wywłaszczaniem zadania, gdy pojawia się nowe, wolne, z
mniejszym zmodyfikowanym terminem zakończenia,
3. powtarzaj 2 aż do uszeregowania wszystkich zadań.
Zadania zależne
Zadania podzielne
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ X, X, X, X, X, X, X]
L
i
= [ X, X, X, X, X, X, X]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ X, X, X, X, X, X, X]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ 4, X, X, X, X, X, X]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ 4, X, X, X, X, X, X]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ 4, 6, X, X, X, X, X]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ 4, 6, X, X, X, X, X]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ 4, 6, 8, X, X, X, X]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ 4, 6, 8, X, X, X, X]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ 4, 6, 8,10, X, X, X]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ 4, 6, 8,10, X, X, X]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ 4, 6, 8,10,10, X, X]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ 4, 6, 8,10,10, X, X]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ 4, 6, 8,10,10,20, X]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ 4, 6, 8,10,10,20, X]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ 4, 6, 8,10,10,20,25]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ 4, 6, 8,10,10,20,25]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1 Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [ 3, 2, 2, 1, 4, 1, 2]
d
j
= [ 4, 6, 8,15,10,20,25]
r
j
= [ 0, 4, 2, 5, 6,15,13]
d
i
*= [ 4, 6, 8,10,10,20,25]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [
3
, 2, 2, 1, 4, 1, 2]
d
j
= [
4
, 6, 8,15,10,20,25]
r
j
= [
0
, 4, 2, 5, 6,15,13]
d
i
*= [
4
, 6, 8,10,10,20,25]
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Zadanie obecne w systemie
Zadanie jeszcze poza systemem
Zadanie wykonane
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2 Z3 Z4 Z5 Z6 Z7
p
i
= [
3
, 2, 2, 1, 4, 1, 2]
d
j
= [
4
, 6, 8,15,10,20,25]
r
j
= [
0
, 4, 2, 5, 6,15,13]
d
i
*= [
4
, 6, 8,10,10,20,25]
L
i
= [ X, X, X, X, X, X, X]
t = 1
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Z 1
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2 1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4 Z5 Z6 Z7
p
i
= [
3
, 2,
2
, 1, 4, 1, 2]
d
j
= [
4
, 6,
8
,15,10,20,25]
r
j
= [
0
, 4,
2
, 5, 6,15,13]
d
i
*= [
4
, 6,
8
,10,10,20,25]
L
i
= [ X, X, X, X, X, X, X]
t = 2
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Z 1
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2 1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4 Z5 Z6 Z7
p
i
= [
3
, 2,
2
, 1, 4, 1, 2]
d
j
= [
4
, 6,
8
,15,10,20,25]
r
j
= [
0
, 4,
2
, 5, 6,15,13]
d
i
*= [
4
, 6,
8
,10,10,20,25]
L
i
= [
-1
, X, X, X, X, X, X]
t = 3
Z 1
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4 Z5 Z6 Z7
p
i
= [
3
,
2
,
2
, 1, 4, 1, 2]
d
j
= [
4
,
6
,
8
,15,10,20,25]
r
j
= [
0
,
4
,
2
, 5, 6,15,13]
d
i
*= [
4
,
6
,
8
,10,10,20,25]
L
i
= [
-1
, X, X, X, X, X, X]
t = 4
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Z 1
Z 3
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2 1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4 Z5 Z6 Z7
p
i
= [
3
,
2
,
2
, 1, 4, 1, 2]
d
j
= [
4
,
6
,
8
,15,10,20,25]
r
j
= [
0
,
4
,
2
, 5, 6,15,13]
d
i
*= [
4
,
6
,
8
,10,10,20,25]
L
i
= [
-1
, X, X, X, X, X, X]
t = 4
Pojawia się Z2 i d
2
* < d
3
* więc przerywamy Z3
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Z 1
Z 3
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2 1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5 Z6 Z7
p
i
= [
3
,
2
,
2
,
1
, 4, 1, 2]
d
j
= [
4
,
6
,
8
,
15
,10,20,25]
r
j
= [
0
,
4
,
2
,
5
, 6,15,13]
d
i
*= [
4
,
6
,
8
,
10
,10,20,25]
L
i
= [
-1
, X, X, X, X, X, X]
t = 5
Z 1
Z 3
Z 2
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5
Z6 Z7
p
i
= [
3
,
2
,
2
,
1
,
4
, 1, 2]
d
j
= [
4
,
6
,
8
,
15
,
10
,20,25]
r
j
= [
0
,
4
,
2
,
5
,
6
,15,13]
d
i
*= [
4
,
6
,
8
,
10
,
10
,20,25]
L
i
= [
-1
,
0
, X, X, X, X, X]
t = 6
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Z 1
Z 3
Z 2
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5
Z6 Z7
p
i
= [
3
,
2
,
2
,
1
,
4
, 1, 2]
d
j
= [
4
,
6
,
8
,
15
,
10
,20,25]
r
j
= [
0
,
4
,
2
,
5
,
6
,15,13]
d
i
*= [
4
,
6
,
8
,
10
,
10
,20,25]
L
i
= [
-1
,
0
, X, X, X, X, X]
t = 6
Wznawiamy Z3, bo ma najniższy współczynnik d
i
* z
dostępnych zadań
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Z 1
Z 3
Z 2
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5
Z6 Z7
p
i
= [
3
,
2
,
2
,
1
,
4
, 1, 2]
d
j
= [
4
,
6
,
8
,
15
,
10
,20,25]
r
j
= [
0
,
4
,
2
,
5
,
6
,15,13]
d
i
*= [
4
,
6
,
8
,
10
,
10
,20,25]
L
i
= [
-1
,
0
,
-1
, X, X, X, X]
t = 7
Z 1
Z 3
Z 2
Z 3
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5
Z6 Z7
p
i
= [
3
,
2
,
2
,
1
,
4
, 1, 2]
d
j
= [
4
,
6
,
8
,
15
,
10
,20,25]
r
j
= [
0
,
4
,
2
,
5
,
6
,15,13]
d
i
*= [
4
,
6
,
8
,
10
,
10
,20,25]
L
i
= [
-1
,
0
,
-1
,
-7
, X, X, X]
t = 8
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Z 1
Z 3
Z 2
Z 3
Z 4
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2 1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5
Z6 Z7
p
i
= [
3
,
2
,
2
,
1
,
4
, 1, 2]
d
j
= [
4
,
6
,
8
,
15
,
10
,20,25]
r
j
= [
0
,
4
,
2
,
5
,
6
,15,13]
d
i
*= [
4
,
6
,
8
,
10
,
10
,20,25]
L
i
= [
-1
,
0
,
-1
,
-7
, X, X, X]
t = 9
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Z 1
Z 3
Z 2
Z 3
Z 4
Z 5
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2 1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5
Z6 Z7
p
i
= [
3
,
2
,
2
,
1
,
4
, 1, 2]
d
j
= [
4
,
6
,
8
,
15
,
10
,20,25]
r
j
= [
0
,
4
,
2
,
5
,
6
,15,13]
d
i
*= [
4
,
6
,
8
,
10
,
10
,20,25]
L
i
= [
-1
,
0
,
-1
,
-7
, X, X, X]
t = 10
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Z 1
Z 3
Z 2
Z 3
Z 4
Z 5
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5
Z6 Z7
p
i
= [
3
,
2
,
2
,
1
,
4
, 1, 2]
d
j
= [
4
,
6
,
8
,
15
,
10
,20,25]
r
j
= [
0
,
4
,
2
,
5
,
6
,15,13]
d
i
*= [
4
,
6
,
8
,
10
,
10
,20,25]
L
i
= [
-1
,
0
,
-1
,
-7
, X, X, X]
t = 11
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Z 1
Z 3
Z 2
Z 3
Z 4
Z 5
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5
Z6 Z7
p
i
= [
3
,
2
,
2
,
1
,
4
, 1, 2]
d
j
= [
4
,
6
,
8
,
15
,
10
,20,25]
r
j
= [
0
,
4
,
2
,
5
,
6
,15,13]
d
i
*= [
4
,
6
,
8
,
10
,
10
,20,25]
L
i
= [
-1
,
0
,
-1
,
-7
,
2
, X, X]
t = 12
Z 1
Z 3
Z 2
Z 3
Z 4
Z 5
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5
Z6
Z7
p
i
= [
3
,
2
,
2
,
1
,
4
, 1,
2
]
d
j
= [
4
,
6
,
8
,
15
,
10
,20,
25
]
r
j
= [
0
,
4
,
2
,
5
,
6
,15,
13
]
d
i
*= [
4
,
6
,
8
,
10
,
10
,20,
25
]
L
i
= [
-1
,
0
,
-1
,
-7
,
2
, X, X]
t = 13
Pojawia się Z7, ale musi zaczekać na Z6
Z 1
Z 3
Z 2
Z 3
Z 4
Z 5
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5
Z6
Z7
p
i
= [
3
,
2
,
2
,
1
,
4
, 1,
2
]
d
j
= [
4
,
6
,
8
,
15
,
10
,20,
25
]
r
j
= [
0
,
4
,
2
,
5
,
6
,15,
13
]
d
i
*= [
4
,
6
,
8
,
10
,
10
,20,
25
]
L
i
= [
-1
,
0
,
-1
,
-7
,
2
, X, X]
t = 14
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Z 1
Z 3
Z 2
Z 3
Z 4
Z 5
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5
Z6
Z7
p
i
= [
3
,
2
,
2
,
1
,
4
,
1
,
2
]
d
j
= [
4
,
6
,
8
,
15
,
10
,
20
,
25
]
r
j
= [
0
,
4
,
2
,
5
,
6
,
15
,
13
]
d
i
*= [
4
,
6
,
8
,
10
,
10
,
20
,
25
]
L
i
= [
-1
,
0
,
-1
,
-7
,
2
, X, X]
t = 15
Z 1
Z 3
Z 2
Z 3
Z 4
Z 5
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5
Z6
Z7
p
i
= [
3
,
2
,
2
,
1
,
4
,
1
,
2
]
d
j
= [
4
,
6
,
8
,
15
,
10
,
20
,
25
]
r
j
= [
0
,
4
,
2
,
5
,
6
,
15
,
13
]
d
i
*= [
4
,
6
,
8
,
10
,
10
,
20
,
25
]
L
i
= [
-1
,
0
,
-1
,
-7
,
2
,
-4
, X]
t = 16
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Z 1
Z 3
Z 2
Z 3
Z 4
Z 5
Z 6
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5
Z6
Z7
p
i
= [
3
,
2
,
2
,
1
,
4
,
1
,
2
]
d
j
= [
4
,
6
,
8
,
15
,
10
,
20
,
25
]
r
j
= [
0
,
4
,
2
,
5
,
6
,
15
,
13
]
d
i
*= [
4
,
6
,
8
,
10
,
10
,
20
,
25
]
L
i
= [
-1
,
0
,
-1
,
-7
,
2
,
-4
, X]
t = 17
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Z 1
Z 3
Z 2
Z 3
Z 4
Z 5
Z 6
Z 7
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5
Z6
Z7
p
i
= [
3
,
2
,
2
,
1
,
4
,
1
,
2
]
d
j
= [
4
,
6
,
8
,
15
,
10
,
20
,
25
]
r
j
= [
0
,
4
,
2
,
5
,
6
,
15
,
13
]
d
i
*= [
4
,
6
,
8
,
10
,
10
,
20
,
25
]
L
i
= [
-1
,
0
,
-1
,
-7
,
2
,
-4
,
-7
]
t = 18
Z 1
Z 3
Z 2
Z 3
Z 4
Z 5
Z 6
Z 7
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Minimalizacja maksymalnego opóźnienia na
maszynach równoległych
N=7
Z1
Z2
Z3
Z4
Z5
Z6
Z7
p
i
= [
3
,
2
,
2
,
1
,
4
,
1
,
2
]
d
j
= [
4
,
6
,
8
,
15
,
10
,
20
,
25
]
r
j
= [
0
,
4
,
2
,
5
,
6
,
15
,
13
]
d
i
*= [
4
,
6
,
8
,
10
,
10
,
20
,
25
]
L
i
= [
-1
,
0
,
-1
,
-7
,
2
,
-4
,
-7
]
t = 18
L
max
* = 2
Z
1
Z
3
Z
5
Z
2
Z
4
Z
6
Z
7
Z 1
Z 3
Z 2
Z 3
Z 4
Z 5
Z 6
Z 7
t
1
2
3
4
5
6
7
8
9
1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8