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