Microsoft PowerPoint - Badania operacyjne-wykład 4

2014-01-10

Podział metod programowania sieciowego

Metody deterministyczne – metody o ustalonej
strukturze sieci, w której czasy trwania czynno

stałe i znane lub maj

charakter

probabilistyczny

Metody stochastyczne – metody o
niezdeterminowanej strukturze logicznej sieci, w
której czasy trwania czynno

ci mo

na okre

tylko z pewnym prawdopodobie

stwem.

ID,2013/2014

Podstawowe pojęcia

Zespół poł

czonych ze sob

czynno

wykonywanych w celu uzyskania okre

lonego

celu, zwykle w ramach ogranicze

: czasu,

zasobów i kosztu.

Modelowane jest w postaci wykresu sieciowego

wykresu sieciowego

(sieci zale

ci, sieci czynno

ci).

Sie

czynno

ci to graf skierowany spójny

graf skierowany spójny

acykliczny

acykliczny,, opisany ilo

ciowo;

opisany ilo

ciowo; graf, który ma jeden

wierzchołek pocz

tkowy i jeden wierzchołek

cowy.

Przedsięwzięcie

ID,2013/2014

2014-01-10

Podstawowe pojęcia

Graf to struktura składaj

ca si

z w

złów

(wierzchołków) wzajemnie poł

czonych za pomoc

kraw

dzi (łuków).

Grafy dzielimy na grafy skierowane i nieskierowane.

Graf

Graf nieskierowany

Graf skierowany

ID,2013/2014

Podstawowe pojęcia

Graf jest spójny, je

li ka

de dwa wierzchołki

na poł

czy

cie

Spójność grafu

Graf niespójny

Graf spójny

ID,2013/2014

2014-01-10

Podstawowe pojęcia

Cykl to do droga zamkni

ta, czyli taka, która

czy si

w pocz

tkowym wierzchołku drogi w

grafie.

Graf nie zawieraj

cy cykli nazywamy acyklicznym.

Cykl w grafie

<1,2,4,3,4,1> - cykl
<1,2,4,1> - cykl prosty
<2,2> - p

tla

<1,2,3,1> - cykl

ID,2013/2014

Podstawowe pojęcia

Graf, w którym ka

dej kraw

dzi (ka

demu łukowi)

jest przyporz

dkowana okre

lona warto

ść

liczbowa. Warto

ść

ta niesie ze sob

okre

lon

informacj

np. o odległo

ci, czasie, koszcie itp.

Graf ważony

ID,2013/2014

2014-01-10

Podstawowe pojęcia

Elementy składowe przedsi

wzi

cia: zdarzenia i

zdarzenia i

czynno

ci.

Kraw

dzie sieci reprezentuj

czynno

ci,

wierzchołki za

zdarzenia.

Sieć czynności

ID,2013/2014

Oznaczenie

symboliczne

Planowanie

sieciowe

Teoria grafów

czynno

ść

łuk, kraw

zdarzenie

wierzchołek

Podstawowe pojęcia

Odwzorowuj

wykonywanie dowolnego zadania

stkowego.

procesem trwaj

cym w czasie. Proces ten

procesem trwaj

cym w czasie. Proces ten

"zu

ywa„ nie tylko czas, ale równie

rodki,

"zu

ywa„ nie tylko czas, ale równie

rodki,

poci

ga koszty zwi

zane z jego realizacj

poci

ga koszty zwi

zane z jego realizacj

, itp.

Obrazem graficznym czynno

ci jest strzałka

(łuk). Kierunek strzałki wskazuje kierunek
przebiegu czynno

ci w czasie (kolejno

ść

ich

wykonywania):

Czynności

A=19

ID,2013/2014

2014-01-10

Podstawowe pojęcia

Wprowadzane do sieci w celu zaznaczenia
kolejno

ci wyst

powania innych czynno

ci.

Nie zu

ywaj

czasu (ich czas trwania jest równy

zeru) ani

rodków.

Obrazem graficznym czynno

ci pozornej jest

strzałka przerywana:

Czynności pozorne (fikcyjne)

ID,2013/2014

Podstawowe pojęcia

Czynno

ść

charakteryzuje para wska

ników i-j,

gdzie i jest numerem zdarzenia, w którym
czynno

ść

rozpoczyna, a j – numerem

zdarzenia w którym czynno

ść

czy.

g czynno

ci to kolejno, nast

puj

ce po sobie

czynno

ci, dla których zdarzenie ko

cowe pewnej

czynno

ci jest jednocze

nie zdarzeniem

pocz

tkowym dla czynno

ci nast

pnej.

Czynności

Czynności –

– cd

cd..

ID,2013/2014

2014-01-10

Podstawowe pojęcia

Osi

gni

cie stanu zaawansowania pracy przy

realizacji projektu.

Moment rozpocz

cia lub zako

czenia (jednej lub

cej) czynno

ci.

Nie pochłania

adnych kosztów i nie jest rozło

one

w czasie.

Zdarzenia przedstawia si

graficznie za pomoc

figur geometrycznych np. kół, prostok

tów.

Zdarzenie

ID,2013/2014

Podstawowe pojęcia

de ze zdarze

ma w sieci swoj

etykiet

–

numer

numer. Numeracja zdarze

powinna by

„rosn

ca”, tj.

e dla ka

dej czynno

rozpoczynaj

cej si

w zdarzeniu o numerze i a

cym w zdarzeniu o numerze j zachodzi i<j.

Zdarzenie zaszło

Zdarzenie zaszło je

eli zako

czone zostały

wszystkie czynno

ci, dla których to zdarzenie jest

zdarzeniem ko

cowym.

Zdarzenie

Zdarzenie -- cd

cd..

ID,2013/2014

2014-01-10

Podstawowe pojęcia

Zdarzenie pocz

tkowe

Zdarzenie pocz

tkowe - zdarzenie, które nie jest

cem

adnej czynno

ci.

Zdarzenie ko

cowe

Zdarzenie ko

cowe - zdarzenie, które nie jest

pocz

tkiem

adnej czynno

ci.

W modelu sieciowym wyst

puje jeden wierzchołek

jeden wierzchołek

(zdarzenie) pocz

tkowy i jeden wierzchołek

(zdarzenie) pocz

tkowy i jeden wierzchołek

cowy.

Zdarzenie

Zdarzenie -- cd

cd..

ID,2013/2014

Zdarzenie pocz

tkowe nie ma czynno

poprzedzaj

cych

Zdarzenie ko

cowe nie ma czynno

nast

puj

cych po nich

Zasady konstruowania sieci czynności

ID,2013/2014

2014-01-10

Wykres sieciowy mo

e kilka ko

cowych zdarze

wówczas ł

czy si

je czynno

ciami pozornymi w

jedno zdarzenie ko

cowe.

Zasady konstruowania sieci czynności

ID,2013/2014

Dane zdarzenie nie mo

e nast

, dopóki nie

zako

wszystkie czynno

ci prowadz

ce do

niego i warunkuj

ce zaj

cie tego zdarzenia.

adna kolejna czynno

ść

nie mo

e si

rozpocz

ąć

dopóki nie zaistnieje zdarzenie ko

ce czynno

poprzedzaj

ce.

Wektory (łuki) czynno

ci powinny by

skierowane z

lewej strony do prawej

Zasady konstruowania sieci czynności

ID,2013/2014

2014-01-10

Wykres sieciowy nie
mo

e mie

obiegów

zamkni

tych (cyklu), tj.

tli ł

cych

dwukrotnie te same
zdarzenia.

Strzałki obrazuj

czynno

ci nie mog

przecina

Zasady konstruowania sieci czynności

ID,2013/2014

Dwa zdarzenia mog

poł

czone tylko jedn

czynno

. Je

eli kilka czynno

ci wykonywanych

jest równolegle pomi

dzy dwoma zdarzeniami to

nale

y wprowadzi

czynno

ci pozorne.

Zasady konstruowania sieci czynności

ID,2013/2014

2014-01-10

Zdarzenia i czynno

ci powinny by

odpowiednio

uporz

dkowane, tzn. ka

dy poprzednik ma mie

mniejszy numer lub wcze

niejsz

liter

nast

pnika (zatem numeruj

c zdarzenia nale

zwraca

uwag

na to, by zdarzenie wcze

niejsze

miało mniejszy numer i < j). Wymóg ten wyklucza
wyst

pienie cyklu (tzn. sytuacji, gdy wychodz

c z

jednego wierzchołka i poruszaj

c si

kraw

dziach, mo

na do tego samego wierzchołka

wróci

Zasady konstruowania sieci czynności

ID,2013/2014

Etapy tworzenia wykresu sieciowego

Ustalenie listy czynno

ci wchodz

cych w skład

przedsi

wzi

cia,

Ustalenie zdarzenia pocz

tkowego i ko

cowego

przedsi

wzi

cia,

Okre

lenie kolejno

ci wykonywania czynno

ci.

Numeracja w

złów w sieci.

ID,2013/2014

2014-01-10

Przykład 1

Firma produkuj

ca sprz

t RTV zamierza

urz

dzi

wystaw

w celu wypromowania firmy

na rynku.

ID,2013/2014

Przykład 1

A –

–

wybór lokalizacji wystawy,

B –

–

przygotowanie eksponatów,

C –

–

przygotowanie terenu wystawy,

D –

–

przygotowanie stoisk,

E –

–

dostawa eksponatów,

F –

–

przygotowanie obsługi stoisk (ustalenie składu

osobowego i szkolenie),

G –

–

urz

dzenie stoisk wystawowych,

H –

–

otwarcie wystawy.

1. Ustalenie listy czynności

ID,2013/2014

2014-01-10

Przykład 1

2. Ustalenie zdarzenia początkowego i końcowego

przedsięwzięcia

Zdarzeniem pocz

tkowym jest …

„podj

cie decyzji o urz

dzeniu wystawy”,

a zdarzeniem ko

cowym …

„otwarcie wystawy”.

ID,2013/2014

Przykład 1

Dla ka

dej czynno

ci nale

y ustali

czynno

ci poprzedzaj

czynno

ci poprzedzaj

ce, czyli te, które

powinny by

zako

czone przed rozpocz

ciem

danej czynno

ci;

czynno

ci równoległe

czynno

ci równoległe, tzn. te, które mog

wykonywane jednocze

nie z czynno

rozpatrywan

;

czynno

ci nast

puj

czynno

ci nast

puj

ce, tzn. te, które powinny

rozpocz

ąć

po zako

czeniu rozpatrywanej

czynno

ci.

3. Określenie kolejności wykonywania czynności

ID,2013/2014

2014-01-10

Przykład 1

A –

–

wybór lokalizacji wystawy

B –

–

przygotowanie

eksponatów

C –

–

przygotowanie terenu

wystawy

D –

–

przygotowanie stoisk

E –

–

dostawa eksponatów

F –

–

przygotowanie obsługi

stoisk

G –

–

urz

dzenie stoisk

wystawowych

H –

–

otwarcie wystawy

3. Określenie kolejności wykonywania czynności

Czynno

ci bezpo

rednio:

poprzedzaj

nast

puj

A
B
C
D
E
F

G
H

-
-

A
C
B
A

E, D

F, G

C, F

E
D

G
G
H
H

ID,2013/2014

Przykład 1

Sieć czynności

ID,2013/2014

2014-01-10

Przykład 1

Zdarzenia i czynno

ci powinny by

odpowiednio

uporz

dkowane, tzn. ka

dy poprzednik ma mie

mniejszy numer lub wcze

niejsz

liter

nast

pnika (zatem numeruj

c zdarzenia nale

zwraca

uwag

na to, by zdarzenie wcze

niejsze

miało mniejszy numer i < j). Wymóg ten wyklucza
wyst

pienie cyklu (tzn. sytuacji, gdy wychodz

c z

jednego wierzchołka i poruszaj

c si

kraw

dziach, mo

na do tego samego wierzchołka

wróci

4. Numeracja węzłów w sieci

ID,2013/2014

Przykład 1

4. Numeracja węzłów w sieci

ID,2013/2014

2014-01-10

Przykład 2

Firma X planuje wprowadzenie nowego
produktu na rynek. Przedsi

wzi

cie składa

z czynno

ci dotycz

cych sfery

projektowania produkcji, jak równie

działa

zwi

zanych z badaniem rynku.

ID,2013/2014

Przykład 2

A --

Nabycie surowców na prototypy

B --

Produkcja prototypów i ich ocena

C --

Badanie rynku

D --

Analiza kosztów (bez pakowania)

E --

Decyzje o podj

ciu produkcji

F --

Nabycie surowców do produkcji

G --

Produkcja

H --

Wybór opakowania

I --

Nabycie opakowa

J --

Pakowanie

K --

Reklama i zbieranie zamówie

L --

Wysyłka do sklepów

1. Ustalenie listy czynności

ID,2013/2014

2014-01-10

Przykład 2

2. Ustalenie zdarzenia początkowego i końcowego

przedsięwzięcia

Zdarzeniem pocz

tkowym jest …

„pojawienie si

pomysłu na nowy wyrób”,

a zdarzeniem ko

cowym

… „dystrybucja wyrobów”.

ID,2013/2014

Przykład 2

A --

Nabycie surowców na prototypy

Produkcja prototypów i ich ocena

C --

Badanie rynku

D --

Analiza kosztów produkcji

E --

Decyzje o podj

ciu produkcji

F --

Nabycie surowców do produkcji

G --

Produkcja

H --

Wybór opakowania

I --

Nabycie opakowa

J –

–

Pakowanie

K --

Reklama i zbieranie zamówie

L --

Wysyłka do sklepów

3. Określenie kolejności wykonywania czynności

Czynno

ci bezpo

rednio:

poprzedzaj

nast

puj

A
B
C
D
E
F

G
H

B,C

D
E

B,C
H,E

G,I

J,K

D,H
D,H

F,I,K

J
L
L

ID,2013/2014

2014-01-10

Przykład 2

Sieć czynności

ID,2013/2014

Przykład 2

4. Numeracja węzłów w sieci

ID,2013/2014

2014-01-10

Metoda CPM - ścieżki krytycznej
(z ang. Critical Path Method)

ID,2013/2014

Informacje ogólne

Deterministyczna analiza czasowa przedsi

wzi

cia

Metoda ta pozwala na wyznaczenie
najwcze

niejszego mo

liwego terminu

zako

czenia przedsi

wzi

cia, gdy znane s

czasy

trwania

trwania oraz relacje kolejno

ci wykonania

relacje kolejno

ci wykonania

poszczególnych zada

wchodz

cych w skład tego

przedsi

wzi

cia. Relacje kolejno

ci najcz

ęś

ciej s

odwzorowywane przy pomocy sieci powi

lub

poprzez okre

lenie poprzedników (nast

pników)

dla ka

dego zadania.

Metoda CPM

ID,2013/2014

2014-01-10

Interpretacja sieciowa terminów

gdzie:

i - numer zdarzenia (i=1,2,…)

j - numer zdarzenia (j=2,3…)

- najwcze

niejszy mo

liwy moment zaistnienia zdarzenia i

- najwcze

niejszy mo

liwy moment zaistnienia zdarzenia j

- najpó

niejszy dopuszczalny moment zaistnienia zdarzenia i

– najpó

niejszy dopuszczalny moment zaistnienia zdarzenia j

- zapas czasu dla zdarzenia i

- zapas czasu dla zdarzenia j

<i,j> – czynno

ść

o zdarzeniu pocz

tkowym i oraz ko

cowym j

– czas trwania czynno

ci <i,j>

Metoda CPM

ID,2013/2014

Etapy analizy

Etap 1.

Etap 1. Wyznaczanie najwcze

niejszych mo

liwych

Wyznaczanie najwcze

niejszych mo

liwych

momentów zaistnienia zdarze

(t)

momentów zaistnienia zdarze

(t)

dla zdarzenia pocz

tkowego

dla zdarzenia nast

pnego (j)

w przypadku, gdy do zdarzenia dochodzi wi

cej ni

jedna

czynno

ść

, najwcze

niejszy mo

liwy moment zaistnienia

tego zdarzenia jest równy maksymalnej z tak obliczonych
wielko

ci, czyli:

Dla zdarzenia ko

cowego

}

{

max

∑

,...

Metoda CPM

ID,2013/2014

2014-01-10

Etapy analizy

Etap 2. Wyznaczanie najpó

niejszych dopuszczalnych

Wyznaczanie najpó

niejszych dopuszczalnych

momentów zaistnienia zdarze

(T)

momentów zaistnienia zdarze

(T)

dla zdarzenia ko

cowego

dla zdarzenia poprzedniego (i)

w przypadku gdy do zdarzenia dochodzi wi

cej ni

jedna

czynno

ść

, wybieramy wielko

ść

najmniejsz

, czyli

}

{

min

−

,...

−

UWAGA:

Najwcze

niejszy i najpó

niejszy termin zdarzenia ko

cowego

sobie równe, gdy

zdarzenie to nie ma nast

pników

Metoda CPM

ID,2013/2014

Etapy analizy

Etap 3. Wyznaczanie luzów (zapasów) czasowych dla

Wyznaczanie luzów (zapasów) czasowych dla

zdarze

(L)

zdarze

(L)

−

Metoda CPM

UWAGA:

Luz czasowy zdarzenia wskazuje, o ile jednostek czasu mo

na opó

termin

zaistnienia danego zdarzenia bez wpływu na termin zako

czenia realizacji projektu

ID,2013/2014

2014-01-10

Etapy analizy

Etap 4.

Etap 4. Wyznaczanie zapasów czasu dla czynno

Wyznaczanie zapasów czasu dla czynno

zapas całkowity

Metoda CPM

−

UWAGA:

Zapas czasu dla czynno

ci stanowi rezerw

czasu, który mo

e by

wykorzystany dodatkowo na wykonanie danej czynno

ci, bez wpływu

na termin realizacji projektu.

ID,2013/2014

Etapy analizy

Etap 4. Wyznaczanie zapasów czasu dla czynno

Wyznaczanie zapasów czasu dla czynno

zapas swobodny

Metoda CPM

−

UWAGA:

Wykorzystanie tego zapasu nie ma wpływu na zapasy zwi

zane z

czynno

ciami nale

żą

cymi do danej

cie

ki.

ID,2013/2014

2014-01-10

Etapy analizy

Etap 4. Wyznaczanie zapasów czasu dla czynno

Wyznaczanie zapasów czasu dla czynno

zapas warunkowy

Metoda CPM

−

UWAGA:

Ta rezerwa czasu mo

e by

wykorzystana bez zmniejszenia zapasów

poprzednich, okre

lonych dla danej

cie

ki.

ID,2013/2014

Etapy analizy

Etap 5. Wyznaczenie harmonogramu przedsi

wzi

cia

Wyznaczenie harmonogramu przedsi

wzi

cia

Metoda CPM

Najwcześniejszy możliwy termin rozpoczęcia czynności <i,j>

Najpóźniejszy dopuszczalny termin rozpoczęcia czynności <i,j>

Najwcześniejszy możliwy termin zakończenia czynności <i,j>

Najpóźniejszy dopuszczalny termin zakończenia czynności <i,j>

NWR

NPR

−

NWZ

NPZ

ID,2013/2014

2014-01-10

Etapy analizy

Etap 6. Okre

lanie

cie

ki (drogi) krytycznej przedsi

wzi

cia

Metoda CPM

cie

ka krytyczna

cie

ka krytyczna to nieprzerwany ci

g czynno

ci, prowadz

od zdarzenia pocz

tkowego do zdarzenia ko

cowego,

posiadaj

cy najdłu

szy czas trwania. Warunkuje najkrótszy czas

wykonania przedsi

wzi

cia.

Składa si

z czynno

ci krytycznych

czynno

ci krytycznych, w przypadku realizacji

których zapas czasu jest równy zeru

równy zeru.

Zdarzenia

Zdarzenia le

żą

ce na

cie

ce krytycznej maj

równie

zerowe

równie

zerowe

zapasy czasu.

zapasy czasu.
Przekroczenie terminu zako

czenia którejkolwiek czynno

krytycznej powoduje opó

nienie wykonania całego projektu.

W sieciach mo

e wyst

powa

cej ni

jedna

cie

e wyst

powa

cej ni

jedna

cie

krytyczna

krytyczna.

ID,2013/2014

Przykład 2

Czynno

ść

Opis czynno

Czynno

ci bezpo

rednio:

Czas trwania

(dni)

poprzedzaj

nast

puj

A
B
C
D
E
F

G
H

Nabycie surowców na prototypy
Produkcja prototypów i ich ocena
Badanie rynku
Analiza kosztów produkcji
Decyzje o podj

ciu produkcji

Nabycie surowców do produkcji
Produkcja
Wybór opakowania
Nabycie opakowa

Pakowanie
Reklama i zbieranie zamówie

Wysyłka do sklepów

B,C

D
E

B,C
H,E

G,I

J,K

D,H
D,H

F,I,K

J
L
L

20
35
10

15
30

20
10

ID,2013/2014

2014-01-10

C=35

A=5

B=20

D=10

E=1

F=15

H=2

Etap 1. Wyznaczenie najwcześniejszych możliwych momentów

Etap 1. Wyznaczenie najwcześniejszych możliwych momentów
zaistnienia zdarzeń (t)

zaistnienia zdarzeń (t)

Przykład 2

G=30

I=10

J=5

K=20

106

L=10

Najkrótszy czas realizacji całego przedsięwzięcia 106 dni

ID,2013/2014

C=35

A=5

B=20

D=10

E=1

F=15

H=2

Etap 1. Wyznaczenie najpóźniejszych dopuszczalnych

Etap 1. Wyznaczenie najpóźniejszych dopuszczalnych
momentów zaistnienia zdarzeń (T)

momentów zaistnienia zdarzeń (T)

Przykład 2

G=30

I=10

J=5

K=20

106

L=10

106

ID,2013/2014

2014-01-10

Etap 3. Wyznaczenie zapasów czasowych dla zdarzeń (L)

Przykład 2

C=35

A=5

B=20

D=10

E=1

F=15

H=2

G=30

I=10

J=5

K=20

106

L=10

106

ID,2013/2014

Etap 4. Wyznaczenie

Etap 4. Wyznaczenie całkowitych

całkowitych zapasów czasu dla czynności

zapasów czasu dla czynności

Etap 5. Wyznaczenie harmonogramu przedsięwzięcia

Przykład 2

Czynność

<i,j>

NWR

NPR

NWZ

NPZ

<1,2>

<2,3>

<1,3>

<3,4>

<4,5>

<5,6>

<6,8>

<3,7>

<7,8>

<8,9>

<5,9>

<9,10>

106

ID,2013/2014

2014-01-10

Etap 5. Wyznaczenie harmonogramu przedsięwzięcia

Etap 5. Wyznaczenie harmonogramu przedsięwzięcia –

– wykres

wykres

Gantta (wg NWR

ij)

Przykład 2

100

105

110

ID,2013/2014

Etap 5. Wyznaczenie harmonogramu przedsięwzięcia

Etap 5. Wyznaczenie harmonogramu przedsięwzięcia –

– wykres

wykres

Gantta

Przykład 2

100

105

110

5,7

ID,2013/2014

2014-01-10

Przykład 2

C=35

A=5

B=20

D=10

E=1

F=15

H=2

G=30

I=10

J=5

K=20

106

L=10

106

Etap 6. Wyznaczenie ścieżki krytycznej przedsięwzięcia

Najkrótszy czas realizacji całego przedsięwzięcia wyznaczony został przez ścieżkę:

C-D-E-F-G-J-L

ID,2013/2014

Metoda CPM - COST

ID,2013/2014

2014-01-10

Cech

metody CPM-COST jest rozpatrywanie

liwo

ci skrócenia czasu trwania

poszczególnych czynno

ci, przy czym ka

skrócenie poci

ga za sob

odpowiednie koszty.

Celem jest wyznaczenie takiego terminu
zako

czenia przedsi

wzi

cia przy którym całkowity

koszt realizacji jest minimalny.

W CPM-COST zakłada si

e zale

ść

pomi

dzy

kosztem skrócenia danej czynno

ci a liczb

jednostek czasu, o które zostanie ona skrócona ma
charakter liniowy.

Informacje ogólne

Metoda

Metoda CPM

CPM--COST

COST

ID,2013/2014

– normalny czas trwania czynno

ci, któremu

odpowiadaj

najni

sze koszty wykonania czynno

(koszt normalny)

- czas graniczny, najkrótszy mo

liwy ze wzgl

dów

technicznych i technologicznych czas wykonania
czynno

ci przy koszcie granicznym k

Interpretacja określeń i oznaczeń

Metoda

Metoda CPM

CPM--COST

COST

ID,2013/2014

2014-01-10

Interpretacja określeń i oznaczeń

Metoda

Metoda CPM

CPM--COST

COST

S -

określa wzrost kosztu związany ze

skróceniem czasu trwania czynności o

jednostkę.

−

S –

redni gradient

kosztu

ID,2013/2014

Etapy analizy

Etap 1. Wyznaczenie terminu ko

cowego i

cie

krytycznej na sieci zale

ci (na podstawie

normalnych czasów trwania czynno

ci).

Etap 2. Zestawienie czynno

ci krytycznych i

obliczenie dla nich gradientów kosztów S.

Etap 3. Wyeliminowanie z zestawienia tych
czynno

ci krytycznych, dla których

redni gradient

kosztów nie istnieje, tzn.

Metoda

Metoda CPM

CPM--COST

COST

ID,2013/2014

2014-01-10

Etapy analizy

Etap 4. Proces skracania rozpoczynamy od
czynno

ci krytycznej o najni

szym gradiencie

kosztów S.

Etap 5. Przy skracaniu czasu trwania czynno

nale

y stara

skróci

jej czas o jak najwi

ksz

najwi

ksz

liczb

jednostek czasu. Wyst

puj

tu jednak dwa

ograniczenia:

czas graniczny danej czynno

ci t

pojawienie si

nowej

cie

ki krytycznej.

Metoda

Metoda CPM

CPM--COST

COST

ID,2013/2014

Etapy analizy

Nowa

cie

ka pojawi si

wtedy, gdy zaniknie zapas

czasu w ci

gu czynno

ci niekrytycznych.

Etap 6. Przy istnieniu dwóch lub wi

cej

cie

krytycznych w sieci nale

y skraca

czas o t

sam

wielko

ść

na wszystkich równoległych

cie

kach

krytycznych.

Etap 7. Najkrótszy termin wykonania
przedsi

wzi

cia uzyskuje si

, gdy wszystkie

czynno

ci le

żą

ce na którejkolwiek

cie

krytycznej osi

czasy graniczne t

. Dalsze

skracanie czasu wykonania przedsi

wzi

cia jest

niemo

liwe.

Metoda

Metoda CPM

CPM--COST

COST

ID,2013/2014

2014-01-10

Etapy analizy

Etap 8. Koszty przyspieszenia na ka

dym etapie

oblicza si

jako iloczyn gradientu kosztów (S) dla

danej czynno

ci i liczby jednostek czasu, o które

dana czynno

ść

krytyczna została skrócona.

czne koszty przyspieszenia s

sum

kosztów

poniesionych na poszczególnych etapach.

Metoda

Metoda CPM

CPM--COST

COST

ID,2013/2014

Przykład 3

Przedsi

wzi

cie składa si

z 9 czynno

ci, dla których podano

czasy normalne (t

), czasy graniczne (t

) w dniach oraz koszty

normalne (K

) i koszty graniczne (K

) w zł.

Wykre

siatk

zale

ci oraz wyznaczy

najwcze

niejszy mo

liwy termin

zako

czenia przedsi

wzi

cia.

Do jakiego terminu mo

na skróci

czas realizacji przedsi

wzi

cia? Jakie z tym

ążą

koszty?

i-j

1-2
1-3
1-4
2-7
3-5
4-6
5-8
6-8
7-8

10
12

6
4

15
10

7
6
4

6
2

6
5

100
120
250
330
400
230
300
400
300

250
240
290
390
400
260
400
440
390

50
20
10
30

15
20
10
30

ID,2013/2014

2014-01-10

Etap 1.

Etap 1. Wyznaczenie terminu końcowego i ścieżki krytycznej na

Wyznaczenie terminu końcowego i ścieżki krytycznej na

sieci zależności

Przykład 3

Najkrótszy czas realizacji całego przedsięwzięcia wynosi 33 dni
i wyznaczony jest przez ścieżkę:

1-3-5-8

i-j

1-2 3
1-3 0
1-4 11
2-7 3
3-5 0
4-6 11
5-8 0
6-8 11
7-8 3

ID,2013/2014

Etap 2

Etap 2. Zestawienie czynności krytycznych i obliczenie dla nich

. Zestawienie czynności krytycznych i obliczenie dla nich

gradientów kosztów

gradientów kosztów S.

Przykład 3

i-j

1-2
1-3
1-4
2-7
3-5
4-6
5-8
6-8
7-8

10
12

6
4

15
10

7
6
4

6
2

6
5

100
120
250
330
400
230
300
400
300

250
240
290
390
400
260
400
440
390

10
30

Etap 3

Etap 3. Wyeliminowanie z zestawienia tych czynności krytycznych,

. Wyeliminowanie z zestawienia tych czynności krytycznych,

dla których średni gradient kosztów nie istnieje

ID,2013/2014

2014-01-10

Etap 4

Etap 4. Proces skracania rozpoczynamy od czynności

. Proces skracania rozpoczynamy od czynności

krytycznej o najniższym gradiencie kosztów S

Przykład 3

1 faza skracania

i-j

1-2
1-3
1-4
2-7
3-5
4-6
5-8
6-8
7-8

10
12

6
4

15
10

7
6
4

6
2

6
5

100
120
250
330
400
230
300
400
300

250
240
290
390
400
260
400
440
390

10
30

ID,2013/2014

Przykład 3

1 faza skracania

Etap 5

Etap 5. Skracanie czasu trwania czynności krytycznych

. Skracanie czasu trwania czynności krytycznych

Koszt przyspieszenia czynności <1-3>: 20·3=60 jedn. pieniężnych

Dwie

cie

ki krytyczne: 1-3-5-8 oraz 1-2-7-8

ID,2013/2014

2014-01-10

Etap 4

Etap 4. Proces skracania rozpoczynamy od czynności

. Proces skracania rozpoczynamy od czynności

krytycznej o najniższym gradiencie kosztów S

2 faza skracania

i-j

1-2
1-3
1-4
2-7
3-5
4-6
5-8
6-8
7-8

10
12

6
4

15
10

7
6
4

6
2

6
5

100
120
250
330
400
230
300
400
300

250
240
290
390
400
260
400
440
390

Przykład 3

Dwie

cie

ki krytyczne: 1-3-5-8 oraz 1-2-7-8

ID,2013/2014

Etap 6

Etap 6. Dwie ścieżki krytyczne

. Dwie ścieżki krytyczne –

– skracamy czas o tą samą

skracamy czas o tą samą

wielkość na wszystkich równoległych ścieżkach krytycznych

Przykład 3

2 faza skracania

Koszt przyspieszenia czynności <1-3>: 20·3=60 jedn. pieniężnych
Koszt przyspieszenia czynności <4-8>: 20·5=100 jedn. pieniężnych

Koszt przyspieszenia czynności <2-7>: 30·2=60 jedn. pieniężnych
Koszt przyspieszenia czynności <7-8>: 30·3=90 jedn. pieniężnych
Koszt przyspieszenia czynności <1-2>: 50·3=150 jedn. pieniężnych

460 jedn.pieni

ęż

nych

Trzy

cie

ki krytyczne: 1-3-

5-8, 1-2-7-8 i 1-4-6-8

ID,2013/2014

2014-01-10

Wszystkie czynno

ci le

żą

ce na

cie

ce krytycznej

1-3-5-8 oraz 1-2-7-8 osi

ły czasy graniczne t

Dalsze skracanie czasu wykonania
przedsi

wzi

cia jest niemo

liwe.

Najkrótszy termin wykonania projektu to … 22 dni.

Etap 7

Etap 7. Najkrótszy termin wykonania programu sieciowego

. Najkrótszy termin wykonania programu sieciowego

Przykład 3

ID,2013/2014

czne koszty przyspieszenia s

sum

kosztów

poniesionych na poszczególnych etapach.
Skrócenie czasu trwania przedsi

wzi

cia z 33 do

22 dni kosztuje 520 jedn. pieni

ęż

nych.

Etap 8

Etap 8. Łączne koszty przyspieszenia

. Łączne koszty przyspieszenia

Przykład 3

ID,2013/2014