IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v13y2025i2p274-d1568202.html
   My bibliography  Save this article

Comparison of Continuous-Time Partial Markov Chain Construction by Heuristic Algorithms for Purpose of Approximate Transient Analysis

Author

Listed:
  • Eimutis Valakevičius

    (Department of Mathematical Modelling, Kaunas University of Technology, Studentų g. 50, LT-44239 Kaunas, Lithuania)

  • Mindaugas Bražėnas

    (Department of Mathematical Modelling, Kaunas University of Technology, Studentų g. 50, LT-44239 Kaunas, Lithuania)

  • Tomas Ruzgas

    (Department of Applied Mathematics, Kaunas University of Technology, Studentų g. 50, LT-44239 Kaunas, Lithuania)

Abstract

We investigate the construction of a partial absorbing continuous-time Markov chain (CTMC) using a heuristic algorithm aimed at approximate transient analysis. The accuracy of transient state probabilities is indicated by the probability of absorbing state(s) at the specified time moment. A key challenge is the construction of a partial CTMC that minimizes the probability of reaching the absorbing state(s). The generation of all possible partial CTMCs is too computationally demanding, in general. Thus, we turn to investigation of heuristic algorithms that chose to include one state at a time based on limited information (i.e., the partial chain that is already constructed) and without any assumptions about the structure of the underlying CTMC. We consider three groups of such algorithms: naive, based on state characterization by the shortest path (obtained by Dijkstra method) and based on exact/approximate state probabilities. After introducing the algorithms, we discuss the problem of optimal partial CTMC construction and provide several examples. Then we compare the algorithm performance by constructing the partial CTMCs for two models: car sharing system and a randomly generated CTMC. Our obtained numerical results suggest that heuristic algorithms using state characterization via the shortest path offer a balance between accuracy and computational effort.

Suggested Citation

  • Eimutis Valakevičius & Mindaugas Bražėnas & Tomas Ruzgas, 2025. "Comparison of Continuous-Time Partial Markov Chain Construction by Heuristic Algorithms for Purpose of Approximate Transient Analysis," Mathematics, MDPI, vol. 13(2), pages 1-19, January.
    • Handle: RePEc:gam:jmathe:v:13:y:2025:i:2:p:274-:d:1568202
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/13/2/274/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/13/2/274/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Qihui Bu, 2024. "Transient Analysis for a Queuing System with Impatient Customers and Its Applications to the Pricing Strategy of a Video Website," Mathematics, MDPI, vol. 12(13), pages 1-14, June.
    2. Brameret, P.-A. & Rauzy, A. & Roussel, J.-M., 2015. "Automated generation of partial Markov chain from high level descriptions," Reliability Engineering and System Safety, Elsevier, vol. 139(C), pages 179-187.
    Full references (including those not matched with items on IDEAS)

    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. Piriou, Pierre-Yves & Faure, Jean-Marc & Lesage, Jean-Jacques, 2017. "Generalized Boolean logic Driven Markov Processes: A powerful modeling framework for Model-Based Safety Analysis of dynamic repairable and reconfigurable systems," Reliability Engineering and System Safety, Elsevier, vol. 163(C), pages 57-68.
    2. Meng, Huixing & Kloul, Leïla & Rauzy, Antoine, 2018. "Modeling patterns for reliability assessment of safety instrumented systems," Reliability Engineering and System Safety, Elsevier, vol. 180(C), pages 111-123.
    3. Pierre-Yves Piriou & Jean-Marc Faure & Jean-Jacques Lesage, 2022. "Finding the minimal cut sequences of dynamic, repairable, and reconfigurable systems from Generalized Boolean logic Driven Markov Process models," Journal of Risk and Reliability, , vol. 236(1), pages 209-220, February.
    4. Michel Batteux & Tatiana Prosvirnova & Antoine Rauzy, 2017. "AltaRica 3.0 assertions: The whys and wherefores," Journal of Risk and Reliability, , vol. 231(6), pages 691-700, December.
    5. Vinay Kumar & Neelesh Shankar Upadhye, 2025. "Modeling and simulation of first-come, first-served queueing system with impatient multiclass customers," Operational Research, Springer, vol. 25(1), pages 1-37, March.
    6. Rauzy, Antoine & Blériot-Fabre, Chaire, 2015. "Towards a sound semantics for dynamic fault trees," Reliability Engineering and System Safety, Elsevier, vol. 142(C), pages 184-191.
    7. Liang, Qingzhu & Yang, Yinghao & Zhang, Hang & Peng, Changhong & Lu, Jianchao, 2022. "Analysis of simplification in Markov state-based models for reliability assessment of complex safety systems," Reliability Engineering and System Safety, Elsevier, vol. 221(C).

    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:gam:jmathe:v:13:y:2025:i:2:p:274-:d:1568202. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.