27479 img350 (5)

5. Programowanie sieciowe

Metody programowania sieciowego wprowadzono w końcu lat pięćdziesiątych, a ich wielość i różnorodność sprawiła, że dzisiaj należy dokonać ich klasyfikacji. Ze względu na strukturę logiczną metody sieciowe można podzielić na metody sieciowe o strukturze logicznej zdeterminowanej (sieci typu DAN¹) i o strukturze logicznej stochastycznej (sieci typu GAN²). W myśl tak przyjętego podziału będziemy rozważać modele sieciowe przedsięwzięć.

Przez £rzedsięwzi^de rozumie się zorganizowane działanie ludzkie zmierzające do osiągnięcia określonego celu, zawarte w skończonym przedziale czasu - z wyróżnionym początkiem i końcem - oraz zrealizowane przez skończoną liczbę osób, środków technicznych, energii, materiałów, środków finansowych i informacji.

Do określenia struktury przedsięwzięcia niezbędne jest zdefiniowanie jego podstawowych elementów składowych, tj. zdarzenia i czynności. Zdarzenie to zjawisko fizyczne, zlokalizowane za pomocą punktu geometrycznego w czasie i przestrzeni, a w modelu sieciowym oznacza osiągnięcie stanu zaawansowania prac przy realizacji przedsięwzięcia. Zdarzenia przedstawiamy graficznie za pomocą kółek lub innych figur geometrycznych, np. rombu. Czynnośćto dowolnie wyodrębniona część przedsięwzięcia charakteryzująca się trwaniem, terminem rozpoczęcia, zakończenia oraz ilością zaangażowanych do jej wykonania środków. Obrazem graficznym czynności są strzałki (wektory). Kierunek strzałki wskazuje kierunek przebiegu czynności w czasie. Zależności pomiędzy zdarzeniami i czynnościami określają strukturę logiczną modelu sieciowego, która może być zdeterminowana, jeśli w trakcie realizacji przedsięwzięcia wszystkie czynności przedstawione w sieci są zrealizowane, lub stochastyczna, jeśli w trakcie realizacji przedsięwzięcia bierze udział tylko część czynności przedstawiona w sieci, z określonym, większym od zera prawdopodobieństwem.

5.1. Modele sieciowe o zdeterminowanej strukturze logicznej

Do najbardziej znanych metod analizy sieciowej DAN należą CPM (Critical Path Method), jej rozszerzenie o analizę czasowo-kosztową CPM-COST, PERT (Program Evaluation and Review Techniąue) oraz PERT-COST. W rozważanej klasie metod sieciowych optymalizacja przedsięwzięcia polega na:

a)    wyodrębnieniu i zestawieniu wchodzących w jego skład czynności (zadań cząstkowych);

b)    ocenie parametrów poszczególnych czynności i zdarzeń (czasu, nakładów lub innych parametrów addytywnych);

c)    konstrukcji sieci zależności technologicznych;

d)    wyznaczeniu podstawowych charakterystyk sieci dotyczących zarówno poszczególnych czynności i zdarzeń, jak też całego projektu;

e)    wyznaczeniu tzw. ścieżki krytycznej.

Warto zauważyć, że przy konstrukcji sieci obowiązują pewne reguły. Nie każdy podział sieci na czynności składowe (zadania cząstkowe) jest dopuszczalny z punktu widzenia planowania i kierowania realizacją przedsięwzięcia.

A zatem należy ustalić taki stopień szczegółowości podziału przedsięwzięcia na zadania cząstkowe, aby jego struktura logiczna określająca wymagany porządek realizacji czynności dała się przedstawić w postaci grafu nie zawierającego ścieżek cyklicznych, pętli itp. W praktyce zaleca się, ze względu na przejrzystość konstruowanej sieci, aby w sieci nie było skrzyżowań łuków. Wymaga się ponadto, aby w modelu sieciowym przedsięwzięcia:

a)    istniał dokładnie jeden wierzchołek (zdarzenie) początkowy i jeden wierzchołek końcowy (postulat ten można spełnić wprowadzając tzw. czynności pozorne);

b)    wierzchołki i łuki (zdarzenia i czynności) były odpowiednio uporządkowane, tzn. każdy poprzednik ma mieć mniejszy numer lub wcześniejszą literę od następnika (w praktyce żądanie to wyklucza występowanie ścieżek cyklicznych i pętli);

c)    dwa zdarzenia były połączone tylko jedną czynnością; jeżeli kilka czynności wykonywanych równolegle poprzedza jedną, należy wprowadzić czynności pozorne;

d)    każda czynność może być zrealizowana tylko jeden raz z prawdopodobieństwem równym jeden podczas wykonywania przedsięwzięcia.

5.2. Metoda CPM

Przykład 30. Rozważmy przykład zamontowania silnika do samochodu. Kolejność wykonywania poszczególnych czynności, czasy ich trwania oraz opis przedstawiono w tabl. 152. Przeprowadzić analizę sieciową tak sformułowanego przedsięwzięcia, przyjmując jako kryterium optymalności mini-

157

1

   DAN - Deterministic Analysis Network.

2

   GAN - Generalized Analysis Network,