×

A path enumeration approach for the analysis of critical activities in fuzzy networks. (English) Zbl 1250.90040

Summary: This paper addresses the problem of determining the degree of possible and necessary criticality of activities as well as determining paths in networks that have fuzzy activity durations. In such networks, activities and paths are reported in a fuzzy representation as being critical, with certain degrees of possibility and necessity, instead of being declared critical or not in a binary way. Although the problem of computing the possibility and necessity degrees of criticality for paths have been investigated in the literature, those problems for activities have not yet been addressed. Herein, an efficient algorithm that relies on a path enumeration technique is proposed to compute the possibility degrees of criticality of activities. Additionally, the proposed algorithm computes paths with maximum and minimum degrees for the necessity of criticality, which correspond to activities. Real-world project networks were used to evaluate the performance of the algorithm.

MSC:

90B35 Deterministic scheduling theory in operations research

Software:

PSPLIB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Buckley, J. J., Fuzzy PERT, (Evans, G. W.; Karwowski, W.; Wilhelm, M., Application of Fuzzy Set Methodologies in Industrial Engineering (1989), Elsevier: Elsevier Amsterdam), 103-125
[2] Chanas, S.; Dubois, D.; Zielinski, P., On the sure criticality of tasks in activity networks with imprecise durations, IEEE Transaction on Systems, Man, and Cybernetics - Part B, 32, 393-407 (2002)
[3] Chanas, S.; Kamburowski, J., The use of fuzzy variables in PERT, Fuzzy Sets and Systems, 5, 1-19 (1981) · Zbl 0451.90076
[4] Chanas, S.; Zielinski, P., Critical path analysis in the network with fuzzy activity times, Fuzzy Set and Systems, 122, 195-204 (2001) · Zbl 1015.90096
[5] Chanas, S.; Zielinski, P., The computational complexity of the criticality of the problems in a network with interval activity times, European Journal of Operational Research, 136, 3, 541-550 (2002) · Zbl 1008.90029
[6] Chanas, S.; Zielinski, P., On the hardness of evaluating criticality of activities in a planar network with duration intervals, Operation Research Letters, 31, 53-59 (2003) · Zbl 1036.90024
[7] Chen, S. P., Analysis of critical paths in a project network with fuzzy activity times, European Journal of Operation Research, 183, 442-459 (2007) · Zbl 1128.90010
[8] Chen, S. P.; Hsueh, Y. J., A simple approach to fuzzy critical path analysis in project networks, Applied Mathematical Modelling, 32, 1289-1297 (2008) · Zbl 1172.90333
[9] Chen, C. T.; Huang, S. F., Applying fuzzy method for measuring criticality in project network, Information Sciences, 177, 2448-2458 (2007) · Zbl 1124.90013
[10] Chen, W.; Shi, Y.; Teng, H.; Lan, X.; Hu, L., An efficient hybrid algorithm for resource-constrained project scheduling, Information Sciences, 180, 1031-1039 (2010)
[11] Cohen, Y.; Sadeh, A., A new approach for constructing and generating AOA networks, Journal of Computer Science, 1 (2007)
[12] Demeulemeester, E. L.; Herroelen, W. S., Project Scheduling: A Research Handbook (2002), Kluwer Academic Publishers · Zbl 1059.90068
[13] Dubois, D.; Fargier, H.; Fortemps, P., Fuzzy scheduling: modeling flexible constraints vs. coping with incomplete knowledge, European Journal Operation Research, 147, 231-252 (2003) · Zbl 1037.90028
[14] Dubois, D.; Fargier, H.; Fortin, J., Computational methods for determining the latest starting times and floats of tasks in interval-valued networks, Journal of Intelligent Manufacturing, 16, 407-421 (2005)
[15] 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, 266-280 (2003) · Zbl 1037.90004
[16] Dubois, D.; Prade, H., Operations on fuzzy numbers, International Journal of System Science, 30, 613-626 (1978) · Zbl 0383.94045
[17] Dubois, D.; Prade, H., Possibility Theory: An Approach to Computerized Processing of Uncertainty (1988), Plenum Press
[18] E Elmaghraby, S.; Kamburowski, J., The analysis of activity network under generalized precedence relations (GPRs), Management Science, 38, 1245-1263 (1992) · Zbl 0758.90044
[19] Fortin, J.; Zielinski, P.; Dubois, D.; Fargier, H., Interval analysis in scheduling, (van Beek, P., 11th International Conference on Principles and Practice of Constraint Programming, CP 2005. 11th International Conference on Principles and Practice of Constraint Programming, CP 2005, LNCS, vol. 3709 (2005), Springer-Verlag: Springer-Verlag Berlin), 226-240 · Zbl 1153.90421
[20] Gazdik, I., Fuzzy network planning, IEEE Transaction on Reliability, R-32, 3, 304-313 (1983) · Zbl 0526.90053
[21] Hapke, M.; Jaszkiewicz, A.; Slowiński, R., Fuzzy project scheduling system for software development, Fuzzy Sets and Systems, 67, 101-117 (1994)
[22] Herroelen, W.; Leus, R., Project scheduling under uncertainty: survey and research potentials, European Journal of Operational Research, 165, 289-306 (2005) · Zbl 1066.90050
[23] Kamburowski, J.; Michael, D. J.; Stallmann, M., Minimizing the complexity of an activity network, Networks, 36, 1-6 (2000) · Zbl 0969.90017
[24] Kaufmann, A.; Gupta, M. M., Fuzzy Mathematical Models in Engineering and Management Science (1988), North-Holland: North-Holland Amsterdam · Zbl 0683.90024
[25] J.E. Kelley, M.R. Walker, Critical path planning and scheduling, in: Proc. Eastern Joint Computer Conference, vol. 16, 1959, pp. 160-172.; J.E. Kelley, M.R. Walker, Critical path planning and scheduling, in: Proc. Eastern Joint Computer Conference, vol. 16, 1959, pp. 160-172.
[26] Kolisch, R.; Sprecher, A., Psplib – a project scheduling library, European Journal of Operational Research, 96, 205-216 (1996) · Zbl 0947.90587
[27] Kolisch, R.; Sprecher, A.; Drexl, A., Characterization and generation of a general class of resource-constrained project scheduling problems, Management Science, 41, 1693-1703 (1995) · Zbl 0870.90070
[28] Krishnamoorty, M. S.; Deo, N., Complexity of the minimum dummy activities problem in a pert network, Network, 9, 189-194 (1979) · Zbl 0414.68018
[29] Kurihara, K.; Nishiuchi, N., Efficient Monte Carlo simulation method of GERT-type network for project management, Computers & Industrial Engineering, 42, 521-531 (2002)
[30] Liberatore, M. J., Critical path analysis with fuzzy activity times, IEEE Transactions on Engineering Management, 55, 329-337 (2008)
[31] Lootsma, F. A., Stochastic and fuzzy PERT, European Journal of Operational Research, 43, 74-183 (1989) · Zbl 0681.90039
[32] Malcolm, D. G.; Roseboom, J. H.; Clark, C. E., Application of a technique for research and development program evaluation, Operations Research, 7, 646-669 (1959) · Zbl 1255.90070
[33] Prade, H., Using fuzzy sets theory in a scheduling problem: a case study, Fuzzy Sets and Systems, 2, 153-165 (1979) · Zbl 0403.90036
[34] Ragsdale, C., The current state of network simulation in project management theory and practice, Omega, 17, 21-25 (1989)
[35] Shipley, M. F.; de Korvin, A.; Omer, K., BIFPET methodology versus PERT in project management: fuzzy probability instead of the beta distribution, Journal of Engineering and Technology Management, 14, 49-65 (1997)
[36] Xu, B.; Fang, W.; Shi, R.; Yu, J.; Liu, L., Three-objective fuzzy chance-constrained programming model for multiproject and multi-item investment combination, Information Sciences, 179, 623-641 (2009) · Zbl 1157.90579
[37] S.H. Yakhchali, M.H. Fazel Zarandi, I.B. Turksen, S.H. Ghodsypour, Possible criticality of paths in networks with imprecise durations and time lags, in: IEEE Conference, NAFIPS, 2007, pp. 277-282.; S.H. Yakhchali, M.H. Fazel Zarandi, I.B. Turksen, S.H. Ghodsypour, Possible criticality of paths in networks with imprecise durations and time lags, in: IEEE Conference, NAFIPS, 2007, pp. 277-282.
[38] S.H. Yakhchali, M.H. Fazel Zarandi, I.B. Turksen, S.H. Ghodsypour, Necessary criticality of paths in networks with imprecise durations and time lags, in: IEEE Conference, NAFIPS, 2007, pp. 271-276.; S.H. Yakhchali, M.H. Fazel Zarandi, I.B. Turksen, S.H. Ghodsypour, Necessary criticality of paths in networks with imprecise durations and time lags, in: IEEE Conference, NAFIPS, 2007, pp. 271-276.
[39] Yakhchali, S. H.; Ghodsypour, S. H., Erratum to on computing the latest starting times and floats of activities in a network with imprecise durations’, Fuzzy Sets and Systems, 159, 856 (2008) · Zbl 1168.90477
[40] S.H. Yakhchali, S.H. Ghodsypour, Hybrid genetic algorithms for computing the float of activities in networks with imprecise durations, in: IEEE International Conference on Fuzzy Systems, Hong Kong, 2008, pp. 1789-1794.; S.H. Yakhchali, S.H. Ghodsypour, Hybrid genetic algorithms for computing the float of activities in networks with imprecise durations, in: IEEE International Conference on Fuzzy Systems, Hong Kong, 2008, pp. 1789-1794.
[41] Yakhchali, S. H.; Ghodsypour, S. H., Computing the latest starting times of activities in interval-valued networks with minimal time lags, European Journal of Operational Research, 200, 874-880 (2010) · Zbl 1177.90191
[42] Yakhchali, S. H.; Ghodsypour, S. H., A path enumeration approach for temporal analysis in networks with imprecise durations and generalized precedence relations, Applied Soft Computing, 34, 2044-2058 (2010) · Zbl 1193.90118
[43] S.H. Yakhchali, S.H. Ghodsypour, On criticality of paths in networks with imprecise durations and generalized precedence relations, in: World Conference on Soft Computing, 2008.; S.H. Yakhchali, S.H. Ghodsypour, On criticality of paths in networks with imprecise durations and generalized precedence relations, in: World Conference on Soft Computing, 2008. · Zbl 1168.90477
[44] S.H. Yakhchali, S.H. Ghodsypour, S.M.T. Fatemi Ghomi, An incremental approach for temporal analysis in networks with imprecise activity and time lag durations, in: IEEE International Conference on Industrial Engineering and Engineering Management, Singapore, 2008.; S.H. Yakhchali, S.H. Ghodsypour, S.M.T. Fatemi Ghomi, An incremental approach for temporal analysis in networks with imprecise activity and time lag durations, in: IEEE International Conference on Industrial Engineering and Engineering Management, Singapore, 2008.
[45] S.H. Yakhchali, S.H. Ghodsypour, C. O’Brien, Project scheduling with irregular starting time cost and imprecise durations, in: 15th International Working Seminar on Production Economics, Innsbruck, Austria, vol. 4, 2008, pp. 249-256.; S.H. Yakhchali, S.H. Ghodsypour, C. O’Brien, Project scheduling with irregular starting time cost and imprecise durations, in: 15th International Working Seminar on Production Economics, Innsbruck, Austria, vol. 4, 2008, pp. 249-256.
[46] Zadeh, L. A., Fuzzy sets as a basis for a theory of possibility, Fuzzy Sets and Systems, 1, 3-28 (1978) · Zbl 0377.04002
[47] Zadeh, L. A., Toward a generalized theory of uncertainty (GTU) - an outline, Information Sciences, 17, 1-40 (2005) · Zbl 1074.94021
[48] Zadeh, L. A., Is there a need for fuzzy logic?, Information Sciences, 178, 2751-2779 (2008) · Zbl 1148.68047
[49] Zielinski, P., On computing the latest starting times and floats of activities in a network with imprecise durations, Fuzzy Sets and Systems, 159, 53-76 (2005) · Zbl 1079.90069
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.