×

zbMATH — the first resource for mathematics

Criticality analysis of activity networks under interval uncertainty. (English) Zbl 1208.90061
Summary: 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.

MSC:
90B35 Deterministic scheduling theory in operations research
90B10 Deterministic network models in operations research
68R10 Graph theory (including graph drawing) in computer science
Software:
RanGen; PSPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adlakha, V. G., & Kulkarni, V. G. (1989). A classified bibliography of research on stochastic PERT networks: 1966–1987. INFOR, 27, 272–296. · Zbl 0678.90033
[2] Averbakh, I., & Lebedev, V. (2004). Interval data minmax regret network optimization problems. Discrete Applied Mathematics, 138, 289–301. · Zbl 1056.90010
[3] 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.
[4] Chanas, S., & Kamburowski, J. (1981). The use of fuzzy variables in PERT. Fuzzy Set Systems, 5, 1–19. · Zbl 0451.90076
[5] 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. · Zbl 1008.90029
[6] 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. · Zbl 1036.90024
[7] 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.
[8] Conde, E. (2009). A minmax regret approach to the critical path method with task interval times. European Journal of Operational Research, 197, 235–242. · Zbl 1157.90439
[9] Demeulemeester, E., Vanhoucke, M., & Herroelen, W. (2003). A random network generator for activity-on-the-node networks. Journal of Scheduling, 6, 13–34. · Zbl 1154.90440
[10] 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.
[11] Dubois, D., & Prade, H. (1980). Fuzzy sets and systems: theory and applications. New York: Academic Press. · Zbl 0444.94049
[12] Dubois, D., Prade, H., & Smets, P. (1996). Representing partial ignorance. IEEE Transactions on Systems, Man and Cybernetics, 26, 361–377.
[13] 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. · Zbl 1037.90004
[14] 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.
[15] Dubois, D., Prade, H., & Smets, P. (2008). A definition of subjective possibility. International Journal of Approximate Reasoning, 48, 352–364. · Zbl 1184.68507
[16] Elmaghraby, S. E. (1977). Activity networks: project planning and control by network models. New York: Wiley. · Zbl 0385.90076
[17] Elmaghraby, S. E. (2000). On criticality and sensitivity in activity networks. European Journal of Operational Research, 127, 220–238. · Zbl 0990.90119
[18] 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.
[19] Ferson, S., & Ginzburg, L. (1996). Different methods are needed to propagate ignorance and variability. Reliability Engineering and Systems Safety, 54, 133–144.
[20] 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/ .
[21] 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. · Zbl 1153.90421
[22] 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. · Zbl 05516457
[23] Gazdik, I. (1983). Fuzzy network planning. IEEE Transactions on Reliability, 32, 304–313. · Zbl 0526.90053
[24] Hagstrom, J. N. (1988). Computational complexity of PERT problems. Networks, 18, 139–147.
[25] Hapke, M., & Słowiński, R. (1996). Fuzzy priority heuristics for project scheduling. Fuzzy Sets and Systems, 86, 291–299.
[26] Hapke, M., Jaszkiewicz, A., & Słowiński, R. (1994). Fuzzy project scheduling system for software development. Fuzzy Sets and Systems, 67, 101–107.
[27] Karasan, O. E., Pinar, M. C., & Yaman, H. (2001). The robust shortest path problem with interval data. Optimization Online.
[28] Kasperski, A., & Zieliński, P. (2006). The robust shortest path problem in series-parallel multidigraphs with interval data. Operations Research Letters, 34, 69–76. · Zbl 1080.90058
[29] 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. · Zbl 1177.90345
[30] Kaufmann, A., & Gupta, M. M. (1991). Fuzzy mathematical models in engineering and management science. Amsterdam: North Holland. · Zbl 0683.90024
[31] Kelley, J. E. (1961). Critical path planning and scheduling–mathematical basis. Operations Research, 9, 296–320. · Zbl 0098.12103
[32] Kleindorfer, G. B. (1971). Bounding distributions for a stochastic acyclic network. Operations Research, 19, 1586–1601. · Zbl 0247.90026
[33] Kolisch, R., & Sprecher, A. (1996). PSPLIB–a project scheduling problem library. European Journal of Operational Research, 96, 205–216. · Zbl 0947.90587
[34] Kouvelis, P., & Yu, G. (1997). Robust discrete optimization and its applications. Dordrecht: Kluwer Academic. · Zbl 0873.90071
[35] Loostma, F. A. (1997). Fuzzy logic for planning and decision-making. Dordrecht: Kluwer Academic.
[36] 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. · Zbl 1024.90012
[37] 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. · Zbl 1255.90070
[38] McCahon, C. S. (1993). Using PERT as an approximation of fuzzy project-network analysis. IEEE Transactions on Engineering Management, 40, 146–153.
[39] McCahon, C. S., & Lee, E. S. (1988). Project network analysis with fuzzy activity times. Computers and Mathematics with Applications, 15, 829–838. · Zbl 0648.90041
[40] Meilijson, I., & Nadas, A. (1979). Convex majorization with an application to the length of critical paths. Journal of Applied Probability, 16, 671–677. · Zbl 0417.60025
[41] Moore, R. E. (1979). Methods and applications of interval analysis. Philadelphia: SIAM. · Zbl 0417.65022
[42] Nasution, S. H. (1994). Fuzzy critical path method. IEEE Transactions on Systems, Man, and Cybernetics, 24, 48–57.
[43] Prade, H. (1979). Using fuzzy sets theory in a scheduling problem: a case study. Fuzzy Sets and Systems, 2, 153–165. · Zbl 0403.90036
[44] Rommelfanger, H. (1994). Network analysis and information flow in fuzzy environment. Fuzzy Sets and Systems, 67, 119–128.
[45] Shogan, A. W. (1977). Bounding distributions for a stochastic PERT network. Networks, 7, 359–381. · Zbl 0366.94042
[46] Valdes, J., Tarjan, R. E., & Lawler, E. L. (1982). The recognition of series parallel digraphs. SIAM Journal on Computing, 11, 298–313. · Zbl 0478.68065
[47] 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. · Zbl 1079.90069
[48] 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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.