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

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

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.

Tabela 2 przedstawia czasy trwania poszczególnych czynności

Tabela

Czynności	tij
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

t_ij – czas trwania czynności z i do j

w_i=t_ij^wp – najwcześniejszy możliwy moment rozpoczęcia czynności t_ij

t_ij^pp  – najpóźniejszy dopuszczalny moment rozpoczęcia czynności t_ij

t_ij^wk – najwcześniejszy możliwy moment zakończenia czynności t_ij

p_j = t_ij^pk – najpóźniejszy dopuszczalny moment zakończenia czynności t_ij

L_ij – całkowity zapas czasowy

${\hat{L}}_{\text{ij}}$ – swobodny zapas czasowy

${\tilde{L}}_{\text{ij}}$ – warunkowy zapas czasowy

Zależności

L_ij = p_j − w_i − t_ij

$${\hat{L}}_{\text{ij}} = w_{j} - w_{i} - t_{\text{ij}}$$

$${\tilde{L}}_{\text{ij}} = p_{j} - p_{i} - t_{\text{ij}}$$

t_ij^pp = p_j − t_ij

t_ij^wk = w_i + t_ij

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.

Tabela

Czynności	tij	wi	wj	pi	pj	tij^wp	tij^pk	tij^pp	tij^wk	Lij	$${\hat{\mathbf{L}}}_{\mathbf{\text{ij}}}$$	$${\tilde{\mathbf{L}}}_{\mathbf{\text{ij}}}$$
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 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 35891011. Czas tego przedsięwzięcia wynosi 45 minut.

Tabela 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
	$B$12	f celu	0
Komórki decyzyjne
	Komórka	Nazwa	Wartość początkowa
	$B$1	t1	0
	$B$2	t2	0
	$B$3	t3	0
	$B$4	t4	0
	$B$5	t5	0
	$B$6	t6	0
	$B$7	t7	0
	$B$8	t8	0
	$B$9	t9	0
	$B$10	t10	0
	$B$11	t11	0
Warunki ograniczające
	Komórka	Nazwa	Wartość komórki
	$B$14	t2-t1	4
	$B$15	t3-t2	5
	$B$16	t4-t3	16
	$B$17	t5-t3	14
	$B$18	t6-t3	12
	$B$19	t7-t3	6
	$B$20	t8-t4	8
	$B$21	t8-t5	10
	$B$22	t8-t6	12
	$B$23	t8-t7	18
	$B$24	t9-t8	7
	$B$25	t10-t9	2
	$B$26	t11-t10	3
	$B$1	t1	0
	$B$2	t2	4
	$B$3	t3	9
	$B$4	t4	25
	$B$5	t5	23
	$B$6	t6	21
	$B$7	t7	15
	$B$8	t8	33
	$B$9	t9	40
	$B$10	t10	42
	$B$11	t11	45