IDEAS home Printed from https://ideas.repec.org/a/eee/matcom/v21y1979i4p376-384.html
   My bibliography  Save this article

The use of cutsets in Monte Carlo analysis of stochastic networks

Author

Listed:
  • Sigal, C.E.
  • Pritsker, A.A.B.
  • Solberg, J.J.

Abstract

Monte Carlo methods utilizing a new network concept, Uniformly Directed Cutsets (UDCs), are presented for analyzing directed, acyclic networks with probabilistic arc durations. The procedures involve sampling arc values for arcs not on a UDC and utilizing known probability information for arcs on a UDC. This approach results in less sampling effort and less associated variance than a straightforward simulation approach. A proof of this variance reduction is offered. The procedures provide estimates for project completion time distributions, criticality indices, minimum time distributions and path optimality indices. All of these network performance measures are useful to decision makers in project planning. Application areas include PERT-type network planning, equipment replacement analysis, reliability modeling, stochastic dynamic programming problems and maximal flow problems.

Suggested Citation

  • Sigal, C.E. & Pritsker, A.A.B. & Solberg, J.J., 1979. "The use of cutsets in Monte Carlo analysis of stochastic networks," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 21(4), pages 376-384.
    • Handle: RePEc:eee:matcom:v:21:y:1979:i:4:p:376-384
    DOI: 10.1016/0378-4754(79)90007-7
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/0378475479900077
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/0378-4754(79)90007-7?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. H. O. Hartley & A. W. Wortham, 1966. "A Statistical Theory for PERT Critical Path Analysis," Management Science, INFORMS, vol. 12(10), pages 469-481, June.
    2. H. Frank, 1969. "Shortest Paths in Probabilistic Graphs," Operations Research, INFORMS, vol. 17(4), pages 583-599, August.
    3. Larry J. Ringer, 1969. "Numerical Operators for Statistical PERT Critical Path Analysis," Management Science, INFORMS, vol. 16(2), pages 136-143, October.
    4. J. J. Martin, 1965. "Distribution of the Time Through a Directed, Acyclic Network," Operations Research, INFORMS, vol. 13(1), pages 46-66, February.
    5. Mark B. Garman, 1972. "More on Conditioned Sampling in the Simulation of Stochastic Networks," Management Science, INFORMS, vol. 19(1), pages 90-95, September.
    6. John M. Burt, Jr. & Mark B. Garman, 1971. "Conditional Monte Carlo: A Simulation Technique for Stochastic Network Analysis," Management Science, INFORMS, vol. 18(3), pages 207-217, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Athanassios N. Avramidis & Kenneth W. Bauer & James R. Wilson, 1991. "Simulation of stochastic activity networks using path control variates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(2), pages 183-201, April.
    2. Dawson, C. W., 1995. "A dynamic sampling technique for the simulation of probabilistic and generalized activity networks," Omega, Elsevier, vol. 23(5), pages 557-566, October.
    3. Brucker, Peter & Drexl, Andreas & Mohring, Rolf & Neumann, Klaus & Pesch, Erwin, 1999. "Resource-constrained project scheduling: Notation, classification, models, and methods," European Journal of Operational Research, Elsevier, vol. 112(1), pages 3-41, January.
    4. N-H Shih, 2005. "Estimating completion-time distribution in stochastic activity networks," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(6), pages 744-749, June.
    5. Elmaghraby, Salah E., 2000. "On criticality and sensitivity in activity networks," European Journal of Operational Research, Elsevier, vol. 127(2), pages 220-238, December.
    6. Elmaghraby, Salah E. & Soewandi, Hanijanto & Yao, Ming-Jong, 2001. "Chance-constrained programming in activity networks: A critical evaluation," European Journal of Operational Research, Elsevier, vol. 131(2), pages 440-458, June.
    7. Fatemi Ghomi, S. M. T. & Hashemin, S. S., 1999. "A new analytical algorithm and generation of Gaussian quadrature formula for stochastic network," European Journal of Operational Research, Elsevier, vol. 114(3), pages 610-625, May.
    8. R. Alan Bowman, 2003. "Sensitivity curves for effective project management," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(5), pages 481-497, August.
    9. Lee, Heejung & Suh, Hyo-Won, 2008. "Estimating the duration of stochastic workflow for product development process," International Journal of Production Economics, Elsevier, vol. 111(1), pages 105-117, January.
    10. Fatemi Ghomi, S. M. T. & Teimouri, E., 2002. "Path critical index and activity critical index in PERT networks," European Journal of Operational Research, Elsevier, vol. 141(1), pages 147-152, August.
    11. Bregman, Robert L., 2009. "A heuristic procedure for solving the dynamic probabilistic project expediting problem," European Journal of Operational Research, Elsevier, vol. 192(1), pages 125-137, January.
    12. Azaron, Amir & Katagiri, Hideki & Sakawa, Masatoshi & Modarres, Mohammad, 2005. "Reliability function of a class of time-dependent systems with standby redundancy," European Journal of Operational Research, Elsevier, vol. 164(2), pages 378-386, July.
    13. Daniel Reich & Leo Lopes, 2011. "Preprocessing Stochastic Shortest-Path Problems with Application to PERT Activity Networks," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 460-469, August.
    14. Azaron, Amir & Katagiri, Hideki & Sakawa, Masatoshi & Kato, Kosuke & Memariani, Azizollah, 2006. "A multi-objective resource allocation problem in PERT networks," European Journal of Operational Research, Elsevier, vol. 172(3), pages 838-854, August.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Tetsuo Iida, 2000. "Computing bounds on project duration distributions for stochastic PERT networks," Naval Research Logistics (NRL), John Wiley & Sons, vol. 47(7), pages 559-580, October.
    2. Fatemi Ghomi, S. M. T. & Hashemin, S. S., 1999. "A new analytical algorithm and generation of Gaussian quadrature formula for stochastic network," European Journal of Operational Research, Elsevier, vol. 114(3), pages 610-625, May.
    3. Fatemi Ghomi, S. M. T. & Rabbani, M., 2003. "A new structural mechanism for reducibility of stochastic PERT networks," European Journal of Operational Research, Elsevier, vol. 145(2), pages 394-402, March.
    4. Schmidt, Craig W. & Grossmann, Ignacio E., 2000. "The exact overall time distribution of a project with uncertain task durations," European Journal of Operational Research, Elsevier, vol. 126(3), pages 614-636, November.
    5. Azaron, Amir & Katagiri, Hideki & Sakawa, Masatoshi & Kato, Kosuke & Memariani, Azizollah, 2006. "A multi-objective resource allocation problem in PERT networks," European Journal of Operational Research, Elsevier, vol. 172(3), pages 838-854, August.
    6. Azaron, Amir & Katagiri, Hideki & Kato, Kosuke & Sakawa, Masatoshi, 2006. "Longest path analysis in networks of queues: Dynamic scheduling problems," European Journal of Operational Research, Elsevier, vol. 174(1), pages 132-149, October.
    7. Azaron, Amir & Fatemi Ghomi, S. M. T., 2003. "Optimal control of service rates and arrivals in Jackson networks," European Journal of Operational Research, Elsevier, vol. 147(1), pages 17-31, May.
    8. Daniel Reich & Leo Lopes, 2011. "Preprocessing Stochastic Shortest-Path Problems with Application to PERT Activity Networks," INFORMS Journal on Computing, INFORMS, vol. 23(3), pages 460-469, August.
    9. Azaron, Amir & Kianfar, Farhad, 2003. "Dynamic shortest path in stochastic dynamic networks: Ship routing problem," European Journal of Operational Research, Elsevier, vol. 144(1), pages 138-156, January.
    10. Amir Azaron & Hideki Katagiri & Masatoshi Sakawa, 2007. "Time-cost trade-off via optimal control theory in Markov PERT networks," Annals of Operations Research, Springer, vol. 150(1), pages 47-64, March.
    11. Bregman, Robert L., 2009. "A heuristic procedure for solving the dynamic probabilistic project expediting problem," European Journal of Operational Research, Elsevier, vol. 192(1), pages 125-137, January.
    12. Yongjia Song & Siqian Shen, 2016. "Risk-Averse Shortest Path Interdiction," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 527-539, August.
    13. Lee, Heejung & Suh, Hyo-Won, 2008. "Estimating the duration of stochastic workflow for product development process," International Journal of Production Economics, Elsevier, vol. 111(1), pages 105-117, January.
    14. Azaron, Amir & Katagiri, Hideki & Sakawa, Masatoshi & Modarres, Mohammad, 2005. "Reliability function of a class of time-dependent systems with standby redundancy," European Journal of Operational Research, Elsevier, vol. 164(2), pages 378-386, July.
    15. Yousry Abdelkader, 2010. "Adjustment of the moments of the project completion times when activity times are exponentially distributed," Annals of Operations Research, Springer, vol. 181(1), pages 503-514, December.
    16. Elmaghraby, Salah E., 2000. "On criticality and sensitivity in activity networks," European Journal of Operational Research, Elsevier, vol. 127(2), pages 220-238, December.
    17. Timothy M. Sweda & Irina S. Dolinskaya & Diego Klabjan, 2017. "Adaptive Routing and Recharging Policies for Electric Vehicles," Transportation Science, INFORMS, vol. 51(4), pages 1326-1348, November.
    18. Azaron, Amir & Fatemi Ghomi, S.M.T., 2008. "Lower bound for the mean project completion time in dynamic PERT networks," European Journal of Operational Research, Elsevier, vol. 186(1), pages 120-127, April.
    19. Nie, Yu (Marco) & Wu, Xing & Dillenburg, John F. & Nelson, Peter C., 2012. "Reliable route guidance: A case study from Chicago," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(2), pages 403-419.
    20. Murthy, Ishwar & Sarkar, Sumit, 1997. "Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function," European Journal of Operational Research, Elsevier, vol. 103(1), pages 209-229, November.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:matcom:v:21:y:1979:i:4:p:376-384. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/mathematics-and-computers-in-simulation/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.