6307877841

2.2.1 Klasyfikacja harmonogramów

Klasyfikacja harmonogramów realizacji projektów oparta jest na podziale stosowanym dla ogólnych problemów produkcji (ang. job-shop), który przedstawiają m.in. Conway, Maxwell i Miller (1967), Baker (1974), Bierwirth i Mattfeld (1999), Pawlak (1999). Jednolitą i sformalizowaną klasyfikację dla problemów typu projektowego przedstawiają Sprecher, Kolisch i Drexl (1995). W zależności od zastosowanej procedury budowy harmonogramu (wykorzystującej uszeregowanie zadań) można uzyskać harmonogramy o zróżnicowanych właściwościach:

•    h. niedopuszczalne (ang. infeasible) - zbiór harmonogramów nie spełniający nałożonych ograniczeń kolejnościowych lub dostępności zasobów,

•    h. dopuszczalne (ang. feasible) - zbiór harmonogramów spełniających wszystkie nałożone ograniczenia zarówno dostępności zasobów, jak i kolejności realizacji zadań,

•    h. półaktywne¹ (ang. semiactive) zwane również półzwartytmi (Janiak, 1999) - podzbiór zbioru harmonogramów dopuszczalnych. Zawiera harmonogramy, w których operacje są umieszczane w najwcześniejszych możliwych terminach. Harmonogram dopuszczalny może być przekształcony w pseudoaktywny poprzez przesunięcie lokalne operacji w lewo. Wiest (1964) określa przekształcenie to (ang. local left shift), jako zmianę terminu rozpoczęcia czynności poprzez serię kolejnych przesunięć o jedną jednostkę czasu bez naruszania ograniczeń.

•    h. aktywne (ang. active) - podzbiór zbioru harmonogramów pseudoaktywnych. Zawiera harmonogramy, w których czynności są umieszczone tak, że nie ma możliwości ich wcześniejszego rozpoczęcia bez naruszenia ograniczeń kolejnościowych lub opóźnienia innej czynności. Wiest (1964) określa globalne przesunięcie w lewo jako przesunięcie czynności do najwcześniejszego możliwego terminu wykonania, które nie jest osiągalne na drodze przesunięcia lokalnego.

•    h. bez opóźnień (ang. nondelay) - stanowią podzbiór zbioru harmonogramów aktywnych. Operacje umieszczane w harmonogramie są wybierane ze zbioru operacji możliwych do zaplanowania w danej chwili tzn. tych dla których operacje poprzedzające zostały zakończone i zasoby potrzebne do realizacji są dostępne. W harmonogramie bez opóźnień zasób nie pozostaje wolny jeżeli może być wykorzystany do jakiejkolwiek operacji.

W przypadku problemów harmonogramowania opartych na regularnych kryteriach oceny (patrz p. 2.4) najkorzystniejsze warunki przeszukiwania - z uwagi na najmniejszy rozmiar - daje przestrzeń harmonogramów bez opóźnień. Jednak nie daje ona gwarancji odnalezienia rozwiązania optymalnego. Co najmniej jeden harmonogram optymalny jest aktywny, natomiast żaden ze zbioru harmonogramów optymalnych nie musi być harmonogramem bez opóźnień (Mattfeld, 1995). Przestrzeń harmonogramów bez opóźnień daje jednak lepsze średnie wyniki, pozwalając tym samym na uzyskanie dobrych wyników przy ograniczonym czasie obliczeń (Storer i in., 1992). Storer, Wu i Vaccari (1992) proponują algorytm tworzący harmonogram hybrydowy dla potrzeb ogólnych problemów harmonogramowania, który pozwala na elastyczne zawężenie przeszukiwanej przestrzeni harmonogramów aktywnych (w skrajnym przypadku do zbioru harmonogramów bez opóźnień).

Neumann, Niibel i Schwindt (2000) rozszerzają klasyfikację harmonogramów wykonalnych dostosowując ją do wymagań problemów ze względnymi i bezwzględnymi ograniczeniami czasowymi. Zaproponowany podział uwzględnia również potrzeby optymalizacji ze względu na nieregularne kryteria oceny harmonogramu. W efekcie autorzy wyróżniają osiem rodzajów harmonogramów²: kwaziakty wne (ang. quasiactive), kwazistabilne (ang. ąuasistable), pseudoaktywne (ang. pseudoactive), pseudostabilne (ang. pseudostable), półaktywne (ang. semiactive), półstabilne (ang. semistable), aktywne (ang. active), stabilne (ang. stable). Na nazwę każdej klasy składają się dwa człony. Termin aktywny odnosi się do harmonogramów stanowiących minimalny punkt w przestrzeni rozwiązań, natomiast stabilny odnosi się do tych, które stanowią

1

   w publikacjach polskich autorzy stosują dla terminu semiactwe tłumaczenie pseudoaktywny, które jednak nie będzie zgodne z najnowszą klasyfikacją, w której Neumann, Niibel i Schwindt (2000) rozróżniają dwie odrębnie klasy semiactive oraz pseudoactive

2

   w literaturze krajowej brak jednolitych terminów określających poszczególne klasy. Przedstawione terminy stanowią jedynie próbę przetłumaczenia oryginalnych odpowiedników angielskich, które są powszechnie stosowane.