Hubert Skrzypulec
Zabrze 05.12.2008r.
ZiIP 3.2
POLITECHNIKA ŚLĄSKA W GLIWICACH
WYDZIAŁ ORGANIZACJI I ZARZĄDZANIA
Katedra Informatyki i Ekonometrii
BADANIA OPERACYJNE
Projekt nr 5
Programowanie sieciowe
Metoda CPM
Hubert Skrzypulec
Zabrze 05.12.2008r.
ZiIP 3.2
POLITECHNIKA ŚLĄSKA W GLIWICACH
WYDZIAŁ ORGANIZACJI I ZARZĄDZANIA
Katedra Informatyki i Ekonometrii
BADANIA OPERACYJNE
Projekt nr 5
Programowanie sieciowe
Metoda CPM
Strona 2 z 6
Treść zadania
W domu państwa Kowalskich zepsuł się telewizor. Jako, że jest on jeszcze na gwarancji
telewizor został zaniesiony do autoryzowanego serwisu. W trakcie sprawdzania i
eliminowania usterek serwisant musi wykonać szereg zabiegów, które muszą być
przeprowadzane w określonej kolejności. Spis czynności, wraz z uwzględnieniem kolejności
oraz czasu ich trwania przedstawia tabela 1. Na jej podstawie należy ustalić czas realizacji
naprawy, narysować diagram sieciowy, wyznaczyć ścieżkę krytyczną oraz narysować wykres
Gantta.
Tabela 1
Symbol
Opis czynności
Czynności
poprzedzające
Czas trwania w
minutach
A
Przeniesienie telewizora na stanowisko naprawcze
-
4
B
Demontaż telewizora
A
5
C
Sprawdzenie zużycia kineskopu
B
10
D
Sprawdzenie zużycia dekodera koloru
B
14
E
Sprawdzenie zużycia detektora
B
8
F
Sprawdzenie zużycia układu sterowania
B
6
G
Naprawa i konserwacja kineskopu
C
8
H
Naprawa i konserwacja dekodera koloru
D
10
I
Naprawa i konserwacja detektora
E
12
J
Naprawa i konserwacja układu sterowania
F
9
K
Montaż telewizora
G, H, I, J
7
L
Oczekiwanie na transport
K
2
M
Przeniesienie do magazynu
L
3
Na podstawie przedstawionych w tabeli czynności tworzę diagram sieciowy.
1
2
3
4
5
6
8
7
9
10
11
A
B
C
D
E
F
J
I
G
H
K
L
M
Strona 3 z 6
Tabela 2 przedstawia czasy trwania poszczególnych czynności
Tabela 2
Czynności
t
ij
1 – 2
4
2 – 3
5
3 – 4
10
3 – 5
14
3 – 6
8
3 – 7
6
4 – 8
8
5 – 8
10
6 – 8
12
7 – 8
9
8 – 9
7
9 – 10
2
10 – 11
3
Zadanie rozwiązuję metodą CPM (Critical Path Method) – ścieżki krytycznej. Ścieżka
krytyczna jest to droga, której czas przejścia jest najdłuższy. Czynności i zdarzenia leżące na
niej mają zerowe zapasy czasu.
Oznaczenia
– czas trwania czynności z i do j
– najwcześniejszy możliwy moment rozpoczęcia czynności t
ij
– najpóźniejszy dopuszczalny moment rozpoczęcia czynności t
ij
– najwcześniejszy możliwy moment zakończenia czynności t
ij
– najpóźniejszy dopuszczalny moment zakończenia czynności t
ij
– całkowity zapas czasowy
– swobodny zapas czasowy
– warunkowy zapas czasowy
t
ij
w
j
j
p
j
p
i
w
i
i
Strona 4 z 6
Zależności
Rozwiązanie
Wyrysowuję siatkę czynności, oszacowuję zapasy czasowe, czas trwania naprawy wraz z
wyznaczeniem ścieżki krytycznej.
Czas wykonania naprawy to 45 minut. Ścieżka krytyczna jest sekwencją czynności:
1
2 35891011
Dla takiej sekwencji czynności zapas czasowy wynosi 0. Zgodnie z praktyką
rozwiązywania zagadnień sieciowych jest to nasze rozwiązanie optymalne.
Przygotowuję dane do wyznaczenia wykresu Gantta. Wszystkie oznaczenia zostały
wyjaśnione na stronie trzeciej.
1
2
3
4
5
6
7
8
9
10
11
0
0
0
4
4
0
9
9
0
19
25
6
23
23
0
17
21
4
15
24
9
33
33
0
40
40
0
42
42
0
45
45
0
4
5
10
14
8
6
9
12
10
8
7
2
3
Strona 5 z 6
Tabela 3
Czynności
1 – 2
4
0
4
0
4
0
4
0
4
0
0
0
2 – 3
5
4
9
4
9
4
9
4
9
0
0
0
3 – 4
10
9
19
9
25
9
25
15
19
6
0
6
3 – 5
14
9
23
9
23
9
23
9
23
0
0
0
3 – 6
8
9
17
9
21
9
21
13
17
4
0
4
3 – 7
6
9
15
9
24
9
24
18
15
9
0
9
4 – 8
8
19
33
25
33
19
33
25
27
6
6
6
5 – 8
10
23
33
23
33
23
33
23
33
0
0
0
6 – 8
12
17
33
21
33
17
33
21
29
4
4
0
7 – 8
9
15
33
24
33
15
33
24
24
9
9
0
8 – 9
7
33
40
33
40
33
40
33
40
0
0
0
9 – 10
2
40
42
40
42
40
42
40
42
0
0
0
10 – 11
3
42
45
42
45
42
45
42
45
0
0
0
Rysunek 1 Wykres Gantta
Na wykresie uzyskaliśmy dokładnie taki sam rezultat jak w przypadku rozwiązania
metodą sieci czynności. Ścieżkę krytyczną tworzy sekwencja czynności: 1
2
3
5891011. Czas tego przedsięwzięcia wynosi 45 minut.
Strona 6 z 6
Tabela 4 Rozwiązanie tego zagadnienia za pomocą dodatku Solver w arkuszu kalkulacyjnym Microsoft Excel
Microsoft Excel 12.0 Raport wyników
Komórka celu (Min)
Komórka
Nazwa
Wartość początkowa
Wartość końcowa
$B$12
f celu
0
45
Komórki decyzyjne
Komórka
Nazwa
Wartość początkowa
Wartość końcowa
$B$1
t1
0
0
$B$2
t2
0
4
$B$3
t3
0
9
$B$4
t4
0
25
$B$5
t5
0
23
$B$6
t6
0
21
$B$7
t7
0
15
$B$8
t8
0
33
$B$9
t9
0
40
$B$10
t10
0
42
$B$11
t11
0
45
Warunki ograniczające
Komórka
Nazwa
Wartość komórki
formuła
Status
Luz
$B$14
t2-t1
4
$B$14>=4
Wiążące
0
$B$15
t3-t2
5
$B$15>=5
Wiążące
0
$B$16
t4-t3
16
$B$16>=10
Niewiążące
6
$B$17
t5-t3
14
$B$17>=14
Wiążące
0
$B$18
t6-t3
12
$B$18>=8
Niewiążące
4
$B$19
t7-t3
6
$B$19>=6
Wiążące
0
$B$20
t8-t4
8
$B$20>=8
Wiążące
0
$B$21
t8-t5
10
$B$21>=10
Wiążące
0
$B$22
t8-t6
12
$B$22>=12
Wiążące
0
$B$23
t8-t7
18
$B$23>=9
Niewiążące
9
$B$24
t9-t8
7
$B$24>=7
Wiążące
0
$B$25
t10-t9
2
$B$25>=2
Wiążące
0
$B$26
t11-t10
3
$B$26>=3
Wiążące
0
$B$1
t1
0
$B$1>=0
Wiążące
0
$B$2
t2
4
$B$2>=0
Niewiążące
4
$B$3
t3
9
$B$3>=0
Niewiążące
9
$B$4
t4
25
$B$4>=0
Niewiążące
25
$B$5
t5
23
$B$5>=0
Niewiążące
23
$B$6
t6
21
$B$6>=0
Niewiążące
21
$B$7
t7
15
$B$7>=0
Niewiążące
15
$B$8
t8
33
$B$8>=0
Niewiążące
33
$B$9
t9
40
$B$9>=0
Niewiążące
40
$B$10
t10
42
$B$10>=0
Niewiążące
42
$B$11
t11
45
$B$11>=0
Niewiążące
45