BazEkon - The Main Library of the Cracow University of Economics

BazEkon home page

Main menu

Author
Zieliński Paweł
Title
Computing Efficiently Floats of all Activities in a Series-Parallel Network with Duration Intervals
Efektywne obliczanie zapasów wszystkich czynności w sieci szeregowo-równoległej z przedziałowymi czasami wykonania czynności
Source
Badania Operacyjne i Decyzje, 2003, nr 4, s. 185-208, bibliogr. 17 poz.
Operations Research and Decisions
Keyword
Model sterowania zapasami, Algorytmy, Grafy
Inventory control model, Algorithms, Graphs
Note
streszcz., summ.
Abstract
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).

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.
Accessibility
The Main Library of the Cracow University of Economics
The Library of Warsaw School of Economics
The Library of University of Economics in Katowice
The Main Library of Poznań University of Economics and Business
The Main Library of the Wroclaw University of Economics
Bibliography
Show
  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.
Cited by
Show
ISSN
1230-1868
Language
eng
Share on Facebook Share on Twitter Share on Google+ Share on Pinterest Share on LinkedIn Wyślij znajomemu