6307877842

'2 5)->M 2J

212 1/1

i    -    identyfikator czynności

k/zit

t, - czas realizacji /-tej czynności

k - identyfikator zasobu potrzebnego do realizacji /'-tej czynności Zk    -    liczba potrzebnych jednostek fc-tego zasobu

Rys. 2.1: Przykładowa sieć typu AON dla projektu z dwoma zasobami

punkty ekstremalne. Kolejne zawężenia w ramach klas odnoszą się do poziomu lokalności minimów (ekstremów). Harmonogramy aktywny i stabilny odnoszą się do punktów minimalnych (ekstremalnych) w całej przestrzeni harmonogramów wykonalnych, natomiast półaktywny (półstabilny) do minimów (ekstremów) lokalnych. Klasy quasi- i pseudo- odnoszą się do harmonogramów, które mogą być uzyskane na drodze globalnego (lokalnego) przesunięcia czynności z zachowaniem kolejności ich wykonywania.

2.3 Sposoby reprezentacji problemu harmonogramowania projektu

Powszechnie stosowane jest reprezentowanie problemu harmonogramowania projektów w formie sieci (grafów). Elmaghraby (1970a,b) przedstawia ogólny przegląd sieci i ich zastosowania m.in. w modelowaniu projektów. Dla potrzeb problemów harmonogramowania projektu stosowane są dwa rodzaje reprezentacji: czynność na węźle (ang. AON - Activity-On-Node) oraz czynność na łuku (ang. AOA - Activity-On-Arć). Sysło, Deo i Kowalik (1995) przyjmują nazewnictwo związane z definicją wierzchołków grafu - sieć typu AON nazywają siecią czynności, natomiast sieć typu AOA nazywają siecią zdarzeń. Do prezentacji rozwiązania problemu harmonogramowania projektów najczęściej stosowaną formą jest wykres Gantt’a. Sieć AON stanowi acykliczny graf skierowany g^aon = (W, K), w którym W oznacza zbiór wierzchołków (węzłów) odpowiadających czynnościom, a K oznacza zbiór łuków, które odpowiadają relacjom kolej-nościowym w modelu. Zwykle do zbioru IV dołączane są dwie czynności odpowiadające rozpoczęciu i zakończeniu projektu (źródło i odpływ). Przykład sieci AON dla problemu RCPS z dwoma zasobami przedstawiono na rys. 2.1.

Sieć AOA stanowi acykliczny graf skierowany G^AOA = (W, K), w którym łuki odpowiadają czynnościom natomiast węzły oznaczają zdarzenia (odpowiadają momentom w których rozpoczynają się i kończą czynności). Odwzorowanie problemu RCPS za pomocą sieci zdarzeń przedstawiono na rys. 2.2. W sieci AOA występują czynności pozorne, czyli takie, które odwzorowują zależności kolejnościowe pomiędzy rzeczywistymi czynnościami. Czynności pozorne nie zużywają czasu, ani zasobów. Na rys. 2.2 czynność pozorna oznaczona została linią przerywaną.

W przypadku problemów harmonogramowania zorientowanych na optymalizację kryteriów czasowych najpowszechniej stosowana jest reprezentacja w postaci sieci AON. Węzły sieci oznaczają wówczas czynności, natomiast łuki oznaczają zależności kolejnościowe pomiędzy czynnościami. Wagi przypisane do łuków oznaczają opóźnienie czasowe w relacji pomiędzy czynnościami. Reprezentacja AON stosowana jest zwyczajowo w komercyjnym oprogramowaniu m. in.: Microsoft Project, Welcom Open Plan, Prima-vera. Reprezentacja w postaci sieci AOA stosowana jest w metodzie CPM¹ (ang. Critical Path Method).

1

Jedna z metod stosowanych w zarządzaniu projektami. Zaprojektowana została w roku 1958 w amerykańskiej firmie chemicznej DuPont, w celu usprawnienia procesów produkcji. Pozwala na graficzną prezentację kolejnych czynności wykonywanych w ramach projektu, z zaznaczeniem szacowanego czasu trwania tych czynności, oraz z zachowaniem ich sekwencji. Obszerne omówienie metody można znaleźć m. in. w (Trocki i in., 2003, Zawadzka, 1997).