×

Computing latest starting times of activities in interval-valued networks with minimal time lags. (English) Zbl 1177.90191

Summary: This paper deals with problems of determining possible values of earliest and latest starting times of an activity in networks with minimal time lags and imprecise durations that are represented by means of interval or fuzzy numbers. Although minimal time lags are practical in different projects, former researchers have not considered these problems.
After proposing propositions which reduce the search space, a novel polynomial algorithm is presented to compute intervals of possible values of latest starting times in interval-valued networks with minimal time lags. Then, the results are extended to networks with fuzzy durations.

MSC:

90B35 Deterministic scheduling theory in operations research
90C70 Fuzzy and other nonstochastic uncertainty mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network flows, (Nemhauser, G. L.; Rinnooy Kan, A. H.G.; Todd, M. J., Handbooks in Operations Research and Management Science (1989), Elsevier: Elsevier Amsterdam), 258-263
[2] Bartusch, M.; Mohring, R. H.; Radermacher, F. J., Scheduling project networks with resource constraints and time windows, Annals of Operations Research, 16, 201-240 (1988) · Zbl 0693.90047
[3] 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
[4] 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)
[5] Chanas, S.; Kamburowski, J., The use of fuzzy variables in PERT, Fuzzy Sets and Systems, 5, 1-19 (1981) · Zbl 0451.90076
[6] 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
[7] 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, 541-550 (2002) · Zbl 1008.90029
[8] 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
[9] Chen, S. P., Analysis of critical paths in a project network with fuzzy activity times, European Journal of Operational Research, 183, 442-459 (2007) · Zbl 1128.90010
[10] 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
[11] Chen, C. T.; Huang, S. F., Applying fuzzy method for measuring criticality in project network, Information Sciences, 177, 2448-2458 (2007) · Zbl 1124.90013
[12] Demeulemeester, E. L.; Herroelen, W. S., Project Scheduling: A Research Handbook (2002), Kluwer Academic Publishers · Zbl 1059.90068
[13] Dodin, B., Bounding the project completion time distribution in PERT networks, Operations Research, 33, 862-881 (1985) · Zbl 0579.90055
[14] Dubois, D.; Fargier, H.; Fortemps, P., Fuzzy scheduling: Modeling flexible constraints vs. coping with incomplete knowledge, European Journal Operational Research, 147, 231-252 (2003) · Zbl 1037.90028
[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.; 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)
[17] Dubois, D.; Prade, H., Operations on fuzzy numbers, International Journal of System Science, 30, 613-626 (1978) · Zbl 0383.94045
[18] Dubois, D.; Prade, H., Fuzzy Sets and Systems: Theory and Applications (1980), Academic Press: Academic Press New York · Zbl 0444.94049
[19] Dubois, D.; Prade, H., Possibility Theory: An Approach to Computerized Processing of Uncertainty (1988), Plenum Press · Zbl 0703.68004
[20] Fargier, H., Galvagnon, V., Dubois, D., 2000. Fuzzy PERT in series-parallel graphs. In: Ninth IEEE International Conference Fuzzy Systems, San Antonio, Tx, pp. 717-722.; Fargier, H., Galvagnon, V., Dubois, D., 2000. Fuzzy PERT in series-parallel graphs. In: Ninth IEEE International Conference Fuzzy Systems, San Antonio, Tx, pp. 717-722.
[21] Fortin, J., Dubois, D., 2006. Solving fuzzy PERT using gradual real numbers. In: Proceedings of the Third European Starting AI Researcher Symposium, Riva del Garda, Italy, pp. 196-207.; Fortin, J., Dubois, D., 2006. Solving fuzzy PERT using gradual real numbers. In: Proceedings of the Third European Starting AI Researcher Symposium, Riva del Garda, Italy, pp. 196-207.
[22] Fortin, J.; Dubois, D.; Fargier, H., Gradual numbers and their application to fuzzy interval analysis, IEEE Transactions on Fuzzy Systems, 16, 388-402 (2008)
[23] Fortin, J., Zielinski, P., Dubois, D., Fargier, H., 2005. Interval analysis in scheduling. In: Principles and Practice of Constraint Programming - 11th International Conference, CP, pp. 226-240.; Fortin, J., Zielinski, P., Dubois, D., Fargier, H., 2005. Interval analysis in scheduling. In: Principles and Practice of Constraint Programming - 11th International Conference, CP, pp. 226-240. · Zbl 1153.90421
[24] Gazdik, I., Fuzzy network planning, IEEE Transaction on Reliability, 32, 304-313 (1983) · Zbl 0526.90053
[25] Hapke, M.; Jaszkiewicz, A.; Słowinski, R., Fuzzy project scheduling system for software development, Fuzzy Sets and Systems, 67, 101-117 (1994)
[26] Hapke, M.; Slowinski, R., Fuzzy priority heuristic for project scheduling, Fuzzy Sets and Systems, 83, 291-299 (1996)
[27] Herroelen, W.; Leus, R., Project scheduling under uncertainty: Survey and research potentials, European Journal of Operational Research, 165, 289-306 (2005) · Zbl 1066.90050
[28] Kaufmann, A.; Gupta, M. M., Fuzzy Mathematical Models in Engineering and Management Science (1988), North-Holland: North-Holland Amsterdam · Zbl 0683.90024
[29] Kelley, J. E., Critical path planning and scheduling mathematical basis, Operations Research, 9, 296-320 (1961) · Zbl 0098.12103
[30] Kurihara, K.; Nishiuchi, N., Efficient Monte Carlo simulation method of GERT-type network for project management, Computers and Industrial Engineering, 42, 521-531 (2002)
[31] Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart, and Winston: Holt, Rinehart, and Winston New York · Zbl 0358.68059
[32] Lootsma, F. A., Stochastic and fuzzy PERT, European Journal of Operational Research, 43, 174-183 (1989) · Zbl 0681.90039
[33] 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
[34] Mares, M., Network analysis of fuzzy technologies, (Evans, G. W.; Karwowski, W.; Wilhelm, M. R., Applications of Fuzzy Set Methodologies in Industrial Engineering (1989), Elsevier: Elsevier Amsterdam, The Netherlands), 115-125
[35] McCahon, C. S., Using pert as an approximation of fuzzy project-network analysis, IEEE Transactions on Engineering Management, 40, 146-153 (1993)
[36] McCahon, C. S.; Lee, E. S., Project network analysis with fuzzy activity times, Computers and Mathematics with Applications, 15, 829-838 (1988) · Zbl 0648.90041
[37] Moder, J. J.; Crandall, K. C., Precedence diagramming: Time computations, anomalies and remedies, Project Management: Methods and Studies, 95-110 (1985)
[38] Moder, J. J.; Phillips, C. R.; Davis, E. W., Project Management with CPM, PERT and Precedence Diagramming (1983), Van Nostrand-Reinhold
[39] Mon, D. L.; Cheng, C. H.; Lu, H. C., Application of fuzzy distributions on project management, Fuzzy Sets and Systems, 73, 227-234 (1995) · Zbl 0855.90056
[40] Nasution, S. H., Fuzzy critical path method, IEEE Transactions on Systems Man, Cybernetics, 24, 48-57 (1994)
[41] Prade, H., Using fuzzy sets theory in a scheduling problem: A case study, Fuzzy Sets and Systems, 2, 153-165 (1979) · Zbl 0403.90036
[42] Project Management Institute (PMI), A Guide to the Project Management Body of Knowledge: PMBOK Guide (2004), PMI: PMI Newtown Square, PA
[43] Ragsdale, C., The current state of network simulation in project management theory and practice, Omega, 17, 21-25 (1989)
[44] Rommelfanger, H., Network analysis and information flow in fuzzy environment, Fuzzy Sets and Systems, 67, 119-128 (1994)
[45] 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)
[46] Valls, V.; Lino, P., Criticality analysis in activity-on-node networks with minimal time lags, Annals of Operations Research, 102, 17-37 (2001) · Zbl 1024.90046
[47] Wiest, J. D., Precedence diagramming method: Some unusual characteristics and their implications for project managers, Journal of Operations Management, 1, 121-130 (1981)
[48] Wiest, J. D.; Levy, F. K., A Management Guide to PERT/CPM with GERT/PDM/DCPM and Other Networks (1977), Prentice-Hall
[49] Yakhchali, S.H., Fazel Zarandi, M.H., Turksen, I.B., Ghodsypour, S.H., 2007a. Possible criticality of paths in networks with imprecise durations and time lags. In: IEEE Conference, NAFIPS, pp. 277-282.; Yakhchali, S.H., Fazel Zarandi, M.H., Turksen, I.B., Ghodsypour, S.H., 2007a. Possible criticality of paths in networks with imprecise durations and time lags. In: IEEE Conference, NAFIPS, pp. 277-282.
[50] Yakhchali, S.H., Fazel Zarandi, M.H., Turksen, I.B., Ghodsypour, S.H., 2007b. Necessary criticality of paths in networks with imprecise durations and time lags. In: IEEE Conference, NAFIPS, pp. 271-276.; Yakhchali, S.H., Fazel Zarandi, M.H., Turksen, I.B., Ghodsypour, S.H., 2007b. Necessary criticality of paths in networks with imprecise durations and time lags. In: IEEE Conference, NAFIPS, pp. 271-276.
[51] 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
[52] Yakhchali, S.H., Ghodsypour, S.H., 2008b. Hybrid genetic algorithms for computing the float of activities in networks with imprecise durations. In: IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), Hong Kong, pp. 1789-1794.; Yakhchali, S.H., Ghodsypour, S.H., 2008b. Hybrid genetic algorithms for computing the float of activities in networks with imprecise durations. In: IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), Hong Kong, pp. 1789-1794.
[53] Yakhchali, S.H., Ghodsypour, S.H., O’Brien, C., 2008. Project scheduling with irregular starting time cost and imprecise durations. In: 15th International Working Seminar on Production Economics, Innsbruck, Austria, vol. 4, pp. 249-256.; Yakhchali, S.H., Ghodsypour, S.H., O’Brien, C., 2008. Project scheduling with irregular starting time cost and imprecise durations. In: 15th International Working Seminar on Production Economics, Innsbruck, Austria, vol. 4, pp. 249-256.
[54] Yao, J. S.; Lin, F. T., Fuzzy critical path method based on signed distance ranking of fuzzy numbers, IEEE Transaction on Systems, Man, and Cybernetics-Part A, 30, 76-82 (2000)
[55] Zadeh, L. A., Fuzzy sets as a basis for a theory of possibility, Fuzzy Sets and Systems, 1, 3-28 (1978) · Zbl 0377.04002
[56] 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.