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

• Autorzy: Paweł Zieliński

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

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.

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).

Słowa kluczowe

EN

Inventory control model; Algorithms; Graphs

PL

Model sterowania zapasami; Algorytmy; Grafy

• Czasopismo: Badania Operacyjne i Decyzje
• Rocznik: 2003
• Numer: nr 4
• Strony: 185--208

Twórcy

autor

Paweł Zieliński

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.