Temat zajęć: Programowanie sieciowe.

Cele zajęć: po zakończeniu zajęć student powinien:

Znać:

• Pojęcia: droga krytyczna, zdarzenie krytyczne, czynność krytyczna.

Umieć:

• Rozwiązać zadanie dot. programowania sieciowego

Metody programowania sieciowego to techniki planowania przedsięwzięć, zapewniające sprawny przebieg ich wykonania. Wykorzystanie metod sieciowych w planowaniu przedsięwzięć składa się z kilku etapów:

1. sporządzenie listy czynności, ustalenie zależności pomiędzy nimi (kolejności ich wykonania) oraz czasów ich trwania. W zależności od tego jak określone są czasy trwania czynności wyróżnia się: metody sieciowe deterministyczne (czasy trwania czynności są określone jednoznacznie-jedną liczbą; CPM, CPM- COST naliza czasowo kosztowa) oraz stochastyczne (czasy trwania czynności określone są z pewnym prawdopodobieństwem; PERT, PERT- COST).

2. Stworzenie wykresu sieciowego (czynności- część przedsięwzięcia

określonym czasie trwania i zużywaniu środków trwałych,

wyróżnić można jeszcze czynność pozorną - ich czas trwania jest równy 0 i nie zużywane są środki, przedstawiają jedynie zależności między zdarzeniami i zdarzenia- to moment rozpoczęcia lub zakończenia jednej lub więcej czynności).

3. Wyznaczenie podstawowych charakterystyk sieci - najwcześniejszych możliwych i najpóźniejszych dopuszczalnych momentów zaistnienia zdarzenia zapasów czasu dla zdarzeń i czynności).

4. Wyznaczenie terminu końcowego realizacji całego przedsięwzięcia

Droga krytyczna- ścieżka krytyczna, to ciąg zdarzeń i czynności krytycznych w sieci zależności PERT, najdłuższa droga w sieci, czynności i zdarzenia leżące na niej mają zawsze 0 zapasy czasu. Ścieżek krytycznych w sieci może być > niż 1.

Zdarzenie krytyczne- zdarzenia mające zerowy luz czasowy

Czynność krytyczna- czynność nie posiadająca zapasów czasowych

METODA CPM

Stosując tą metodę dla każdego zdarzenia w sieci wyznacza się:

• Najwcześniejszy moment zaistnienia zdarzenia t

• Najpóźniejszy dopuszczalny moment zaistnienia zdarzenia T

• Zapas czasu L=T-t

i-to numer zdarzenia

Zadanie - przykład

Mając dane o czasie trwania poszczególnych czynności wyznacz ścieżkę krytyczną oraz termin końcowy produkcji gwoździ. Jakie zmiany wywoła skrócenie czynności 2-4 do 2 dni?

Czynność i-j	Czas (dni) tij
1-2 1-3 2-4 2-5 3-5 4-5 4-6 5-6	8 12 10 4 5 7 10 5

Ścieżka krytyczna 1-2-4-5-6

Tk= 30 dni

Rozwiązanie

Jakie zmiany wywoła skrócenie czynności 2-4 do 2 dni?

Powstaną dwie ścieżki krytyczne: 1-3-5-6 oraz 1-2-4-5-6 Tk= 22 dni

Zad. 2

Mając dane o czasie trwania poszczególnych czynności wyznacz ścieżkę krytyczną oraz termin końcowy realizacji przedsięwzięcia.

Czynność i-j	Czas (min) tij
1-2 1-3 1-4 2-5 2-7 3-5 3-6 4-5 5-6 5-7 6-7 6-8 7-8	2 5 4 3 5 6 2 10 8 2 6 5 4

1. jakie zmiany wywoła skrócenie czynności 4-5 do 4 minut?

Zadania do domu

Zad. 1

Mając dane o czasie trwania poszczególnych czynności wyznacz ścieżkę krytyczną oraz najkrótszy czas trwania produkcji ołówków. Jakie zmiany spowoduje skrócenie czasu trwania czynności 4-5 do 6 minut?

Czynność i-j	Czas (min) tij
1-2 1-4 2-3 3-6 4-5 5-6	8 10 6 12 15 10

Odp. Tk=35, ścieżka krytyczna 1-4-5-6; Tk=26, ścieżka krytyczna 1-2-3-6 lub 1-4-5-6

Zad. 2

Mając dane o czasie trwania poszczególnych czynności wyznacz ścieżkę krytyczną oraz najkrótszy czas trwania przedsięwzięcia. Jakie zmiany spowoduje dodanie czynności 2-3 ,
która trwa 15 godzin?

Czynność i-j	Czas (godz) tij
1-2 1-3 2-4 2-5 3-5 4-5 4-6 5-6	8 12 10 4 5 7 10 5

Odp. Tk=30, ścieżka 1-2-4-5-6; Tk=33 godz. Ścieżka 1-2-3-5-6

Zad. 3

Przy produkcji chleba wyróżnić 8 zdarzeń oraz 11 czynności. Czynności oraz czas ich trwania zawiera tabela. Wyznacz ścieżkę krytyczną oraz najkrótszy czas produkcji.

Czynność i-j	Czas (min) tij	Czynność i-j	Czas (min) tij
1-2 1-3 2-3 2-5 3-4 3-5	6 10 6 12 5 8	4-6 5-6 5-7 6-7 7-8	8 7 8 6 7

Odp. Tk=40, ścieżka 1-2-3-5-6-7-8

Zad. 4

Pewne przedsięwzięcie, na które składa się 18 czynności o łącznym czasie ich trwania 200 godzin, zaplanować tak, aby trwało jak najkrócej. Czasy trwania czynności oraz ich następstwo w czasie przedstawia tabela.

Czynność i-j	Czas (min) tij	Czynność i-j	Czas (min) tij
1-2 1-3 1-4 1-5 2-5 2-6 3-4 3-5 3-7	5 10 3 12 10 23 5 3 16	3-8 4-8 5-6 5-7 6-10 7-9 7-10 8-9 9-10	9 7 9 12 20 13 18 15 10

1. zbuduj siatkę czynności tego przedsięwzięcia.

2. jaki jest najkrótszy czas wykonania całego przedsięwzięcia, wyznacz ścieżkę krytyczną.

Odp. Tk=50 , ścieżka krytyczna 1-2-5-7-9-10

Zad. 5

Aby wyprodukować jogurty i zapakować je na paletę musisz wykonać poszczególne czynności, których czas trwania przedstawia poniższa tabela.

Czynność i-j	Czas (min) tij	Czynność i-j	Czas (min) tij
1-2 1-3 1-7 2-4 2-5 3-6 3-8 4-5 4-12 5-9 6-7 6-10	25 30 50 13 12 19 18 6 8 15 6 27	6-11 7-9 7-10 8-11 9-12 10-14 11-14 12-13 12-15 13-14 14-15	19 20 30 20 20 40 6 10 80 12 50

Wyznacz ścieżkę krytyczną oraz najwcześniejszy termin zakończenia przedsięwzięcia. Jak wpłynie n termin końcowy:

1. wydłużenie czasu czynności 12-13 o 10 dni?

2. Opóźnienie momentu rozpoczęcia czynności 1-7 o 7 dni?

3. Skrócenie czasu czynności 12-15 o 10 dni?

4. Skrócenie czasu trwania czynności 7-10 o 10 dni?

Odp. Tk= 175; ścieżki krytyczne 1-3-6-7-9-12-15 oraz 1-3-7-10-14-15; a)nie wpłynie, bo czynność na 8 dni zapasu; b)opóźni Tk o 2 dni, ścieżki krytyczne będą wyglądały wtedy 1-7-9-12-15 oraz 1-7-10-14-15; c)pozostanie jedna ścieżka krytyczna 1-3-7-10-14-15; d) pozostanie jedna ścieżka krytyczna 1-3-7-9-12-15

Zad. 6

Narysuj wykres sieciowy przedsięwzięcia składającego się z czynności od A do N, jeśli czasy trwania poszczególnych czynności wynoszą odpowiednio 10, 6, 4, 2,4,4,7,3,5,5,4,3,4,1, wiedząc, że:

Przed czynnością:	Należy wykonać czynność:
A B C D E F G H I J K L M N	- A A A B C C C D,C E,F H,I J,G,K J,L,K M,K

Oblicz najkrótszy czas realizacji przedsięwzięcia. Wskaż czynności krytyczne.

Odp. A-B-E-J-M-N. Tk=30

Zad. 7

Sporządzić wykres sieciowy procesu produkcji kabli miedzianych, składającego się
z czynności A-N, jeśli:

Przed zdarzeniem:	Musi zajść zdarzenie:
A B C D E F G H I J K L Ł M N	----- E D E --- A F,M C C D,B H,J G,J,K L,K E,F I,Ł

Przyjmując, że czasy trwania czynności A-N wynoszą kolejno: A-F 2; E-M 4; E-B 3; E-D 8; F-G 10; F-M 12; M-G 5; B-J 4; D-J 7; D-C 6; G-L 1, J-L 2; J-K 9; C-H 8; C-J 3,; L-Ł 11; K-L 10; K-Ł 8; H-K 3; Ł-N 2; I-N 5 dni wyznaczyć najwcześniejszy możliwy termin zakończenia przedsięwzięcia oraz ścieżkę krytyczną. Która z czynności ma największy zapas czasu?

Czy termin końcowy zmieni się jeśli:

a)czynność I-N rozpocznie się o 10 dni później,

b)czas trwania czynności J-K można będzie skrócić o 3 dni?

Odp. Ścieżka krytyczna E-M-G-J-K-Ł-N; Tk= 60, największy zapas ma czynność A-25 dni.

a)czynność I ma 20 dni zapasu, Tk będzie bez zmian

b)ścieżka krytyczna E-D-C-H-K-Ł-M, Tk skróci się o 2 dni.

Zad. 8

Narysuj sieć zależności dla produkcji płytek podłogowych, składającej się z czynności A-Ł, jeśli:

• Czynność A poprzedza czynności B,C,D,E, które mogą być wykonywane równocześnie;

• Czynność F może rozpocząć się po zakończeniu czynności B;

• Czynność G może rozpocząć się po zakończeniu czynności C oraz F;

• Przed czynnością H należy wykonać czynność G i L;

• Po zakończeniu czynności E równocześnie można wykonać czynność I oraz J;

• Czynność L można rozpocząć po zakończeniu czynności G,D,I oraz J;

• Przed rozpoczęciem czynności Ł należy zakończyć czynności H oraz K.

Czasy trwania czynności wynoszą kolejno: 5,15,2,10,18,3,8,9,4,19, 4,10,12,4,10,4

Wyznacz najwcześniejszy możliwy moment realizacji przedsięwzięcia oraz ścieżkę krytyczną. Odpowiedz, czy uda się skrócić termin końcowy jeżeli:

• Czas trwania czynności I - L będzie można skrócić o 2 dni;

• Czas trwania czynności G-L dzięki zaangażowaniu dodatkowych środków zostanie skrócony o 4 dni.

Odp. Tk=58 dni, A-B-F-G-K-Ł oraz A-E-I-K-Ł; nie uda się, bo istnieją dwie równoległe ścieżki krytyczne.

Zad. 9

W zakładzie samochodowym planuje się zamontować nowy silnik do samochodu. Czynności składające się na to przedsięwzięcie oraz czas ich trwania przedstawia tabela. Określ termin końcowy realizacji przedsięwzięcia oraz ścieżkę krytyczną.

Czynność	Opis czynności	Czas trwania tij	Czynności poprzedzające
a	Zaczepić silnik hakami uchwytu	3	-
b	Podnieść silnik do góry	2	a
c	Opuścić silnik na poduszki zawieszenia silnika	4	b
d	Podnieść skrzynię biegów wraz tylnią poprzeczką	5	a
e	Zamocować poprzeczkę do podłogi	7	c, d
f	Przekręcić wspornik rury wydechowej do skrzynki biegów i do rury wydechowej	10	c, d
g	Połączyć linkę napędu licznika km do przekładni napędu prędkościomierza	5	e, f
h	Przekręcić linkę wyłącznika sprzęgła do widełek	7	e, f
i	Przekręcić przewód masy i przyłączyć przewody elektryczne do wyłącznika świateł cofania	8	g ,h
j	Podnieść wał napędowy	3	i
k	Przyłączyć drążek zmiany biegów do dźwigni	8	j
l	Zamontować przewód doprowadzający paliwo do pompy	3	j
m	Przyłączyć przewód serwera podciśnieniowego	2	j
n	Przyłączyć przewody gumowe łączące silnik z nagrzewnicą	7	k, l, m
o	Założyć chłodnicę na wspornik w nadwoziu	5	c, d
p	Zamocować chłodnicę u góry do szkieletu nadwozia	10	o
r	Przyłączyć przewody gumowe do termostatu i pompy wodnej	10	p
s	Przyłączyć wszystkie przewody elektryczne	17	i
t	Napełnić układ chłodzenia płynem niezamarzającym	5	r
u	Sprawdzić czy kurki spustowe są dobrze zakręcone	1	t
w	Założyć filtr powietrza na gaźnik	30	n, u
x	Dokonać regulacji silnika	10	s, w
v	Sprawdzić poprawność instalacji elektrycznej	8	s, w
y	Sprawdzić poprawność montażu	15	v, x
z	Wykonać test silnika	23	y

Odp. Tk=130minutl ścieżka krytyczna a-b-c-f-h-i-j-h-n-w-x-y-z

Zad. 10

Naprawa silnika elektrycznego składa się z następujących czynności:

Czynność	Opis czynności	Czas trwania tij
a	Przeniesienie silnika na stanowisko demontażu	3
b	Demontaż silnika	10
c	Kontrola zużycia części A	5
d	Kontrola zużycia części B	10
e	Kontrola zużycia części C	8
f	Kontrola zużycia części D	12
g	Naprawa i konserwacja części A	2,8,14
h	Naprawa i konserwacja części B	5,7,9
i	Naprawa i konserwacja części C	4,5,18
j	Naprawa i konserwacja części D	6,8,18
k	Montaż części silnika A,B,C,D	12
l	Oczekiwanie na transport	2,6,10
ł	Przeniesienie do magazynu	8

Wiadomo, że czynność A musi poprzedzać B. Czynność C,D,E oraz F mogą być wykonane równolegle , jednak czynność G musi być poprzedzona czynnością C; czynność H czynnością D, czynność I czynnością E, a czynność J czynnością F. Czynność K może nastąpić po wykonaniu wszystkich poprzednich czynności. Czynność L następuje po czynności K, a przed czynnością Ł. Podaj czas wykonania naprawy silnika oraz ścieżkę krytyczną.

Odp. Tk= 62, ścieżka krytyczna A-B-F-J-K-L-Ł

METODA PERT

Dla każdej czynności dane są trzy oceny czasu jej trwania:

a- czas optymistyczny (czas trwania czynności w najbardziej sprzyjających warunkach)

b- czas pesymistyczny (czas trwania czynności w najmniej sprzyjających warunkach)

m - czas modalny, najbardziej prawdopodobny (czas, który najczęściej występuje

przy wielokrotnym powtarzaniu czynności).

Spełniona jest relacja a≤m≤b

Na podstawie tych trzech ocen oblicza się oczekiwany czas trwania

czynności te wg wzoru:

Oraz wariancję czasu oczekiwanego, która określa spodziewane odchylenie rzeczywistego czasu trwania czynności od wyznaczonego czasu oczekiwanego.

Wariancja terminu wykonania

(suma wariancji czynności krytycznych)

Odchylenie terminu wykonania

Znając oczekiwany termin wykonania oraz jego wariancję można także obliczyć prawdopodobieństwo, że przedsięwzięcie będzie zakończone w pewnym narzuconym z góry terminie td. aby to prawdopodobieństwo określić oblicza się statystykę daną wzorem:

Gdzie, td- termin narzucony z góry; tw- oczekiwany termin wykonania przedsięwzięcia (najwcześniejszy możliwy termin zdarzenia końcowego), a σ2TW- wariancja terminu wykonania.

Z tablic dystrybuanty rozkładu normalnego odczytujemy prawdopodobieństwo dotrzymania narzuconego z góry terminu.

P{td Ⴃ tw}=F(x)

Gdy wartość prawdopodobieństwa znajduje się w granicach od 0,25 do 0,6

to dotrzymanie terminu jest realne.

Gdy F(x)≤0,25 to istnieje znikoma szansa na dotrzymanie terminu narzuconego.

Jeśli F(x)>0,6 to istnieją niewykorzystane moce wytwórcze (nadmiar maszyn, zasobów itp.).

F(x) <0,25;0,6> wtedy i tylko wtedy gdy x <-0,6744;0,2533>

Zadanie - przykład

Czynności związane z dostarczeniem do klienta wózków widłowych charakteryzują następujące dane umieszczone w tabeli:

Czynność	Czasy
		a	m	b
1-2	3	4	5
1-3	3	3	3
2-4	7	9	17
2-5	10	12	14
3-6	1	5	9
3-7	5	10	15
4-9	6	12	18
5-8	4	6	14
5-9	1	1	7
6-8	4	4	4
7-8	10	15	20
7-10	5	5	11
8-9	5	8	11
9-10	1	5	9

Znajdź najkrótszy czas realizacji dostawy. Czy termin 40 dni jest możliwy do realizacji? Podaj jak zmieni się czas trwania przedsięwzięcia, gdy czas czynności 7-10 oszacowano na 10,13,16?

Rozwiązanie

1. Czas końcowy Tk= …………

2. ścieżka krytyczna ………………………………….

3. Czy dotrzymanie terminu 40 dni jest realne?

1. Oblicz wariancję czynności znajdujących się na ścieżce krytycznej

σ²_…-….=

σ²_…-….=

σ²_…-….=

σ²_…-….=

σ²_…-….=

2. Oblicz wariancje terminu wykonania (suma wariancji czynności krytycznych)

σ²_TW=

3. Oblicz odchylenie terminu wykonania

σ_TW=

4. Oblicz prawdopodobieństwo, że przedsięwzięcie będzie wykonane w narzuconym terminie

X= ……………………………..

5. Odczytaj wartość F(x) z tablic rozkładu normalnego i udziel odpowiedzi na zadane pytanie.

F(x)=

Odp. ……………………………………………………………………………………….

Zad. 2

Aby złożyć rower musisz wykonać kolejno 15 czynności. Czynności te charakteryzują następujące dane przedstawione w tabeli:

Czynność	Czasy
		a	m	b
1-2	2	5	8
2-3	8	9	16
2-4	6	7	8
3-4	3	6	9
3-5	9	11	13
3-6	4	6	8
4-7	2	2	2
4-8	5	9	19
5-6	0	0	0
5-8	5	6	13
6-8	10	11	12
6-9	2	3	10
7-8	7	7	7
7-9	7	9	11
8-9	2	4	12

Określ najkrótszy czas złożenia roweru. Jakie jest prawdopodobieństwo dotrzymania terminu dyrektywnego 40 dni, a jakie 43 dni?

Odp. Czas najkrótszy 42 dni; dla 40 dni- P{t_k≤40}= 0,2090 termin mało realny; dla 43 dni P{t_k≤43}= 0,4 termin możliwy do dotrzymania.

Zad. 3

Twoja firma produkuje piłeczki do Squash. Posiadając pełne dane o czasach trwania czynności tego procesu produkcyjnego, określ czas trwania całego przedsięwzięcia oraz odpowiedz na pytanie: czy termin 77 dni jest realny?

Czynność	Czasy
		a	M	b
1-2	4	8	24
1-3	3	3	3
1-4	3	5	7
2-5	3	6	9
2-6	15	20	37
3-4	4	6	20
3-7	10	15	20
3-8	4	5	6
4-5	3	6	9
4-8	20	30	46
5-6	20	21	22
6-8	14	17	26
7-8	30	30	36
7-9	25	25	25
8-9	4	4	4
9-10	6	6	6
9-11	7	10	13
9-12	14	15	16
10-12	10	12	14
11-12	3	11	13

Odp. 1-3-4-5-6-8-9-11-12; φ²_Tw= 144/9; φ_Tw=4 dni

Ćw. 4 Planowanie i sterowanie produkcją

KONSPEKT

11

30

30

6

0

0

0

1

10

8

10

0

8

8

2

0

18

0

25

18

7

5

4

25

Najdłuższy czas (największy)

Najkrótszy czas

4

0

3

12

20

8

5

12

5

tej

4

3

10

……

…..

……

…..

……

……

…..

……

……

……

…….

1

0

0

0

2

…..

…..

…..

3

…..

…..

……

4

….

….

…..

5

….

….

…..

6

….

….

…..

7

….

….

…..

8

….

….

…..

9

….

….

…..

10

41

41.

…..

---