The computational complexity of the criticality problems in a network with interval activity times.

*(English)*Zbl 1008.90029Summary: The paper analyzes the criticality in a network with interval activities duration times. A natural generalization of the criticality notion (for a path, an activity and an event) for the case of network with interval activity duration times is given. The computation complexity of five problems linked to the introduced criticality notion is presented.

##### MSC:

90B50 | Management decision making, including multiple objectives |

90B35 | Deterministic scheduling theory in operations research |

65Y20 | Complexity and performance of numerical algorithms |

PDF
BibTeX
XML
Cite

\textit{S. Chanas} and \textit{P. Zieliński}, Eur. J. Oper. Res. 136, No. 3, 541--550 (2002; Zbl 1008.90029)

Full Text:
DOI

##### References:

[1] | Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0286.68029 |

[2] | J.J. Buckley, Fuzzy PERT, in: G.W. Evans, W. Karwowski, M.R. Wilhelm (Eds.), Applications of Fuzzy Set Methodologies in Industrial Engineering, Elsevier, Amsterdam 1989, pp. 103-114 |

[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.; Zieliński, P., Critical path analysis in the network with fuzzy activity times, Fuzzy sets and systems, 122, 195-204, (2001) · Zbl 1015.90096 |

[5] | Elmaghraby, S.E., On criticality and sensitivity in activity networks, European journal of operational research, 127, 220-238, (2000) · Zbl 0990.90119 |

[6] | Garey, M.R.; Johnson, D.S., Strong NP-completeness results: motivation, examples, and implications, Journal of the ACM, 25, 4, 499-508, (1978) · Zbl 0379.68035 |

[7] | Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freemam San Francisco · Zbl 0411.68039 |

[8] | Gazdik, I., Fuzzy network planning, IEEE transactions on reliability, R-32 3, 304-313, (1983) · Zbl 0526.90053 |

[9] | Johnson, D.S.; Kashdan, S.D., Lower bounds for selection in X+Y and other multisets, Journal of the ACM, 25, 4, 556-570, (1978) · Zbl 0388.68057 |

[10] | Kamburowski, J., An upper bound on the expected completion time of PERT networks, European journal of operational research, 21, 206-212, (1985) · Zbl 0569.90047 |

[11] | J. Kamburowski, Normally distributed activity durations in networks, Journal of Operational Research Society 36 (1985) 1051-1057; corrigendum 37 (1986) 529 · Zbl 0579.90052 |

[12] | Kamburowski, J., On the computational complexity of the shortest route and maximum flow problems in stochastic networks, Foundations of control engineering, 11, 4, 167-175, (1986) · Zbl 0616.90016 |

[13] | Kelley, J.E., Critical path planning and scheduling – mathematical basis, Operations research, 9, 296-320, (1961) · Zbl 0098.12103 |

[14] | Loostma, F.A., Stochastic and fuzzy PERT, European journal of operational research, 43, 174-183, (1989) · Zbl 0681.90039 |

[15] | Malcolm, D.G.; Roseboom, J.H.; Clark, C.E.; Fazar, W., Application of a technique for research and development project evaluation, Operations research, 7, 5, 646-669, (1959) · Zbl 1255.90070 |

[16] | Nasution, S.H., Fuzzy critical path method, IEEE transactions on systems man and cybernetics, 24, 1, 48-57, (1994) |

[17] | Prade, H., Using fuzzy sets theory in a scheduling problem: A case study, Fuzzy sets and systems, 2, 153-165, (1979) · Zbl 0403.90036 |

[18] | Rommelfanger, H., Network analysis and information flow in fuzzy environment, Fuzzy sets and systems, 67, 119-128, (1994) |

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.