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
3
5
8
9
10
11

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

5
8
9
10
11. 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