Skip to main content
SpringerLink
Log in

Criticality analysis of activity networks under interval uncertainty

  • Published:
Journal of Scheduling Aims and scope Submit manuscript

Abstract

This paper reconsiders the Project Evaluation and Review Technique (PERT) scheduling problem when information about task duration is incomplete. We model uncertainty on task durations by intervals. With this problem formulation, our goal is to assert possible and necessary criticality of the different tasks and to compute their possible earliest starting dates, latest starting dates, and floats. This paper combines various results and provides a complete solution to the problem. We present the complexity results of all considered subproblems and efficient algorithms to solve them.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Adlakha, V. G., & Kulkarni, V. G. (1989). A classified bibliography of research on stochastic PERT networks: 1966–1987. INFOR, 27, 272–296.

    Google Scholar 

  • Averbakh, I., & Lebedev, V. (2004). Interval data minmax regret network optimization problems. Discrete Applied Mathematics, 138, 289–301.

    Article  Google Scholar 

  • Buckley, J. J. (1989). Fuzzy PERT. In G. Evans, W. Karwowski, & M. Wilhelm (Eds.), Applications of fuzzy set methodologies in industrial engineering (pp. 103–114). Amsterdam: Elsevier.

    Google Scholar 

  • Chanas, S., & Kamburowski, J. (1981). The use of fuzzy variables in PERT. Fuzzy Set Systems, 5, 1–19.

    Article  Google Scholar 

  • Chanas, S., & Zieliński, P. (2002). The computational complexity of the criticality problems in a network with interval activity times. European Journal of Operational Research, 136, 541–550.

    Article  Google Scholar 

  • Chanas, S., & Zieliński, P. (2003). On the hardness of evaluating criticality of activities in planar network with duration intervals. Operation Research Letters, 31, 53–59.

    Article  Google Scholar 

  • Chanas, S., Dubois, D., & Zieliński, P. (2002). On the sure criticality of tasks in activity networks with imprecise durations. IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics, 34, 393–407.

    Article  Google Scholar 

  • Conde, E. (2009). A minmax regret approach to the critical path method with task interval times. European Journal of Operational Research, 197, 235–242.

    Article  Google Scholar 

  • Demeulemeester, E., Vanhoucke, M., & Herroelen, W. (2003). A random network generator for activity-on-the-node networks. Journal of Scheduling, 6, 13–34.

    Article  Google Scholar 

  • Dubois, D. (1983). Modèles mathématiques de l’imprécis et de l’incertain en vue d’applications aux techniques d’aide à la décision. Thèse d’état de l’Université Scientifique et Médicale de Grenoble et de l’Institut National Politechnique de Grenoble.

  • Dubois, D., & Prade, H. (1980). Fuzzy sets and systems: theory and applications. New York: Academic Press.

    Google Scholar 

  • Dubois, D., Prade, H., & Smets, P. (1996). Representing partial ignorance. IEEE Transactions on Systems, Man and Cybernetics, 26, 361–377.

    Article  Google Scholar 

  • Dubois, D., Fargier, H., & Galvagnon, V. (2003). On latest starting times and floats in activity networks with ill-known durations. European Journal of Operational Research, 147, 266–280.

    Article  Google Scholar 

  • Dubois, D., Fargier, H., & Fortin, J. (2005). Computational methods for determining the latest starting times and floats of tasks in interval-valued activity networks. Journal of Intelligent Manufacturing, 16, 407–422.

    Article  Google Scholar 

  • Dubois, D., Prade, H., & Smets, P. (2008). A definition of subjective possibility. International Journal of Approximate Reasoning, 48, 352–364.

    Article  Google Scholar 

  • Elmaghraby, S. E. (1977). Activity networks: project planning and control by network models. New York: Wiley.

    Google Scholar 

  • Elmaghraby, S. E. (2000). On criticality and sensitivity in activity networks. European Journal of Operational Research, 127, 220–238.

    Article  Google Scholar 

  • Fargier, H., Galvagnon, V., & Dubois, D. (2000). Fuzzy PERT in series-parallel graphs. In 9th IEEE international conference on fuzzy systems (pp. 717–722). San Antonio, TX.

  • Ferson, S., & Ginzburg, L. (1996). Different methods are needed to propagate ignorance and variability. Reliability Engineering and Systems Safety, 54, 133–144.

    Article  Google Scholar 

  • Fortin, J., & Dubois, D. (2006). Solving fuzzy PERT using gradual real numbers. In L. Penserini, P. Peppas, & A. Perini (Eds.), Frontiers in artificial intelligence and applications : Vol. 142. Starting AI researcher’s symposium (STAIRS) (pp. 196–207). Riva del Garda, Italy, 28 August–01 September 2006. Amsterdam: IOS Press. http://www.iospress.nl/.

    Google Scholar 

  • Fortin, J., Zieliński, P., Dubois, D., & Fargier, H. (2005). Interval analysis in scheduling. In P. van Beek (Ed.), Lecture notes in computer science : Vol. 3709. Principles and practice of constraint programming—CP 2005 (pp. 226–240). Berlin: Springer.

    Chapter  Google Scholar 

  • Fortin, J., Dubois, D., & Fargier, H. (2008). Gradual numbers and their application to fuzzy interval analysis. IEEE Transactions on Fuzzy Systems, 16(2), 388–402.

    Article  Google Scholar 

  • Gazdik, I. (1983). Fuzzy network planning. IEEE Transactions on Reliability, 32, 304–313.

    Article  Google Scholar 

  • Hagstrom, J. N. (1988). Computational complexity of PERT problems. Networks, 18, 139–147.

    Article  Google Scholar 

  • Hapke, M., & Słowiński, R. (1996). Fuzzy priority heuristics for project scheduling. Fuzzy Sets and Systems, 86, 291–299.

    Article  Google Scholar 

  • Hapke, M., Jaszkiewicz, A., & Słowiński, R. (1994). Fuzzy project scheduling system for software development. Fuzzy Sets and Systems, 67, 101–107.

    Article  Google Scholar 

  • Karasan, O. E., Pinar, M. C., & Yaman, H. (2001). The robust shortest path problem with interval data. Optimization Online.

  • Kasperski, A., & Zieliński, P. (2006). The robust shortest path problem in series-parallel multidigraphs with interval data. Operations Research Letters, 34, 69–76.

    Article  Google Scholar 

  • Kasperski, A., & Zieliński, P. (2010). Minmax regret approach and optimality evaluation in combinatorial optimization problems with interval and fuzzy weights. European Journal of Operational Research, 200, 680–687.

    Article  Google Scholar 

  • Kaufmann, A., & Gupta, M. M. (1991). Fuzzy mathematical models in engineering and management science. Amsterdam: North Holland.

    Google Scholar 

  • Kelley, J. E. (1961). Critical path planning and scheduling—mathematical basis. Operations Research, 9, 296–320.

    Article  Google Scholar 

  • Kleindorfer, G. B. (1971). Bounding distributions for a stochastic acyclic network. Operations Research, 19, 1586–1601.

    Article  Google Scholar 

  • Kolisch, R., & Sprecher, A. (1996). PSPLIB—a project scheduling problem library. European Journal of Operational Research, 96, 205–216.

    Article  Google Scholar 

  • Kouvelis, P., & Yu, G. (1997). Robust discrete optimization and its applications. Dordrecht: Kluwer Academic.

    Google Scholar 

  • Loostma, F. A. (1997). Fuzzy logic for planning and decision-making. Dordrecht: Kluwer Academic.

    Google Scholar 

  • Ludwig, A., Möhring, R. H., & Stork, F. (2001). A computational study on bounding the makespan distribution in stochastic project networks. Annals of Operations Research, 102, 49–64.

    Article  Google Scholar 

  • Malcolm, D. G., Roseboom, J. H., Clark, C. E., & Fazar, W. (1959). Application of a technique for research and development program evaluation. Operations Research, 7, 646–669.

    Article  Google Scholar 

  • McCahon, C. S. (1993). Using PERT as an approximation of fuzzy project-network analysis. IEEE Transactions on Engineering Management, 40, 146–153.

    Article  Google Scholar 

  • McCahon, C. S., & Lee, E. S. (1988). Project network analysis with fuzzy activity times. Computers and Mathematics with Applications, 15, 829–838.

    Article  Google Scholar 

  • Meilijson, I., & Nadas, A. (1979). Convex majorization with an application to the length of critical paths. Journal of Applied Probability, 16, 671–677.

    Article  Google Scholar 

  • Moore, R. E. (1979). Methods and applications of interval analysis. Philadelphia: SIAM.

    Google Scholar 

  • Nasution, S. H. (1994). Fuzzy critical path method. IEEE Transactions on Systems, Man, and Cybernetics, 24, 48–57.

    Article  Google Scholar 

  • Prade, H. (1979). Using fuzzy sets theory in a scheduling problem: a case study. Fuzzy Sets and Systems, 2, 153–165.

    Article  Google Scholar 

  • Rommelfanger, H. (1994). Network analysis and information flow in fuzzy environment. Fuzzy Sets and Systems, 67, 119–128.

    Article  Google Scholar 

  • Shogan, A. W. (1977). Bounding distributions for a stochastic PERT network. Networks, 7, 359–381.

    Article  Google Scholar 

  • Valdes, J., Tarjan, R. E., & Lawler, E. L. (1982). The recognition of series parallel digraphs. SIAM Journal on Computing, 11, 298–313.

    Article  Google Scholar 

  • Zieliński, P. (2005). On computing the latest starting times and floats of activities in a network with imprecise durations. Fuzzy Sets and Systems, 150, 53–76.

    Article  Google Scholar 

  • Zieliński, P. (2006). Efficient computation of project characteristics in a series-parallel activity network with interval durations. In G. Della Riccia, D. Dubois, R. Kruse, & H. J. Lenz (Eds.), CISM courses and lectures : Vol. 482. Decision theory and multi-agent planning (pp. 111–130). New York: Springer.

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LIRMM, Université Montpellier 2 and CNRS, 161 rue Ada, 34392, Montpellier Cedex 5, France

    Jérôme Fortin

  2. Institute of Mathematics and Computer Science, Wrocław University of Technology, Wybrzeże Wyspiańskiego 27, 50-370, Wrocław, Poland

    Paweł Zieliński

  3. I.R.I.T., Université Paul Sabatier, 118 route Narbonne, 31062, Toulouse Cedex 4, France

    Didier Dubois & Hélène Fargier

Authors
  1. Jérôme Fortin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paweł Zieliński
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Didier Dubois
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Hélène Fargier
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Paweł Zieliński.

Additional information

Dedicated to the memory of Professor Stefan Chanas.

The extended abstract version of this paper has appeared in Proceedings of 11th International Conference on Principles and Practice of Constraint Programming (CP2005) (Fortin et al. 2005). Paweł Zieliński was partially supported by Polish Committee for Scientific Research, grant 3T11C05430.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fortin, J., Zieliński, P., Dubois, D. et al. Criticality analysis of activity networks under interval uncertainty. J Sched 13, 609–627 (2010). https://doi.org/10.1007/s10951-010-0163-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10951-010-0163-3

Keywords

Search

Navigation