Efektywne obliczanie zapasow wszystkich czynnosci w sieci szeregowo-rownoleglejz przedzialowymi czasami wykonania czynnosci

W artykule rozwaza sie problem obliczania przedzialow mozliwych wartosci zapasow (calkowitych zapasow) czynnosci w sieciach, w ktorych czasy wykonania czynnosci sa zadane nieprecyzyjnie za pomoca liczb przedzialowych. Rozwazany problem jest silnie NP-trudny w klasie dowolnych sieci i pozostaje NP-trudny w klasie sieci planarnych. Fargier i inni pokazali, ze problem jest wielomianowy w klasie sieci szeregowo-rownoleglych. Proponuje sie algorytm oparty na redukcjach grafowych obliczajacy w czasie O (n) przedzial mozliwych wartosci zapasow dla jednej czynnosci w sieci szeregowo-rownoleglej. Algorytm oparty jest na redukcjach szeregowych i rownoleglych zachowujacych zapasy czynnosci. Moze on byc rowniez zastosowany w celu uproszczenia problemu obliczania przedzialow mozliwych wartosci zapasow dla jednej czynnosci w dowolnych sieciach, ktory jest NP-trudny. Algorytm ten ma taka sama zlozonosc jak algorytm zaproponowany przez Fargier i innych. Zastosowanie algorytmu zaproponowanego w pracy albo algorytmu zaproponowanego przez Fargier i innych w celu obliczenia przedzialow mozliwych wartosci zapasow dla wszystkich czynnosci w sieci wymaga zatem czasu O (n2). W pracy poprawiono ten wynik, proponujac algorytm o liniowej zlozonosci pamieciowej obliczajacy w czasie O (n log n) przedzialy mozliwych wartosci zapasow dla wszystkich czynnosci w sieciach szeregowo-rownoleglych. Zastosowano w nim struktury danych oparte na dynamicznych drzewach wyrazen (Cohen i Tamassia) i dynamicznych drzewach (Sleator i Tarjan).