Efficient computation of project characteristics in a series-parallel activity network with interval durations

  • Paweł Zieliński
Part of the CISM International Centre for Mechanical Sciences book series (CISM, volume 482)


The paper deals with the problems of computing the completion time of a project, floats and the earliest and the latest starting times of activities, and of evaluating criticality of activities in a network with uncertain durations specified as intervals. We show efficient methods for determining these project characteristics in the network having a series-parallel topology.


Completion Time Decomposition Tree Path Tree Dynamic Tree Project Characteristic 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. S. W. Bent, D.D. Sleator and R. E. Tarjan. Biased Search Trees. SIAM Journal on Computing 14:545–568, 1985.zbMATHCrossRefMathSciNetGoogle Scholar
  2. J.J. Buckley. Fuzzy PERT. In G.W. Evans, W. Karwowski and M.R. Wilhelm, editors, Applications of Fuzzy Set Methodologies in Industrial Engineering. Elsevier, Amsterdam-Oxford-New York-Tokyo, 1989, 103–114.Google Scholar
  3. R.F. Cohen and R. Tamassia. Dynamic Expression Trees. Algorithmica 13:245–265, 1995.zbMATHCrossRefMathSciNetGoogle Scholar
  4. S. Chanas and J. Kamburowski. The use of fuzzy variables in PERT. Fuzzy Sets and Systems 5:1–19, 1981.CrossRefMathSciNetGoogle Scholar
  5. S. Chanas, D. Dubois and P. Zieliński. On the sure criticality of tasks in activity networks with imprecise durations. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics 32:393–407, 2002.CrossRefGoogle Scholar
  6. S. Chanas and P. Zieliński. Critical path analysis in the network with fuzzy activity times. Fuzzy Sets and Systems 122:195–204, 2001.zbMATHCrossRefMathSciNetGoogle Scholar
  7. S. Chanas and P. Zieliński. The computational complexity of the criticality problems in a network with interval activity times. European Journal of Operational Research 136:541–550, 2002.zbMATHCrossRefMathSciNetGoogle Scholar
  8. S. Chanas and P. Zieliński. On the hardness of evaluating criticality of activities in a planar network with duration intervals. Operations Research Letters 31:53–59, 2003.zbMATHCrossRefMathSciNetGoogle Scholar
  9. D. Dubois, H. Fargier and V. Galvagnon. On latest starting times and floats in activity networks with ill-known durations. European Journal of Operational Research 147:266–280, 2003.zbMATHCrossRefMathSciNetGoogle Scholar
  10. H. Fargier, V. Galvagnon and D. Dubois. Fuzzy PERT in series-parallel graphs. In 9-th IEEE Int. Conf on Fuzzy Systems, San Antonio, TX, pages 717–722, 2000.Google Scholar
  11. J. Fortin, P. Zieliński, D. Dubois and H. Fargier. Interval analysis in scheduling. In P. van Beek (Ed.), Principles and Practice of Constraint Programming — CP 2005. LNCS vol. 3709, 2005.Google Scholar
  12. M. Hapke, A. Jaszkiewicz and R. Slowiński. Fuzzy project scheduling system for software development. Fuzzy Sets and Systems 67:101–117, 1994.CrossRefMathSciNetGoogle Scholar
  13. J.E. Kelley and M.R. Walker. Critical path planning and and Scheduling. In Proceedings of the Eastern Joint Computational Conference pages 160–172, 1959.Google Scholar
  14. F.A. Loostma. Fuzzy Logic for Planning and Decision-Making. Dordrecht Kluwer Acad. Publ., 1997.Google Scholar
  15. H. Prade. Using fuzzy sets theory in a scheduling problem: a case study. Fuzzy Sets and Systems 2:153–165, 1979.zbMATHCrossRefMathSciNetGoogle Scholar
  16. H. Rommelfanger. Network analysis and information flow in fuzzy environment. Fuzzy Sets and Systems 67:119–128, 1994.CrossRefMathSciNetGoogle Scholar
  17. D.D. Sleator and R. E. Tarjan. A Data Structure for Dynamic Trees. Journal of Computer and System Science 26:362–391, 1983.zbMATHCrossRefMathSciNetGoogle Scholar
  18. J. Valdes, R. E. Tarjan, E. L. Lawler. The Recognition of Series Parallel Digraphs. SIAM Journal on Computing 11:298–313, 1982.zbMATHCrossRefMathSciNetGoogle Scholar
  19. P. Zieliński. On computing the latest starting times and floats of activities in a network with imprecise durations. Fuzzy Sets and Systems 150:53–76, 2005.CrossRefMathSciNetGoogle Scholar

Copyright information

© CISM, Udine 2006

Authors and Affiliations

  • Paweł Zieliński
    • 1
  1. 1.Institute of Mathematics and Computer ScienceWrocław University of TechnologyWroclaw

Personalised recommendations