Zmodyfikowany algorytm
Johnsona
Problem F3||Cmax
Autor: Marcin Grzymski
Zmodyfikowany algorytm
Johnsona
Problem F3||Cmax
Autor: Marcin Grzymski
Szeregowanie na procesorach
dedykowanych
• dla
F3||C
max
, w którym M
2
jest
zdominowana
przez M
1
(
i,j
p
1i
p
2j
) lub przez M
3
(
i,j
p
3i
p
2j
) można użyć Johnsona stosując
zmodyfikowane czasy wykonania (p
1i
+p
2i
, p
2i
+p
3i
), i=1,...,n.
1. Oblicz zmodyfikowane czasy wykonania:
t
1i
=p
1i
+p
2i
t
2i
=p
2i
+p
3i
,
Symbole t
1i
i t
2i
są dodatkowo wprowadzonymi parametrami
w celu wyznaczenia kolejności uszeregowania zadań w następnych krokach.
2. Podziel zadania na zbiory
N
1
={Z
j
: t
1j
<t
2j
}, N
2
={Z
j
: t
1j
t
2j
},
3. Porządkuj:
N
1
w kolejności niemalejącej t
1j
,
N
2
w kolejności nierosnącej t
2j
,
4. Utwórz harmonogram permutacyjny (maksymalnie
„przesunięty w lewo”) na podstawie kolejności N
1
,N
2
.
Szeregowanie na procesorach
dedykowanych
Przykład.
dla
F3||C
max
, w którym M
2
jest
zdominowana
przez M
1
,
m=3, n=5.
M
2
M
3
10
20
M
1
30
40
Z
5
Z
5
Z
5
M
2
M
3
10
20
M
1
30
40
Z
5
Z
5
Z
5
Z
2
Z
2
Z
2
M
2
M
3
10
20
M
1
30
40
Z
5
Z
5
Z
5
Z
2
Z
2
Z
2
Z
3
Z
3
Z
3
M
2
M
3
10
20
M
1
30
40
Z
5
Z
5
Z
5
Z
2
Z
2
Z
2
Z
3
Z
3
Z
3
Z
4
Z
4
Z
4
M
2
M
3
10
20
M
1
30
40
Z
5
Z
5
Z
5
Z
2
Z
2
Z
2
Z
3
Z
3
Z
3
Z
4
Z
4
Z
4
Z
1
Z
1
Z
1
Z
Z
Z
Z
Z
M
4
3
5
6
3
M
1
3
2
1
2
M
3
5
4
4
4
2
1
3
1
2
3
4
5
N
N
N
N
N
2
1
2
2
1
+
+
+
+
+
=
=
=
=
=
t
4
8
6
5
6
t
5
6
7
7
5
=
=
=
=
=
+
+
+
+
+
2
1
N
:
Z
Z
5
6
1
5
2
N
:
Z
Z
Z
6
5
4
2
3
4
1