1

Szeregowanie zada

ń

 w modelu 

deterministycznym

dr hab. inŜ. Krzysztof Giaro

Politechnika Gdańska, Wydział ETI

pok. 207

Plan wykładu

1. Wstęp do deterministycznego szeregowania zadań
2. Metoda ścieŜki krytycznej
3. Podstawowe problemy optymalizacji dyskretnej
4. Minimalizacja kryterium C

max

5. Minimalizacja kryterium 

Σ

C

i

6. Minimalizacja kryterium L

max

7. Minimalizacja liczby spóźnionych zadań
8. Szeregowanie zadań na maszynach dedykowanych

Wst

ę

p do deterministycznego szeregowania zada

ń

Dziedzina 

ta 

zajmuje 

się 

szeregowaniem

(układaniem 

harmonogramów) 

zadań

(programów, czynności,  prac)  na 

maszynach

(procesorach, obrabiarkach, stanowiskach obsługi). 

Szukamy  harmonogramu  wykonania  dla  danego  zbioru  zadań  w 
określonych  warunkach,  tak  by  zminimalizować  przyjęte 

kryterium 

oceny

(koszt) uszeregowania. 

Model  deterministyczny

:  parametry  systemu  i  zadań  są  od  początku 

znane.

Geneza i motywacje praktyczne:

• harmonogramowanie produkcji przemysłowej,
• planowanie projektów,
• organizacja pracy, 
• plany zajęć szkolnych, spotkań i konferencji,
• przetwarzanie procesów w wielozadaniowych systemach operacyjnych,
• organizacja obliczeń rozproszonych.

Wst

ę

p do deterministycznego szeregowania zada

ń

M

1

M

2

M

3

Z

2

9

Z

4

Z

1

Z

5

Z

3

Reprezentacja graficzna harmonogramu – diagram Gantta

Przykład. 

Pięć  zadań  o  czasach  wykonania  p

1

,...,p

5

=6,9,4,1,4  naleŜy 

uszeregować  na  trzech  maszynach  tak,  by  zakończyły  się  one  moŜliwie  jak 
najszybciej.

Dlaczego ten harmonogram jest poprawny?

Klasyczna

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, 

• inne – wprowadzimy za chwilę ...

Wst

ę

p do deterministycznego szeregowania zada

ń

Sposoby obsługi zada

ń

Procesory 

równoległe

(kaŜdy procesor moŜe obsłuŜyć kaŜde zadanie):

• procesory identyczne

– wszystkie są jednakowo szybkie,

• procesory jednorodne

– mają róŜne szybkości, ale stosunki czasów 

wykonania zadań są niezaleŜne od maszyn,

• procesory dowolne

– prędkości zaleŜą od wykonywanych zadań.

M

1

M

2

M

3

Z

2

9

Z

4

Z

1

Z

5

Z

3

Uszeregowanie na maszynach równoległych

Wst

ę

p do deterministycznego szeregowania zada

ń

Sposoby obsługi zada

ń

Procesory 

dedykowane

•

zadania  są  podzielone  na  operacje  (zadanie  Z

j

zawiera  operacje  O

ij

do 

wykonania  na  maszynach  M

i

,  o  długościach  czasowych  p

ij

).  Zadanie  kończy 

się wraz z wykonaniem swej najpóźniejszej operacji,

•

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. 

Trzy główne typy systemów obsługi dla maszyn dedykowanych:
•

system  przepływowy

(flow

shop)  –

operacje  kaŜdego  zadania  są 

wykonywane  przez  procesory  w  tej  samej  kolejności  wyznaczonej  przez 
numery maszyn,
•

system  otwarty

(open shop)  – kolejność  wykonania  operacji  w  obrębie 

zadań jest dowolna,
•

system  gniazdowy

(job shop)  – dla  kaŜdego  zadania  mamy  dane 

przyporządkowanie maszyn operacjom oraz wymaganą kolejność.

2

Wst

ę

p do deterministycznego szeregowania zada

ń

Sposoby obsługi zada

ń

Procesory 

dedykowane

– system otwarty 

(kolejność operacji dowolna).

M

1

M

2

M

3

Z

2

7

Z

3

Z

1

Z

1

Z

2

Z

2

Z

1

Z

1

Z

3

Z

3

Nauczyciele

Klasy

M

1

M

2

M

3

Z

1

3

2

1

Z

2

3

2

2

Z

3

1

1

2

Przykład. Jednodniowy plan zajęć szkolnych.

Wst

ę

p do deterministycznego szeregowania zada

ń

Sposoby obsługi zada

ń

Procesory 

dedykowane

– system przepływowy (kolejność operacji musi być 

zgodna z numeracją maszyn).

 

M 

1

 

M 

2

 

M 

3

 

Z 

2

 

10 

Z 

3

 

Z 

1

 

Z 

1

 

Z 

2

 

Z 

2

 

Z 

1

 

Z 

1

 

Z 

3

 

Z 

3

 

Roboty

Detale

M

1

M

2

M

3

Z

1

3

2

1

Z

2

3

2

2

Z

3

1

1

2

Z

a

Z

b

Z

c

M

1

M

2

M

3

Maszyny dedykowane zostawimy na później ...

Przykład. Taśma produkcyjna.

Wst

ę

p do deterministycznego szeregowania zada

ń

Parametry zada

ń

Zadanie Z

j

:

•

Czas wykonywania

. Dla procesorów identycznych jest on niezaleŜny 

od  maszyny  i  wynosi  p

j

.  Procesory  jednorodne  M

i

charakteryzują  się 

współczynnikami szybkości b

i

, wtedy czas dla M

i

to p

j

/b

i

. Dla maszyn 

dowolnych mamy czasy p

ij

zaleŜne od zadań i procesorów.

•

Moment przybycia

(release time) r

j

. Czas, od którego zadanie  moŜe 

zostać podjęte. Wartość domyślna – zero.

•

Termin  zakończenia

d

j

.  Opcjonalny  parametr.  Występuje  w  dwóch 

wariantach.  MoŜe  oznaczać  czas,  od  którego  nalicza  się  spóźnienie 
(

due date

), lub termin, którego przekroczyć nie wolno (

deadline

).

•

Waga

w

j

– opcjonalny parametr, określający waŜność zadania przy 

naliczaniu kosztu harmonogramu. Domyślnie zadania są jednakowej 
wagi i wtedy w

j

=1.

Dane są: zbiór n zadań Z={Z

1

,...,Z

n

} oraz m maszyn (procesorów) 

M={M

1

,...,M

m

}.

Wst

ę

p do deterministycznego szeregowania zada

ń

Parametry zada

ń

Zadania zaleŜne

:

•

W  zbiorze  zadań  Z moŜna  wprowadzić 

ograniczenia  kolejnościowe

w  postaci  dowolnej  relacji  częściowego  porządku.  Wówczas  Z

i

pZ

j

oznacza,  Ŝe  zadanie  Z

j

moŜe  się  zacząć  wykonywać  dopiero  po 

zakończeniu Z

i

(

czemu?

np. Z

j

korzysta z wyników pracy Z

i

).

•

Jeśli  ograniczenia  te  nie  występują,  mówimy  o 

zadaniach 

niezaleŜnych

(tak się przyjmuje domyślnie) w przeciwnym razie są one 

zaleŜne

. 

•

Relację  zwykle  podaje  się  w  postaci  acyklicznego  digrafu o 

wierzchołkach  z  Z (droga  z  Z

i

do  Z

j

oznacza,  Ŝe  Z

i

pZ

j

)  z  łukami 

przechodnimi, lub bez (tylko relacje nakrywania – diagram Hassego).

Wst

ę

p do deterministycznego szeregowania zada

ń

Parametry zada

ń

Przykład. Harmonogram dla zadań zaleŜnych (p

j

podano w kółkach).

2

6

4

Z

5

1

1

2

3

1

Z

1

Z

2

Z

3

Z

4

Z

6

Z

7

Z

8

Z

9

Z

10

2

2

 M 

1

 

M 

2

 

M 

3

 

Z 

2

 

10 

Z 

10

 

Z

5

 

 

Z 

1

 

Z 

9

 

Z 

4

 

Z 

1

 

Z

3

Z 

6

 

5 

Z 

1

 

Z 

7

 

Z

8

 

 

Wst

ę

p do deterministycznego szeregowania zada

ń

Parametry zada

ń

Przykład. Harmonogram dla zadań zaleŜnych (p

j

podano w kółkach).

2

6

4

Z

5

1

1

2

3

1

Z

1

Z

2

Z

3

Z

4

Z

6

Z

7

Z

8

Z

9

Z

10

2

2

 M 

1

 

M 

2

 

M 

3

 

Z 

2

 

10 

Z 

10

 

Z

5

 

 

Z 

1

 

Z 

9

 

Z 

4

 

Z 

1

 

Z

3

Z 

6

 

5 

Z 

1

 

Z 

7

 

Z

8

 

 

3

Wst

ę

p do deterministycznego szeregowania zada

ń

Parametry zada

ń

Przykład. Harmonogram dla zadań zaleŜnych (p

j

podano w kółkach).

2

6

4

Z

5

1

1

2

3

1

Z

1

Z

2

Z

3

Z

4

Z

6

Z

7

Z

8

Z

9

Z

10

2

2

 M 

1

 

M 

2

 

M 

3

 

Z 

2

 

10 

Z 

10

 

Z

5

 

 

Z 

1

 

Z 

9

 

Z 

4

 

Z 

1

 

Z

3

Z 

6

 

5 

Z 

1

 

Z 

7

 

Z

8

 

 

Wst

ę

p do deterministycznego szeregowania zada

ń

Parametry zada

ń

Zadania mogą być:
•

niepodzielne

– przerwy w wykonaniu są niedopuszczalne 

(domyślnie),
•

podzielne

– wykonanie moŜna przerwać i podjąć ponownie, w 

przypadku maszyn równoległych nawet na innym procesorze.

Uszeregowanie zadań podzielnych na maszynach równoległych

M

1

M

2

M

3

Z

2

9

Z

1

Z

1

Z

3

Z

3

Z

3

Wst

ę

p do deterministycznego szeregowania zada

ń

Zasady poprawno

ś

ci harmonogramu

(juŜ w całości):

•

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 Z

j

wykonuje się w całości w przedziale czasu [r

j

,

∞

),

•

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.

Wst

ę

p do deterministycznego szeregowania zada

ń

PołoŜenie zadania Z

i

w gotowym harmonogramie:

•

moment zakończenia

C

i

(ang. completion time),

•

czas przepływu

przez system (flow time) F

i

=C

i

–r

i

,

•

opóźnienie

(lateness) L

i

=C

i

–d

i

,

•

spóźnienie

(tardiness) T

i

=max{C

i

–d

i

,0},

• “

znacznik spóźnienia

” U

i

=w(C

i

>d

i

), a więc odpowiedź (0/1 czyli 

Nie/Tak) na pytanie „czy zadanie się spóźniło?”

Kryteria kosztu harmonogramu

Wst

ę

p do deterministycznego szeregowania zada

ń

Kryteria kosztu harmonogramu

Najczęściej stosowane:

•

długość uszeregowania

C

max

=max{C

j

: j=1,...,n},

•

całkowity (łączny) czas zakończenia zadania

Σ

C

j

= 

Σ

i=1,...,n

C

i

,

•

ś

redni czas przepływu 

F = (

Σ

i=1,...,n

F

i

)/n.

M

1

M

2

M

3

Z

2

9

Z

4

Z

1

Z

5

Z

3

Uszeregowanie na trzech maszynach równoległych. p

1

,...,p

5

=6,9,4,1,4.

C

max

= 9,

ΣΣΣΣ

C

j

= 6+9+4+7+8 = 34

MoŜna wprowadzać wagi (priorytety) zadań:

•

całkowity waŜony czas zakończenia 

Σ

w

j

C

j

= 

Σ

i=1,...,n

w

i

C

i

,

w

1

,...,w

5

=1,2,3,1,1

ΣΣΣΣ

w

j

C

j

= 6+18+12+7+8 = 51

Wst

ę

p do deterministycznego szeregowania zada

ń

Kryteria kosztu harmonogramu

Oparte na wymaganych terminach zakończenia:

•

maksymalne opóźnienie

L

max

=max{L

j

: j=1,...,n},

•

maksymalne spóźnienie

T

max

=max{T

j

: j=1,...,n},

•

całkowite spóźnienie

Σ

T

j

= 

Σ

i=1,...,n

T

i

,

•

liczba spóźnionych zadań

Σ

U

j

= 

Σ

i=1,...,n

U

i

,

• moŜna wprowadzać wagi zadań, np łączne waŜone spóźnienie

Σ

w

j

T

j

= 

Σ

i=1,...,n

w

i

T

i.

M

1

M

2

M

3

Z

2

9

Z

4

Z

1

Z

5

Z

3

L

max

= T

max

= 2

ΣΣΣΣ

T

j

= 4, 

ΣΣΣΣ

U

j

= 2 

L

i

=

–1    2    –1      2      0

T

i

=

0    2     0       2      0

Zadanie: Z

1

Z

2

Z

3 

Z

4   

Z

5

d

i

=

7     7      5      5      8

Niektóre kryteria są sobie równowaŜne

Σ

L

i

= 

Σ

C

i

–

Σ

d

i

, F= (

Σ

C

i

)/n – (

Σ

r

i

)/n.

4

Wst

ę

p do deterministycznego szeregowania zada

ń

Jak to opisa

ć

? Notacja trójpolowa.

α

αα

α

|  

ββββ

|  

γγγγ

ś

rodowisko 

maszynowe

charakterystyka 

zadań

kryterium 

optymalizacji

α

moŜe mieć postać:

• P – procesory identyczne

• Q – procesory jednorodne

• R – procesory dowolne

• O – system otwarty (open shop)

• F – system przepływowy (flow shop)

• PF – „permutacyjny” flow shop

• J – system ogólny (job shop)

Ponadto:

• po symbolu moŜna podać liczbę 
maszyn np. 

O4

,

• dla jednej maszyny piszemy cyfrę 1 
bez symbolu (wtedy model nie ma 
znaczenia), 

• piszemy 

–

przy braku maszyn 

(czynności bezstanowiskowe).

Wst

ę

p do deterministycznego szeregowania zada

ń

Jak to opisa

ć

? Notacja trójpolowa.

ββββ

MoŜliwe wartości:

• pmtn – zadania podzielne (preemption),

• res – wymagane są dodatkowe zasoby (nie omawiamy),

• prec – zadania zaleŜne,

• r

j

– występują róŜne wartości momentów przybycia,

• p

j

=1 lub UET – zadania o jednostkowym czasie wykonania,

• p

ij

∈

{0,1} lub ZUET – operacje w zadaniach są jednostkowe lub puste 

(procesory dedykowane),

• C

j

≤

d

j

– istnieją wymagane i nieprzekraczalne terminy zakończenia zadań,

• no–idle – procesory muszą pracować w sposób ciągły, bez okienek,

• no–wait – okienka między operacjami w zadaniach są zabronione 
(procesory dedykowane).

ββββ

puste to cechy domyślne: zadania są niepodzielne, niezaleŜne, z 

r

j

=0, czasy wykonania i ewentualne wymagane terminy zakończenia 

d

j

dowolne.

Wst

ę

p do deterministycznego szeregowania zada

ń

Jak to opisa

ć

? Notacja trójpolowa.

ββββ

MoŜliwe wartości:

• in–tree, out–tree, chains ... – róŜne szczególne postaci relacji zaleŜności 
kolejnościowych (prec).

out–tree

in–tree

Wst

ę

p do deterministycznego szeregowania zada

ń

Jak to opisa

ć

? Notacja trójpolowa.

Przykłady.

P3|prec|C

max

– szeregowanie niepodzielnych zadań zaleŜnych na 

trzech identycznych maszynach równoległych w celu 
zminimalizowania długości harmonogramu.

R|pmtn,prec,r

i

|

ΣΣΣΣ

U

i

– szeregowanie podzielnych zadań zaleŜnych z 

róŜnymi czasami przybycia i terminami zakończenia na 
równoległych dowolnych maszynach (liczba procesorów jest 
częścią danych) w celu minimalizacji liczby zadań spóźnionych.

1|r

i

,C

i

≤≤≤≤

d

i

|–

– pytanie o istnienie (brak kryterium kosztu, więc nic 

nie optymalizujemy!) uszeregowania zadań niepodzielnych i 
niezaleŜnych o róŜnych momentach przybycia na jednej maszynie, 
tak by Ŝadne zadanie nie było spóźnione.

Wst

ę

p do deterministycznego szeregowania zada

ń

Redukcje podproblemów do problemów ogólniejszych

Przykłady.

1

P

Pm

Q

Qm

R

Rm

∅

p

i

=1

∅

r

j

∑w

i

F

i

F

∑w

i

T

i

∑T

i

∑w

i

U

i

∑U

i

L

max

C

max

prec

chain

∅

out–tree

in–tree

Wst

ę

p do deterministycznego szeregowania zada

ń

Zło

Ŝ

ono

ść

 problemów szeregowania

JeŜeli uwzględnimy tylko liczby maszyn 1,2,3,

•

, to istnieje 4536 

problemów, z których:

•

416 – wielomianowe,

•

3817 – NP–trudne,

•

303 – otwarte.

Jak sobie radzić z NP–trudnością?

•

wielomianowe  algorytmy 

przybliŜone

o  gwarantowanej 

dokładności względnej,

•

dokładne algorytmy 

pseudowielomianowe

,

•

algorytmy dokładne, szybkie tylko w 

ś

rednim przypadku

,

•

heurystyki

wyszukujące 

(np. 

tabu 

search, 

algorytmy 

genetyczne),

•

dla  małych  rozmiarów  danych  – wykładnicze 

przeszukiwanie 

wyczerpujące

(np. branch–bound). 

5

Ogólny schemat analizy zagadnienia

Problem optymalizacyjny X

wersja decyzyjna X

d

X

d

∈

P? 

↔

X

d

∈

NPC?

Stwórz efektywny

algorytm dla X

X

d

∈

PseudoP?  

↔

X

d

∈

NPC! ?

Zbuduj dla X algorytm 

pseudowielomianowy

Zadowalają nas przybliŜenia?

Tak

Wielomianowe algorytmy:
• przybliŜone
• schematy aproksymacyjne

Nie

Określ satysfakcjonującą

restrykcję zagadnienia X

• Małe dane: szukanie wyczerpujące (branch & bound)

• Heurystyki: tabu search, algorytmy genetyczne, ... 

Brak

Wst

ę

p do deterministycznego szeregowania zada

ń

Szeregowanie operacji bezprocesorowych. 

Metoda 

ś

cie

Ŝ

ki krytycznej.

Model 

–|prec|C

max

operacji o róŜnych czasach wykonania, z 

zaleŜnościami kolejnościowymi, ale nie wymagających procesorów. 
Celem jest znalezienie najkrótszego moŜliwego harmonogramu.

Relacja zaleŜności kolejnościowych p to 

częściowy porządek

(bez 

przekątnej) w zbiorze zadań, czyli jest ona:
• przeciwzwrotna: 

∀

Zi

¬

Z

i

pZ

i

• przechodnia 

∀

Zi,Zj,Zk,

(Z

i

pZ

j

∧

Z

j

pZ

k

) ⇒ Z

i

pZ

k

Szeregowanie operacji bezprocesorowych. 

Metoda 

ś

cie

Ŝ

ki krytycznej.

Sieć AN

(activity on node):

• wierzchołki odpowiadają operacjom, ich wagi (liczby naturalne) są równe 
czasom wykonywania,

• Z

i

pZ

j

⇔

w sieci istnieje ścieŜka skierowana z wierzchołka Z

i

do 

wierzchołka Z

j

,

• zwykle  usuwa się łuki przechodnie (jak w diagramie Hassego).

Metody reprezentacji relacji zaleŜności kolejnościowych p za pomocą

digrafu acyklicznego

.

Sieć AA

(activity on arc):

• łuki odpowiadają operacjom, ich długości są równe czasom wykonywania,

• przez kaŜdy wierzchołek przechodzi droga z Z (źródło) do U (ujście),

• Z

i

pZ

j

⇔

łuk Z

i

kończy się w początku łuku Z

j

, lub teŜ w sieci istnieje 

ś

cieŜka skierowana z końca łuku Z

i

do początku Z

j

,

• moŜna wprowadzać operacje pozorne – łuki o zerowej długości.

Szeregowanie operacji bezprocesorowych. 

Metoda 

ś

cie

Ŝ

ki krytycznej.

Przykład. Ta sama relacja porządku dla zbioru 19 operacji. 

Z

1

,3

Z

2

,8

Z

3

,2

Z

4

,2

Z

5

,4

Z

6

,6

Z

7

,9

Z

9

,1

Z

10

,2

Z

8

,2

Z

11

,1

Z

12

,2

Z

14

,5

Z

15

,9

Z

13

,6

Z

16

,6

Z

17

,2

Z

18

,5

Z

19

,3

sieć AN

A

Z

C

G

U

B

E

H

J

D

F

I

Z

19

,3

Z

13

,6

Z

8

,2

Z

4

,2

Z

2

,8

Z

10

,2

Z

15

,9

Z

17

,2

Z

12

,2

Z

7

,9

Z

18

,5

Z

14

,5

Z

9

,1

Z

5

,4

Z

1

,3

Z

3

,2

Z

6

,6

Z

11

,1

Z

16

,6

sieć AA

Metody reprezentacji relacji p za pomocą

digrafu acyklicznego

.

Przykład. Przy translacji AN 

 AA niekiedy trzeba wprowadzić (zerowe) 

operacje pozorne.

Z

1

Z

2

Z

3

Z

4

A

B

Z

0

,p

0

=0

Z

3

Z

1

Z

2

Z

4

Z

U

Szeregowanie operacji bezprocesorowych. 

Metoda 

ś

cie

Ŝ

ki krytycznej.

Model 

–|prec|C

max

operacji o róŜnych czasach wykonania, z 

zaleŜnościami kolejnościowymi, ale nie wymagających procesorów. 
Celem jest znalezienie najkrótszego moŜliwego harmonogramu.

Zasada

: dla kaŜdej operacji określamy najwcześniejszy moŜliwy moment 

uruchomienia tj. maksymalną „długość” ścieŜki doń prowadzącej. 

Jak to zrobić?

Algorytm

dla 

AN

: 

1. numeruj wierzchołki „topologicznie” (brak łuków „pod prąd”),
2. wierzchołkom Z

a

bez poprzedników nadaj etykietę l(Z

a

)=0, a kolejnym 

wierzchołkom Z

i

przypisuj l(Z

i

)=max{l(Z

j

)+p

j

: istnieje łuk z Z

j

do Z

i

},

Wynik: l(Z

i

) jest najwcześniejszym moŜliwym terminem rozpoczęcia Z

i

.

Algorytm

dla 

AA

: 

1. numeruj wierzchołki „topologicznie”,
2. źródłu Z nadaj etykietę l(Z)=0, a kolejnym wierzchołkom v przypisuj 
l(v)=max{l(u)+p

j

: łuk Z

j

prowadzi z u do v},

Wynik: l(v) wierzchołka początkowego Z

j

jest najwcześniejszym moŜliwym 

terminem rozpoczęcia tej operacji. l(U) to termin zakończenia harmonogramu.

Szeregowanie operacji bezprocesorowych. 

Metoda 

ś

cie

Ŝ

ki krytycznej.

Z:
A:
B:
C:
D:
E:
F:
G:
H:
I:
J:
U:

0 

Z:0+3 

3 

Z:0+2 

2 

Z:0+8, A:3+4, B:2+6  

8

A:3+2 

5

B:2+9

11

C:8+1, D:5+2

9

C:8+2, E:11+1

12

E:11+2

13

F:9+6, G:12+5

17

G:12+6, H:13+2

18

I:17+5, J:18+3, G:12+9

22

A

Z

C

G

U

B

E

H

J

D

F

I

Z

19

,3

Z

13

,6

Z

8

,2

Z

4

,2

Z

2

,8

Z

10

,2

Z

15

,9

Z

17

,2

Z

12

,2

Z

7

,9

Z

18

,5

Z

14

,5

Z

9

,1

Z

5

,4

Z

1

,3

Z

3

,2

Z

6

,6

Z

11

,1

Z

16

,6

Porządek 

topologiczny

Terminy

uruchomienia

Model 

–|prec|C

max

operacji o róŜnych czasach wykonania, z 

zaleŜnościami kolejnościowymi, ale nie wymagających procesorów. 
Celem jest znalezienie najkrótszego moŜliwego harmonogramu.

Przykład. Harmonogram dla sieci AA złoŜonej z 19 operacji. 

6

Szeregowanie operacji bezprocesorowych. 

Metoda 

ś

cie

Ŝ

ki krytycznej.

5

10

15

20

Z

1

Z

4

Z

3

Z

2

Z

6

Z

5

Z

7

Z

9

Z

8

Z

10

Z

11

Z

12

Z

13

Z

14

Z

15

Z

16

Z

17

Z

18

Z

19

Z:
A:
B:
C:
D:
E:
F:
G:
H:
I:
J:
U:

0 
3 
2 
8
5
11
9
12
13
17
18
22

Z

1

,3

Z

2

,8

Z

3

,2

Z

4

,2

Z

5

,4

Z

6

,6

Z

7

,9

Z

9

,1

Z

10

,2

Z

8

,2

Z

11

,1

Z

12

,2

Z

14

,5

Z

15

,9

Z

13

,6

Z

16

,

6

Z

17

,2

Z

18

,5

Z

19

,3

A

Z

C

G

U

B

E

H

J

D

F

I

Z

19

,3

Z

13

,6

Z

8

,2

Z

4

,2

Z

2

,8

Z

10

,2

Z

15

,9

Z

17

,2

Z

12

,2

Z

7

,9

Z

18

,5

Z

14

,5

Z

9

,1

Z

5

,4

Z

1

,3

Z

3

,2

Z

6

,6

Z

11

,1

Z

16

,6

Szeregowanie operacji bezprocesorowych. 

Metoda 

ś

cie

Ŝ

ki krytycznej.

• Algorytmy ścieŜki krytycznej minimalizują nie tylko 

C

max

, ale 

wszystkie zdefiniowane wcześniej funkcje kryterialne. 

• MoŜemy wprowadzić do modelu róŜne wartości terminów przybycia 
r

j

dla zadań 

Z

j

–

dodając „sztuczne” zadania  (o długości r

j

):

 jako wierzchołki – poprzednicy w modelu AN, 
 jako łuk prowadzący ze źródła Z do początku łuku Z

j

w modelu AA.

Podstawowe problemy optymalizacji dyskretnej

•

Zagadnienie 

maksymalnego  przepływu  w  sieci

.  Dany  jest 

multidigraf bez  pętli  D(V,E)  o  łukach  obciąŜonych  wagami  w:E

→

N

(przepustowość)  i  dwóch  wyróŜnionych  i  róŜnych  wierzchołkach  z
(źródło)  i  u (ujście).  Znajdź 

przepływ

p:E

→

N

∪

{0} o  maksymalnej 

moŜliwej 

objętości

. 

Co to jest przepływ o objętości P?

•

∀

e

∈

E

p(e)

≤

w(e),    

(nie wolno przekroczyć przepustowości łuków)

•

∀

v

∈

V–{z,u}

Σ

e wchodzi do v

p(e) –

Σ

e wychodzi z v

p(e) = 0, 

(do „zwykłego” wierzchołka „wpływa” tyle ile „wypływa”)

•

Σ

e wchodzi do u

p(e) –

Σ

e wychodzi z u

p(e) = P, 

(przez ujście „wypływa” z sieci P jednostek)

•

Σ

e wchodzi do z

p(e) –

Σ

e wychodzi z z

p(e) = –P. 

(wniosek: do źródła „wpływa” P jednostek)

Podstawowe problemy optymalizacji dyskretnej

•

Zagadnienie 

maksymalnego  przepływu  w  sieci

.  Dany  jest 

multidigraf bez  pętli  D(V,E)  o  łukach  obciąŜonych  wagami  w:E

→

N

(przepustowość)  i  dwóch  wyróŜnionych  i  róŜnych  wierzchołkach  z
(źródło)  i  u (ujście).  Znajdź 

przepływ

p:E

→

N

∪

{0} o  maksymalnej 

moŜliwej 

objętości

. 

2

5

3

1

1

2

3

2

2

1

1

4

Z

U

Sieć,  przepustowości
łuków.

Podstawowe problemy optymalizacji dyskretnej

•

Zagadnienie 

maksymalnego  przepływu  w  sieci

.  Dany  jest 

multidigraf bez  pętli  D(V,E)  o  łukach  obciąŜonych  wagami  w:E

→

N

(przepustowość)  i  dwóch  wyróŜnionych  i  róŜnych  wierzchołkach  z
(źródło)  i  u (ujście).  Znajdź 

przepływ

p:E

→

N

∪

{0} o  maksymalnej 

moŜliwej 

objętości

. 

2

/2

5

/2

3

/2

1

/0

1

/0

2

/2

3

/1

2

/2

2

/1

1

/1

1

/1

4

/1

Z

U

... i przepływ. P=5

ZłoŜoność O(|V||E|log(|V|

2

/|E|)) 

≤≤≤≤

O(|V|

3

).

Podstawowe problemy optymalizacji dyskretnej

•

RóŜne modele 

kolorowania grafów

.

•

Problemy 

najdłuŜszej (najkrótszej) drogi

w grafie.

•

Zagadnienia 

programowania  liniowego

– są  rozwiązywalne  w  czasie 

wielomianowym.

•

Wyszukiwanie 

skojarzeń w grafach

. Dany jest graf G(V,E) i funkcja wag 

zadana  na  krawędziach  w:E

→

N

∪

{0}. 

Skojarzeniem

nazywamy  dowolny 

podzbiór A

⊂

E o krawędziach niesąsiadujących.

• Największe  skojarzenie:

znajdź  skojarzenie  o  maksymalnej  moŜliwej 

liczbie krawędzi (

α

(L(G))). ZłoŜoność O(|E||V|

1/2

).

• NajcięŜsze  (najlŜejsze)  skojarzenie  o  danym rozmiarze

.  Dla  danej  liczby 

k

≤α

(L(G)) znajdź skojarzenie o k krawędziach i maksymalnej (minimalnej) 

moŜliwej sumie wag.

• NajcięŜsze  skojarzenie.

Znajdź  skojarzenie  o  maksymalnej  moŜliwej 

sumie  wag.  ZłoŜoności  O(|V|

3

) dla  grafów  dwudzielnych  i  O(|V|

4

) dla 

dowolnych grafów.

7

Podstawowe problemy optymalizacji dyskretnej

Liczność: 4

Waga: 4

1

10

1

1

1

1

1

1

1

10

1

1

1

1

1

1

Liczność: 3

Waga: 12

Największe skojarzenie nie musi być najcięŜszym i odwrotnie.

 M 

1

 

M 

2

 

M 

3

 

5 

 M 

1

 

M 

2

 

M 

3

 

Z 

1

 

5 

 M 

1

 

M 

2

 

M 

3

 

Z 

1

 

5 

Z 

2

 

Z 

2

 

 M 

1

 

M 

2

 

M 

3

 

Z 

1

 

5 

Z 

2

 

Z 

2

 

Z 

3

 

Z 

3

 

 M 

1

 

M 

2

 

M 

3

 

Z 

1

 

5 

Z 

2

 

Z 

2

 

Z 

4

 

Z 

3

 

Z 

3

 

 M 

1

 

M 

2

 

M 

3

 

Z 

1

 

5 

Z 

2

 

Z 

2

 

Z 

5

 

Z 

4

 

Z 

3

 

Z 

3

 

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania niezale

Ŝ

ne

Zadania podzielne

P|pmtn|C

max

.

Algorytm 

McNaughtona

ZłoŜoność O(n)

1. Wylicz optymalną długość 

C

max

*=max{

Σ

j=1,...,n

p

j

/m, max

j=1,...,n

p

j

}

,

2. Szereguj kolejno zadania na maszynie, po osiągnięciu C

max

* 

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, p

1

,...,p

5

=4,5,2,1,2. 

Σ

i=1,...,5

p

i

=14, max p

i

=5, 

C

max

*=max{14/3,5}=5.

Uwaga oznaczenie: przez 

X*

(gdzie X –

nazwa kryterium) będziemy rozumieli 

wartość optymalną

(tj. najmniejszą 

moŜliwą) tego kryterium dla 
konkretnej instancji problemu 
szeregowania np. C

max

*, L

max

*.

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania niezale

Ŝ

ne

Zadania niepodzielne

P||C

max

.

Problem jest NP–trudny juŜ na dwóch maszynach (

P2||C

max

). 

Dowód.

Problem podziału

: dany jest ciąg 

a

1

,...

a

n

liczb naturalnych o 

S=

Σ

i=1,...,n

a

i

parzystej. Czy istnieje jego podciąg o sumie 

S/2?

Redukcja 

PP 

 P2||C

max

: bierzemy 

n zadań o p

j

=

a

j

(

j=1,...,n), dwie 

maszyny, pytamy o istnienie uszeregowania z 

C

max

≤

S/2

.

M

1

M

2

S/2

p

i

...

...

Dokładny algorytm dynamiczny o czasie pracy O(nC

m

), gdzie C

≥

C

max

*.

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania niezale

Ŝ

ne

Zadania niepodzielne

P||C

max

.

Wielomianowe algorytmy przybliŜone. 

Szeregowanie listowe 

(

List Scheduling LS

) – stosowane w rozmaitych 

zagadnieniach:

• Ustal kolejność zadań na liście,
• Za kaŜdym razem, gdy zwalnia się jakaś maszyna/maszyny, wybieraj 
pierwsze (według „listy”) 

wolne (w tym momencie) zadania i przypisuj je do 

zwalniających się procesorów.

Dotyczy problemów z zaleŜnościami 
kolejnościowymi. Zadanie Z

i

jest 

wolne

od 

chwili, w której ukończony został jej ostatni 
poprzednik Z

j

(tj. Z

j

p

p

p

pZ

i

). 

Zadania niezaleŜne zawsze są wolne.

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania niezale

Ŝ

ne

Zadania niepodzielne

P||C

max

.

Wielomianowe algorytmy przybliŜone. 

Szeregowanie listowe 

(

List Scheduling LS

) – stosowane w rozmaitych 

zagadnieniach:

• Ustal kolejność zadań na liście,
• Za kaŜdym razem, gdy zwalnia się jakaś maszyna/maszyny, wybieraj 
pierwsze (według „listy”) 

wolne (w tym momencie) zadania i przypisuj je do 

zwalniających się procesorów.

Przykład. m=3, n=5, p

1

,...,p

5

=2,2,1,1,3. 

M

1

M

2

M

3

5

Uszeregowanie

listowe

Uszeregowanie

optymalne

M

1

M

2

M

3

Z

2

3

Z

1

Z

5

Z

3

Z

4

Z

1

Z

2

Z

3

Z

4

Z

5

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania niezale

Ŝ

ne

Zadania niepodzielne

P||C

max

.

Wielomianowe algorytmy przybliŜone. 

Szeregowanie listowe 

(

List Scheduling LS

) w skrócie:

• Z ustalonego ciągu zadań wybieraj pierwsze wolne (według „listy”), 
przypisując je zawsze do zwalniającego się procesora.

Dokładność. LS jest 2–przybliŜone: 

C

max

(LS)

≤

(2–m

–1

)C

max

*.

Dowód (obejmuje ogólniejszy model zadań z zaleŜnościami kolejnościowymi
P|prec|C

max

). W harmonogramie LS znajdujemy łańcuch zadań 

Z

π

(1)

,..., 

Z

π

(k)

:

Z

π

(1)

– skończone najpóźniej, 

Z

π

(2)

– jego skończony najpóźniej poprzednik 

(tj. 

Z

π

(2)

pZ

π

(1)

) itd. aŜ do zadania

bez poprzednika.

 

C

max

(LS)

Z

π

(1)

 

... 

... 

Z

π

(2)

 

C *

max

(pmtn)

≤

C

max

*

≤

≤

C

max

(LS) 

≤ Σ

i=1,...,k

p

π

(i)

+

Σ

i

∉

π

p

i

/m =

= (1–1/m)

Σ

i=1,...,k

p

π

(i)

+ 

Σ

i 

p

i

/m 

≤

≤

(2–1/

m)C *

max

(pmtn)

≤

(2–1/

m) C

max

*

8

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania niezale

Ŝ

ne

Zadania niepodzielne

P||C

max

.

Wielomianowe algorytmy przybliŜone. 

Szeregowanie LPT

(

Longest Processing Time

):

•

Szereguj listowo, przy czym zadania na liście są wstępnie 

posortowane według nierosnących czasów wykonania p

i

.

Dokładność. LS jest 4/3–przybliŜone: 

C

max

(LPT)

≤

(4/3–(3m)

–1

)C

max

*

.

Procesory dowolne, zadania niezale

Ŝ

ne

Zadania podzielne

R|pmtn|C

max

Istnieje algorytm wielomianowy – wrócimy do tego ... 

Zadania niepodzielne

R||C

max

•

Oczywiście problem jest NP–trudny (uogólnienie 

P||C

max

). 

• Podproblem

Q|p

i

=1|C

max

moŜna rozwiązać w czasie wielomianowym. 

• W praktyce stosuje się LPT.

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania zale

Ŝ

ne

Zadania podzielne

P|pmtn,prec|C

max

.

• W ogólności jest to problem NP–trudny. 
• Istnieje algorytm O(n

2

) dla 

P2|pmtn,prec|C

max

i 

P|pmtn,forest|C

max

. 

• Pomiędzy optymalnym harmonogramem z przerwami i bez zachodzi:

C*

max

≤

C(LS)

≤

(2–m

–1

)C*

max

(pmtn)

Dowód. Analogiczny jak w przypadku szeregowania listowego.

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania zale

Ŝ

ne

Zadania niepodzielne

P|prec|C

max

.

• Oczywiście problem jest NP–trudny. 
• Najbardziej znane przypadki wielomianowe dotyczą zadań jednostkowych: 



P|p

i

=1,in–forest|C

max

i 

P|p

i

=1,out–forest|C

max

(

Algorytm 

Hu

, 

złoŜoność O(n)),


P2|p

i

=1,prec|C

max

(

Algorytm Coffmana–Grahama

, złoŜoność O(n

2

)),

• JuŜ 

P|p

i

=1,opositing–forest|C

max

i 

P2|p

i

∈

∈

∈

∈

{1,2},prec|C

max

są NP–trudne.

Algorytm Hu

: 

• Redukcja  out–forest

 in–forest:  odwrócenie  relacji  prec,  a  po 

uzyskaniu harmonogramu – odwrócenie go,
• in–forest

 in–tree: dodanie “dodatkowego korzenia” dla wszystkich 

drzew, a po uzyskaniu harmonogramu usunięcie go.
• Procedura Hu w skrócie: szeregowanie listowe z ograniczeniami 
kolejnościowymi + lista utworzona wg. nierosnącej odległości od 
korzenia drzewa.

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania zale

Ŝ

ne

Zadania niepodzielne

Algorytm Hu 

(

P|p

i

=1,in–tree|C

max

): 

• Poziom zadania – liczba węzłów na drodze do korzenia.
• Zadanie jest wolne w chwili t – jeŜeli wcześniej wykonane zostały 
wszystkie zadania poprzedzające je.

Policz poziomy zadań;
t:=1;
repeat

Wyznacz listę L

t

zadań wolnych w chwili t;

Uporządkuj L

t

według nierosnącego poziomu;

Przypisz m (lub mniej) zadań z początku L

t

do maszyn;

Usuń przypisane zadania z grafu;
t:=t+1;

until uszeregowano wszystkie zadania;

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania zale

Ŝ

ne

Zadania niepodzielne

Przykład. Algorytm Hu. n=12, m=3.

Z

1

Z

2

Z

3

Z

4

Z

5

Z

7

Z

6

Z

10

Z

9

Z

8

Z

11

Z

12

1

2

3

4

- zadanie dostępne
(wolne)

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania zale

Ŝ

ne

Zadania niepodzielne

Przykład. Algorytm Hu. n=12, m=3.

Z

1

Z

2

Z

3

Z

4

Z

5

Z

7

Z

6

Z

10

Z

9

Z

8

Z

11

Z

12

1

2

3

4

 M 

1

 

M 

2

 

M 

3

 

5 

9

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania zale

Ŝ

ne

Zadania niepodzielne

Przykład. Algorytm Hu. n=12, m=3.

Z

1

Z

2

Z

3

Z

4

Z

5

Z

7

Z

6

Z

10

Z

9

Z

8

Z

11

Z

12

1

2

3

4

 M 

1

 

M 

2

 

M 

3

 

5 

Z 

1

 

Z 

3

 

Z 

2

 

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania zale

Ŝ

ne

Zadania niepodzielne

Przykład. Algorytm Hu. n=12, m=3.

Z

1

Z

2

Z

3

Z

4

Z

5

Z

7

Z

6

Z

10

Z

9

Z

8

Z

11

Z

12

1

2

3

4

 M 

1

 

M 

2

 

M 

3

 

5 

Z 

1

 

Z 

6

 

Z 

3

 

Z 

2

 

Z 

4

 

Z 

5

 

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania zale

Ŝ

ne

Zadania niepodzielne

Przykład. Algorytm Hu. n=12, m=3.

Z

1

Z

2

Z

3

Z

4

Z

5

Z

7

Z

6

Z

10

Z

9

Z

8

Z

11

Z

12

1

2

3

4

 M 

1

 

M 

2

 

M 

3

 

5 

Z 

1

 

Z 

6

 

Z 

3

 

Z 

2

 

Z 

4

 

Z 

5

 

Z 

9

 

Z 

7

 

Z 

8

 

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania zale

Ŝ

ne

Zadania niepodzielne

Przykład. Algorytm Hu. n=12, m=3.

Z

1

Z

2

Z

3

Z

4

Z

5

Z

7

Z

6

Z

10

Z

9

Z

8

Z

11

Z

12

1

2

3

4

 M 

1

 

M 

2

 

M 

3

 

5 

Z 

1

 

Z 

6

 

Z 

3

 

Z 

2

 

Z 

4

 

Z 

5

 

Z 

9

 

Z 

7

 

Z 

8

 

Z 

10

 

Z 

11

 

 M 

1

 

M 

2

 

M 

3

 

5 

Z 

1

 

Z 

6

 

Z 

3

 

Z 

2

 

Z 

4

 

Z 

5

 

Z 

9

 

Z 

7

 

Z 

8

 

Z 

10

 

Z 

11

 

Z 

12

 

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania zale

Ŝ

ne

Zadania niepodzielne

Algorytm Hu 

(

P|p

i

=1,in(out)–forest|C

max

)

Dowód. Porządek in-forest, indukcja ze względu na liczbę zadań (krok 2):

• W kolejnych krokach algorytmu liczba wolnych zadań nie wzrasta.
• Wniosek: w kolejnych chwilach liczba zajętych procesorów nie rośnie.

 

P 

1

 

P 

m

 

l 

k 

• Jeśli 

k

∈

{0,1} 

lub 

l=0, 

to 

harmonogram jest optymalny.

• Niech Z’

⊂

Z oznacza podzbiór zadań z 

poziomów ≥ k. W chwili l+1 wykonano
ostatnie zadanie z Z’. Wykreślając 
pozostałe zadania otrzymamy harmonogram Hu (czyli optymalny) dla Z’.

• Zatem w kaŜdym  harmonogramie dla Z jest zadanie z Z’ jest wykonywane 
najwcześniej w chwili l+1, a po nim występuje jeszcze łańcuch k–1 zadań.
• Wniosek: nasz harmonogram jest optymalny.

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania zale

Ŝ

ne

Zadania niepodzielne

Algorytm Coffmana–Grahama

(

P2|p

i

=1,prec|C

max

): 

1. numeruj zadania przypisując im etykiety l od 1 do n, 

2.

szereguj  listowo,  przy  czym  kolejność  na  liście  odpowiada  malejącym 
etykietom zadań.

Faza 1 – numerowanie  zadań;
Początkowo zadania nie mają list ani etykiet l;
for i:=1 to n do begin

A:=zbiór zadań bez etykiet l, których wszystkie 
bezpośrednie następniki juŜ mają etykiety;
for each Z

∈

A do przypisz do list(Z) malejący ciąg etykiet l

jego bezpośrednich następników;

wybierz Z

∈

A o leksykograficznie najmniejszym list(Z);

l(Z):=i;

end;

10

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania zale

Ŝ

ne

Zadania niepodzielne

Przykład. Algorytm Coffmana–Grahama, n=17.

Z

1

Z

3

Z

2

Z

4

Z

5

Z

6

Z

7

Z

9

Z

10

Z

8

Z

11

Z

12

Z

14

Z

17

Z

13

Z

15

Z

16

( )

( )

( )

( )

1

(1)

(1)

2

(2)

3

(3,2)

4

(4,3,2)

5

(5)

6

7

(7)

8

9

(9)

(9)

(9,6)

10

11

(11,8)

12

(12,10)

13

14

15

(15,13)

16

17

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania zale

Ŝ

ne

Zadania niepodzielne

Przykład. Algorytm Coffmana–Grahama, n=17.

Z

1

Z

3

Z

2

Z

4

Z

5

Z

6

Z

7

Z

9

Z

10

Z

8

Z

11

Z

12

Z

14

Z

17

Z

13

Z

15

Z

16

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

Kolejność na liście: 
Z

2

, Z

1

, Z

7

, Z

3

, Z

6

, Z

5

, Z

12

, Z

4

, Z

10

, 

Z

11

, Z

16

, Z

9

, Z

8

, Z

17

, Z

14

, Z

15

, Z

13

.

 

M 

1

 

M 

2

 

9 

Z 

12

 

Z 

7

 

Z 

2

 

Z 

1

 

Z 

11

 

Z 

3

 

Z 

6

 

Z 

9

 

Z 

5

 

Z 

17

 

Z 

4

 

Z 

15

 

Z 

10

 Z 

16

 Z 

8

  Z 

14

 Z 

13

 

Minimalizacja długo

ś

ci harmonogramu. 

Maszyny równoległe.

Procesory identyczne, zadania zale

Ŝ

ne

Zadania niepodzielne

Dla 

P|prec|C

max

moŜna stosować heurystykę LS. W ogólności jest ona 

2–przybliŜona: 

C

max

(LS)

≤

(2–m

–1

)C

max

*.

Dowód. JuŜ był ...

Kolejność  zadań  na  liście  (priorytety)  ustala  się  róŜnymi  metodami. 
Mogą  się  pojawiać  anomalie  polegające  na  wydłuŜaniu  się 
harmonogramu przy:

•

wzroście liczby maszyn,

•

zmniejszaniu czasu wykonania zadań,

•

zmniejszaniu relacji prec,

•

zmianie kolejności na liście.

Minimalizacja 

ś

redniego czasu przepływu na maszynach 

równoległych

Procesory identyczne, zadania niezale

Ŝ

ne

Wnioski.
• długość pierwszego zadania jest mnoŜona przez największy 
współczynnik, dla kolejnych zadań współczynniki maleją,
• minimalizując 

Σ

C

j

powinniśmy umieszczać krótkie zadania na początku 

(są mnoŜone przez największe współczynniki),
• optymalne uszeregowanie jest zgodne z regułą

SPT

(

Shortest Processing

Times

) – zadania na maszynach są podejmowane w kolejności 

niemalejących czasów wykonania,
•

ale jak znaleźć optymalne przypisanie zadań do procesorów?

Własność: zadanie Z

j

na maszynie M

i

umieszczone na k–tej pozycji od 

końca dodaje do kryterium 

ΣΣΣΣ

C

j

wartość kp

j

(lub kp

ij 

dla maszyn 

R|

).

 

M 

Z 

a

 

Z 

c

 

Z 

b

 

×

3 

×

2 

×

1 

Minimalizacja 

ś

redniego czasu przepływu na maszynach 

równoległych

Procesory identyczne, zadania niezale

Ŝ

ne

Zadania podzielnie i niepodzielne
Przypadki 

P||

ΣΣΣΣ

C

i

i podzielnych 

P|pmtn|

ΣΣΣΣ

C

i

moŜna rozpatrywać razem 

(optymalny harmonogram podzielny nie musi dzielić zadań).

Algorytm optymalny

O(nlog n):

1. Przyjmij, Ŝe liczba zadań dzieli się przez m (ew. wprowadź zadania puste),
2. Uporządkuj je według 

SPT,

3. Przypisuj kolejne m–tki zadań w sposób dowolny do róŜnych maszyn.

Przykład. m=2, n=5, p

1

,...,p

5

=2,5,3,1,3.

SPT:  

Z

4

Z

1

Z

3 

Z

5   

Z

2

p

i

=

1      2      3      3      5

 M 

1

 

M 

2

 

8 

 M 

1

 

M 

2

 

8 

Z 

4

 

 M 

1

 

M 

2

 

8 

Z 

4

 

Z 

3

 

Z 

1

 

 M 

1

 

M 

2

 

8 

Z 

4

 

Z 

3

 

Z 

1

 

Z 

5

 

Z 

2

 

 

M 

1

 

M 

2

 

Z 

4

 

Z 

3

 

Z 

1

 

Z 

5

 

Z 

2

 

MoŜna  
i tak: 

9 

ΣΣΣΣ

C

j

*=21

Z

0

0

Zadanie puste

Minimalizacja 

ś

redniego czasu przepływu na maszynach 

równoległych

Procesory identyczne, zadania niezale

Ŝ

ne

Zadania podzielnie i niepodzielne
Przypadki 

P||

ΣΣΣΣ

C

i

i podzielnych 

P|pmtn|

ΣΣΣΣ

C

i

moŜna rozpatrywać razem 

(optymalny harmonogram podzielny nie musi dzielić zadań).

Algorytm optymalny

O(nlog n):

1. Przyjmij, Ŝe liczba zadań dzieli się przez m (ew. wprowadź zadania puste),
2. Uporządkuj je według 

SPT,

3. Przypisuj kolejne m–tki zadań w sposób dowolny do róŜnych maszyn.

Dowód (przypadek niepodzielny).

Lemat. Dane są dwa ciągi liczb a

1

,...,a

n

i b

1

,...,b

n

. W jaki sposób naleŜy je 

popermutować, by iloczyn skalarny a

π

(1)

b

τ

(1)

+a

π

(2)

b

τ

(2)

+...+a

π

(n

–1

)

b

τ

(n

–1

)

+a

π

(n)

b

τ

(n)

był moŜliwie:
• największy?
• najmniejszy?

– oba posortować niemalejąco,
– jeden posortować niemalejąco, a drugi nierosnąco.

Przykład. Mamy ciągi (3,2,4,6,1) i (5,7,8,1,2).
(1,2,3,4,6) i (1,2,5,7,8) 

 1+4+15+28+48=96

(1,2,3,4,6) i (8,7,5,2,1) 

 8+14+15+8+6=51

11

Minimalizacja 

ś

redniego czasu przepływu na maszynach 

równoległych

Procesory identyczne, zadania niezale

Ŝ

ne

Zadania podzielnie i niepodzielne
Przypadki 

P||

ΣΣΣΣ

C

i

i podzielnych 

P|pmtn|

ΣΣΣΣ

C

i

moŜna rozpatrywać razem 

(optymalny harmonogram podzielny nie musi dzielić zadań).

Algorytm optymalny

O(nlog n):

1. Przyjmij, Ŝe liczba zadań dzieli się przez m (ew. wprowadź zadania puste),
2. Uporządkuj je według SPT,
3. Przypisuj kolejne m–tki zadań w sposób dowolny do róŜnych maszyn.

Dowód (przypadek niepodzielny). RozwaŜamy uszeregowanie optymalne. 
MoŜna przyjąć, Ŝe na kaŜdej maszynie jest k zadań (ew. zadania puste).

 M 

1

 

M

m

 

Z

π

(1)

 

Z

π

(m)

 

… 

Z

π

(m+1)

 

Z

π

(2m)

 

Z

π

(km-m+1)

 

Z

π

(km)

 

Σ

C

i 

=  kp

π

(1)

+...+kp

π

(m)

+

+(k–1)p

π

(m+1) 

+...+(k–1)p

π

(2m)

+

+1p

π

(km–m+1) 

+...+1p

π

(km)

Przestawienie zadań według SPT 
nie zwiększy 

Σ

C

i

.

Minimalizacja 

ś

redniego czasu przepływu na maszynach 

równoległych

Procesory identyczne, zadania niezale

Ŝ

ne

Zadania niepodzielne
JuŜ wersja waŜona  

P2||

ΣΣΣΣ

w

j

C

j

(a takŜe równowaŜna 

P2|pmtn|

ΣΣΣΣ

w

j

C

j

) jest 

NP–trudna

.

Dowód. Jak w P2||C

max

. Redukcja PP 

 P2||

ΣΣΣΣ

w

i

C

i

: bierzemy n zadań o p

j

= 

w

j

=a

j

(j=1,...,n), dwie maszyny. Wyznacz liczbę C(a

1

,...,a

n

) taką, Ŝe istnieje 

uszeregowanie o 

Σ

w

j

C

j

≤

C(a

1

,...,a

n

) 

⇔

C

max

*

= 

Σ

i=1,...,n

a

i

/2 (ćwiczenie).

Wariant  waŜony  jednomaszynowy  (

1||

ΣΣΣΣ

w

j

C

j

)  moŜna  rozwiązać  w 

czasie 

O(nlog n)

szeregując według 

reguły Smitha

(uogólnione SPT):

• ustaw zadania w kolejności niemalejącego p

j

/w

j

.

Dowód. RozwaŜamy przyrost kryterium po zamianie dwóch kolejnych 
zadań. 
w

j

p

j

+w

i

(p

i

+p

j

) – w

i

p

i

– w

j

(p

i

+p

j

)  = 

= w

i

p

j

– w

j

p

i

≥

0 

⇔

p

j

/w

j

≥

p

i

/w

i

Naruszenie reguły Smitha sprawi, Ŝe 
wartość

Σ

w

i

C

i 

zmaleje po zamianie.

 

M 

Z 

j

 

Z 

i

 

Minimalizacja 

ś

redniego czasu przepływu na maszynach 

równoległych

Procesory identyczne, zadania niezale

Ŝ

ne

Zadania niepodzielne

Próbą pogodzenia kryteriów 

C

max

i 

ΣΣΣΣ

C

i

jest 

algorytm RPT

:

1. Zastosuj szeregowanie LPT.
2. Na kaŜdej maszynie posortuj zadania według SPT.

Dokładność:

1

≤Σ

C

i

(RPT)

/

Σ

C

i

*

≤

m   

(zwykle jest lepsza)

Procesory identyczne, zadania zale

Ŝ

ne

•

JuŜ 

1|prec|

ΣΣΣΣ

C

i

,

P|prec,p

j

=1|

ΣΣΣΣ

C

i

, 

P2|prec,p

j

∈

∈

∈

∈

{1,2}|

ΣΣΣΣ

C

i

, 

P2|chains|

ΣΣΣΣ

C

i

i 

P2|chains,pmtn|

ΣΣΣΣ

C

i

są NP–trudne.

• Znane są wielomianowe algorytmy dla 

P2|prec,p

j

=1|

ΣΣΣΣ

C

i

(Coffman–

Graham) i 

P|out–tree,p

j

=1|

ΣΣΣΣ

C

i

(adaptacja algorytmu Hu).

• W wersji waŜonej nawet przypadek jednomaszynowy zadaniami 
jednostkowymi 

1|prec,p

j

=1|

ΣΣΣΣ

w

i

C

i

jest NP–trudny.

Minimalizacja 

ś

redniego czasu przepływu na maszynach 

równoległych

Procesory dowolne, zadania niezale

Ŝ

ne

Algorytm O(n

3

) dla 

R||

ΣΣΣΣ

C

i 

bazuje na problemie skojarzeń 
w grafach.

Graf dwudzielny z 

krawędziami obciąŜonymi 
wagami:

•

W partycji V

1

zadania Z

1

,...,Z

n

.

•

W partycji V

2

kaŜdy procesor n

razy: 

k

M

i

, i=1...m, k=1...n.

•

Krawędź z Z

j

do 

k

M

i

ma wagę 

kp

ij

– oznacza ona zadanie Z

j

na 

maszynie M

i

, pozycja k–ta od 

końca.

kp

ij

Z

1

Z

j

Z

n

1

M

1

1

M

m

2

M

1

n

M

m

n

M

1

k

M

i

2

k

n

1

Szukamy najlŜejszego skojarzenia o 
n krawędziach. Przedstawia ono 
szukany harmonogram.

Minimalizacja maksymalnego opó

ź

nienia na maszynach 

równoległych

• Spóźnienie  zadania  T

i

=max{L

i

,0}  nie  bierze  pod  uwagę  wykonania 

się zadań przed terminem.

• Wniosek: T

max

=max{L

max

,0}. Dlatego kryterium T

max

nie rozwaŜamy 

osobno – harmonogram L

max

-optymalny jest teŜ T

max

-optymalny.

• L

max

*

to  najmniejsza  liczba  x,  taka  Ŝe  przedłuŜenie  terminów

d

i

'=d

i

+x pozwala  nie  spóźnić  się  z  Ŝadnym  zadaniem  (spełnione  są 

nowe deadline-y C

i

≤

d

i

' zadań Z

i

).

• Wniosek: 

minimalizacja 

L

max

i 

szukanie 

(jeśli 

istnieje) 

harmonogramu  respektującego  nieprzekraczalne  deadline-y

(tj. 

pytania 

...|...|L

max

i 

...|...,C

i

≤

d

i

|–

) to problemy „jednakowo trudne”.

Własności:

• Aby  opóźnienie  L

i

=C

i

–d

i

zadania  Z

i

w  harmonogramie  było 

określone,  zadania  muszą  być  wyposaŜone  w  oczekiwane  terminy 
zakończenia d

i

.

Minimalizacja maksymalnego opó

ź

nienia na maszynach 

równoległych

Własności:
•

kryterium L

max

jest uogólnieniem C

max

, zagadnienia NP–trudne dla C

max

pozostaną takie w przypadku L

max

,

• mając do wykonania wiele prac z róŜnymi oczekiwanymi terminami 
zakończenia spóźnimy się „najmniej” zaczynając zawsze od 
„najpilniejszej” pracy,
• to samo innymi słowy: w róŜnych wariantach stosujemy 

regułę EDD

(

Earliest Due Date

) – wybieraj zadania Z

j

w kolejności niemalejących 

oczekiwanych terminów zakończenia d

j

,

• problem zadań niepodzielnych na jednej maszynie (

1||L

max

) rozwiązuje 

właśnie szeregowanie według EDD.

 

M 

Z 

a

 

Z 

b

 

d

a

 

d

b

 

M 

Z 

a

 

Z 

b

 

d

a

 

d

b

 

12

Minimalizacja maksymalnego opó

ź

nienia na maszynach 

równoległych

Procesory identyczne, zadania niezale

Ŝ

ne

Zadania podzielne

Jedna maszyna: 

Algorytm Liu

O(n

2

), oparty na regule EDD, 

działający nawet przy 

1|r

i

,pmtn|L

max

:

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).

Dowód. S

Liu

– harmonogram uzyskany algorytmem Liu. S – inny 

harmonogram. Zadania Z

i

respektują deadline-y d

i

’=d

i

+L

max

(S).

Zaczynając od t=0 
przekształcimy S w S

Liu

nie naruszając d

i

’.

• W S

Liu

w chwili t

uruchomiono T

i

 

T 

i

T 

 j

 

t 

… 

… 

… 

r

i

, r

j

d

i

’      d

j

’

T

i

T

j

t

…

…

…

T

j

Wniosek: L

max

(S

Liu

) ≤ L

max

(S).

Minimalizacja maksymalnego opó

ź

nienia na maszynach 

równoległych

Procesory identyczne, zadania niezale

Ŝ

ne

Zadania podzielne

Jedna maszyna: 

Algorytm Liu

O(n

2

), oparty na regule EDD, 

działający nawet przy 

1|r

i

,pmtn|L

max

:

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).

Więcej maszyn (

P|r

i

,pmtn|L

max

). RównieŜ algorytm wielomianowy:

korzystamy z podprocedury rozwiązującej wersję z “twardymi” 
terminami zakończenia 

P|r

i

,C

i

≤≤≤≤

d

i

,pmtn|–

, szukamy optymalnego 

L

max

metodą połowienia.

Minimalizacja maksymalnego opó

ź

nienia na maszynach 

równoległych

P|r

i

,C

i

≤≤≤≤

d

i

,pmtn|–

sprowadzamy do problemu przepływu. Ustawiamy 

wszystkie r

i

i d

i

w ciąg e

0

<e

1

<...<e

k

.

m(e

1

–e

0

)

m(e

i

–e

i–1

)

Z

U

w

1

w

i

w

k

Z

1

Z

j

Z

n

m(e

k

–e

k–1

)

p

1

p

j

p

n

e

1

–e

0

e

i

–e

i–1

Tworzymy sieć:
• Ze źródła wychodzi k łuków o 
przepustowości m(e

i

–e

i–1

) do 

wierzchołków w

i

, i=1,...,k.

• Do ujścia wchodzą łuki o 
przepustowości p

i

z 

wierzchołków Z

i

, i=1,...,n.

• Między w

i

a Z

j

biegnie łuk o 

przepustowości e

i

–e

i–1

, jeŜeli 

zachodzi [e

i–1

,e

i

]

⊆

[r

j

,d

j

].

Uszeregowanie istnieje 

⇔

istnieje przepływ o objętości 

Σ

i=1,...,n

p

i

(moŜna 

rozdysponować moce obliczeniowe procesorów do zadań w odpowiednich 
odcinkach czasu, tak by wykonać wszystkie).

Minimalizacja maksymalnego opó

ź

nienia na maszynach 

równoległych

Niektóre przypadki NP–trudne: 

P2||L

max

, 1|r

j

|L

max

.

Zadania niezale

Ŝ

ne

Zadania niepodzielne

Przypadki wielomianowe:
• dla zadań jednostkowych 

P|p

j

=1,r

j

|L

max

.  

• podobnie  dla  maszyn  jednorodnych 

Q|p

j

=1|L

max

(redukcja  do 

programowania liniowego),
• dla  jednej  maszyny  rozwiązanie  optymalne 

1||L

max

uzyskamy 

szeregując według EDD (to juŜ było ...).

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

i

{d

i

:Z

j

pZ

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

• Inne przypadki wielomianowe: 

P|pmtn,in–tree|L

max

, Q2|pmtn,prec,r

j

|L

max

. 

• Stosuje się teŜ algorytmy pseudowielomianowe.

Minimalizacja maksymalnego opó

ź

nienia na maszynach 

równoległych

• JuŜ 

P|p

j

=1,out–tree|L

max

jest NP–trudny.

• istnieje wielomianowy algorytm dla 

P2|prec,p

j

=1|L

max

.

•

P|p

j

=1,in–tree|L

max

rozwiązuje 

algorytm Bruckera

O(nlog n):

Zadania zale

Ŝ

ne

Zadania niepodzielne

next(j) = bezpośredni następnik zadania Z

j

.

1. wylicz zmodyfikowane terminy zakończenia zadań:

dla korzenia 

d

root

*=1–d

root

i dla pozostałych 

d

k

*=max{1+d

next(k)

*,1–d

k

}

,

2. szereguj zadania dostępne podobnie jak w algorytmie Hu, ale remisy 
rozstrzygaj wybierając zadania według nierosnących 
zmodyfikowanych terminów zakończenia, a nie według poziomów w 
drzewie.

Czyli znowu szeregowanie listowe z inną 
metodą wyznaczania kolejności na liście.