PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2003 | nr 4 | 185--208
Tytuł artykułu

Computing Efficiently Floats of all Activities in a Series-Parallel Network with Duration Intervals

Warianty tytułu
Efektywne obliczanie zapasów wszystkich czynności w sieci szeregowo-równoległej z przedziałowymi czasami wykonania czynności
Języki publikacji
EN
Abstrakty
W artykule rozważa się problem obliczania przedziałów możliwych wartości zapasów (całkowitych zapasów) czynności w sieciach, w których czasy wykonania czynności są zadane nieprecyzyjnie za pomocą liczb przedziałowych. Rozważany problem jest silnie NP-trudny w klasie dowolnych sieci i pozostaje NP-trudny w klasie sieci planarnych. Fargier i inni pokazali, że problem jest wielomianowy w klasie sieci szeregowo-równoległych. Proponuje się algorytm oparty na redukcjach grafowych obliczający w czasie O(n) przedział możliwych wartości zapasów dla jednej czynności w sieci szeregowo-równoległej. Algorytm oparty jest na redukcjach szeregowych i równoległych zachowujących zapasy czynności. Może on być również zastosowany w celu uproszczenia problemu obliczania przedziałów możliwych wartości zapasów dla jednej czynności w dowolnych sieciach, który jest NP-trudny. Algorytm ten ma taką samą złożoność jak algorytm zaproponowany przez Fargier i innych. Zastosowanie algorytmu zaproponowanego w pracy albo algorytmu zaproponowanego przez Fargier i innych w celu obliczenia przedziałów możliwych wartości zapasów dla wszystkich czynności w sieci wymaga zatem czasu O(n2). W pracy poprawiono ten wynik, proponując algorytm o liniowej złożoności pamięciowej obliczający w czasie O(n log n) przedziały możliwych wartości zapasów dla wszystkich czynności w sieciach szeregowo-równoległych. Zastosowano w nim struktury danych oparte na dynamicznych drzewach wyrażeń (Cohen i Tamassia) i dynamicznych drzewach (Sleator i Tarjan).
EN
The paper deals with the problem of computing intervals of possible values of floats for all activities in a series-parallel network with duration intervals. An O(n) time algorithm, using graph reductions, for computing the interval of possible values of floats for a single activity and an algorithm for computing the intervals for all activities in the network that runs O (n log n) time and requires a linear space for a data structure are presented.
Rocznik
Numer
Strony
185--208
Opis fizyczny
Twórcy
Bibliografia
  • [1] BENT S.W., SLEATOR D.D., TARJAN R.E., Biased Search Trees, SIAM Journal on Computing, 14(1985), 545-568.
  • [2] COHEN R.F., TAMASSIA R., Dynamic Expression Trees, Algorithmica, 13 (1995), 245-265.
  • [3] CHANAS S., KAMBUROWSKI J., The use of fuzzy variables in PERT, Fuzzy Sets and Systems, 5 (1981), 1-19.
  • [4] CHANAS S., DUBOIS D., ZIELIŃSKI P., On the sure criticality of task in activity networks with imprecise durations, IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics, 32 (2002), 393-407.
  • [5] CHANAS S., ZIELIŃSKI P., Critical path analysis in the network with fuzzy activity times, Fuzzy Sets and Systems, 122(2001), 195-204.
  • [6] CHANAS S., ZIELlŃSKl P., The computational complexity of the criticality problems in a network with interval activity times, European Journal of Operational Research, 136 (3), (2002), 541-550.
  • [7] CHANAS S., ZIELIŃSKI P., On the hardness of evaluating criticality of activities in a planar network with duration intervals. Operations Research Letters, 31 (2003), 53-59.
  • [8] DUBOIS D., FARGIER H., GALVAGNON V., On latest starting times and floats in activity networks with ill-known durations, European Journal of Operational Research, 147 (2003), 266-280.
  • [9] FARGIER H., GALVAGNON V., DUBOIS D., Fuzzy PERT in series-parallel graphs, 9-th IEEE Int. Conf. on Fuzzy Systems, San Antonio, TX, 2000, 717-722.
  • [10] HAPKE M., JASZKIEWICZ A., SŁOWIŃSKI R., Fuzzy project scheduling system for software development, Fuzzy Sets and Systems, 67 (1994), 101—117.
  • [11] KELLEY J.E., WALKER M.R.., Critical path planning and scheduling, [in:] Proceedings of the Eastern Joint Computational Conference, 16(1959), 160-172.
  • [12] LOOSTMA F.A., Fuzzy Logic for Planning and Decision-Making, Dordrecht: Kluwer Acad. Publ., 1997.
  • [13] PRADE H., Using fuzzy sets theory in a scheduling problem: a case study, Fuzzy Sets and Systems, 2(1979), 153-165.
  • [14] ROMMELFANGER H., Network analysis and information flow in fuzzy environment, Fuzzy Sets and Systems, 67 (1994), 119-128.
  • [15] SLEATOR D.D., TARJAN R.E., A Data Structure for Dynamic Trees, Journal of Computer and System Science, 26 (1983), 362-391.
  • [16] VALDES J., TARJAN R.E., LAWLER E.L., The Recognition of Series Parallel Digraphs, SIAM Journal on Computing, 11 (1982), 298-313.
  • [17] ZIELIŃSKI P., Latest starting times and floats of activities in networks with uncertain durations, Proceedings of an International Conference in Fuzzy Logic and Technology, Eusflat 2003, 10-12 September 2003, Zittau, Germany, 586-591.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000000121959

Zgłoszenie zostało wysłane

Zgłoszenie zostało wysłane

Musisz być zalogowany aby pisać komentarze.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.