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

A Kronecker Algebra Formulation for Markov Activity Networks with Phase-Type Distributions

Author

Listed:
  • Alessio Angius

    (Enerbrain, 10132 Turin, Italy)

  • András Horváth

    (Computer Science Department, University of Turin, 10149 Turin, Italy)

  • Marcello Urgo

    (Mechanical Engineering Department, Polytechnic University of Milan, 20133 Milan, Italy)

Abstract

The application of theoretical scheduling approaches to the real world quite often crashes into the need to cope with uncertain events and incomplete information. Stochastic scheduling approaches exploiting Markov models have been proposed for this class of problems with the limitation to exponential durations. Phase-type approximations provide a tool to overcome this limitation. This paper proposes a general approach for using phase-type distributions to model the execution of a network of activities with generally distributed durations through a Markov chain. An analytical representation of the infinitesimal generator of the Markov chain in terms of Kronecker algebra is proposed, providing a general formulation for this class of problems and supporting more efficient computation methods. This entails the capability to address stochastic scheduling in terms of the estimation of the distribution of common objective functions (i.e., makespan, lateness), enabling the use of risk measures to address robustness.

Suggested Citation

  • Alessio Angius & András Horváth & Marcello Urgo, 2021. "A Kronecker Algebra Formulation for Markov Activity Networks with Phase-Type Distributions," Mathematics, MDPI, vol. 9(12), pages 1-22, June.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:12:p:1404-:d:576533
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/12/1404/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/12/1404/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Golenko-Ginzburg, Dimitri & Gonik, Aharon, 1997. "Stochastic network project scheduling with non-consumable limited resources," International Journal of Production Economics, Elsevier, vol. 48(1), pages 29-37, January.
    2. Creemers, Stefan, 2018. "Maximizing the expected net present value of a project with phase-type distributed activity durations: An efficient globally optimal solution procedure," European Journal of Operational Research, Elsevier, vol. 267(1), pages 16-22.
    3. Stefan Creemers, 2018. "Maximizing the expected net present value of a project with phase-type distributed activity durations: An efficient globally optimal solution procedure," Post-Print hal-02572114, HAL.
    4. George B. Kleindorfer, 1971. "Bounding Distributions for a Stochastic Acyclic Network," Operations Research, INFORMS, vol. 19(7), pages 1586-1601, December.
    5. Stefan Creemers, 2015. "Minimizing the expected makespan of a project with stochastic activity durations under resource constraints," Working Papers of Department of Decision Sciences and Information Management, Leuven 488396, KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven.
    6. Sobel, Matthew J. & Szmerekovsky, Joseph G. & Tilson, Vera, 2009. "Scheduling projects with stochastic activity duration to maximize expected net present value," European Journal of Operational Research, Elsevier, vol. 198(3), pages 697-705, November.
    7. Alessio Angius & András Horváth & Sami M. Halawani & Omar Barukab & Ab Rahman Ahmad & Gianfranco Balbo, 2014. "Constructing Matrix Exponential Distributions by Moments and Behavior around Zero," Mathematical Problems in Engineering, Hindawi, vol. 2014, pages 1-13, December.
    8. Arnold H. Buss & Meir J. Rosenblatt, 1997. "Activity Delay in Stochastic Project Networks," Operations Research, INFORMS, vol. 45(1), pages 126-139, February.
    9. Tsai, Ying-Wei & D. Gemmill, Douglas, 1998. "Using tabu search to schedule activities of stochastic resource-constrained projects," European Journal of Operational Research, Elsevier, vol. 111(1), pages 129-141, November.
    10. D. G. Malcolm & J. H. Roseboom & C. E. Clark & W. Fazar, 1959. "Application of a Technique for Research and Development Program Evaluation," Operations Research, INFORMS, vol. 7(5), pages 646-669, October.
    11. V. G. Kulkarni & V. G. Adlakha, 1986. "Markov and Markov-Regenerative pert Networks," Operations Research, INFORMS, vol. 34(5), pages 769-781, October.
    12. Stefan Creemers, 2015. "Minimizing the expected makespan of a project with stochastic activity durations under resource constraints," Post-Print hal-02992649, HAL.
    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. Lei Liu & Marcello Urgo, 2024. "Robust scheduling in a two-machine re-entrant flow shop to minimise the value-at-risk of the makespan: branch-and-bound and heuristic algorithms based on Markovian activity networks and phase-type dis," Annals of Operations Research, Springer, vol. 338(1), pages 741-764, July.
    2. Sun, Tianqi & Vatn, Jørn, 2024. "A phase-type maintenance model considering condition-based inspections and maintenance delays," Reliability Engineering and System Safety, Elsevier, vol. 243(C).

    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. Hazır, Öncü & Ulusoy, Gündüz, 2020. "A classification and review of approaches and methods for modeling uncertainty in projects," International Journal of Production Economics, Elsevier, vol. 223(C).
    2. Öncü Hazir & Gündüz Ulusoy, 2020. "A classification and review of approaches and methods for modeling uncertainty in projects," Post-Print hal-02898162, HAL.
    3. Creemers, Stefan, 2018. "Maximizing the expected net present value of a project with phase-type distributed activity durations: An efficient globally optimal solution procedure," European Journal of Operational Research, Elsevier, vol. 267(1), pages 16-22.
    4. Rostami, Salim & Creemers, Stefan & Leus, Roel, 2024. "Maximizing the net present value of a project under uncertainty: Activity delays and dynamic policies," European Journal of Operational Research, Elsevier, vol. 317(1), pages 16-24.
    5. Stefan Creemers, 2019. "The preemptive stochastic resource-constrained project scheduling problem," Post-Print hal-02992618, HAL.
    6. Salim Rostami & Stefan Creemers & Roel Leus, 2018. "New strategies for stochastic resource-constrained project scheduling," Journal of Scheduling, Springer, vol. 21(3), pages 349-365, June.
    7. Bruni, Maria Elena & Hazır, Öncü, 2024. "A risk-averse distributionally robust project scheduling model to address payment delays," European Journal of Operational Research, Elsevier, vol. 318(2), pages 398-407.
    8. Hermans, Ben & Leus, Roel & Looy, Bart Van, 2023. "Deciding on scheduling, secrecy, and patenting during the new product development process: The relevance of project planning models," Omega, Elsevier, vol. 116(C).
    9. Creemers, Stefan, 2019. "The preemptive stochastic resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 277(1), pages 238-247.
    10. Peymankar, Mahboobeh & Davari, Morteza & Ranjbar, Mohammad, 2021. "Maximizing the expected net present value in a project with uncertain cash flows," European Journal of Operational Research, Elsevier, vol. 294(2), pages 442-452.
    11. Szmerekovsky, Joseph G. & Venkateshan, Prahalad & Simonson, Peter D., 2023. "Project scheduling under the threat of catastrophic disruption," European Journal of Operational Research, Elsevier, vol. 309(2), pages 784-794.
    12. Creemers, Stefan & De Reyck, Bert & Leus, Roel, 2015. "Project planning with alternative technologies in uncertain environments," European Journal of Operational Research, Elsevier, vol. 242(2), pages 465-476.
    13. Sobel, Matthew J. & Szmerekovsky, Joseph G. & Tilson, Vera, 2009. "Scheduling projects with stochastic activity duration to maximize expected net present value," European Journal of Operational Research, Elsevier, vol. 198(3), pages 697-705, November.
    14. Vaseghi, Forough & Martens, Annelies & Vanhoucke, Mario, 2024. "Analysis of the impact of corrective actions for stochastic project networks," European Journal of Operational Research, Elsevier, vol. 316(2), pages 503-518.
    15. Illana Bendavid & Boaz Golany, 2009. "Setting gates for activities in the stochastic project scheduling problem through the cross entropy methodology," Annals of Operations Research, Springer, vol. 172(1), pages 259-276, November.
    16. Illana Bendavid & Boaz Golany, 2011. "Setting gates for activities in the stochastic project scheduling problem through the cross entropy methodology," Annals of Operations Research, Springer, vol. 189(1), pages 25-42, September.
    17. Eli Gutin & Daniel Kuhn & Wolfram Wiesemann, 2015. "Interdiction Games on Markovian PERT Networks," Management Science, INFORMS, vol. 61(5), pages 999-1017, May.
    18. Masoud Arjmand & Amir Abbas Najafi & Majid Ebrahimzadeh, 2020. "Evolutionary algorithms for multi-objective stochastic resource availability cost problem," OPSEARCH, Springer;Operational Research Society of India, vol. 57(3), pages 935-985, September.
    19. Wiesemann, Wolfram & Kuhn, Daniel & Rustem, Berç, 2010. "Maximizing the net present value of a project under uncertainty," European Journal of Operational Research, Elsevier, vol. 202(2), pages 356-367, April.
    20. Bruni, M.E. & Di Puglia Pugliese, L. & Beraldi, P. & Guerriero, F., 2017. "An adjustable robust optimization model for the resource-constrained project scheduling problem with uncertain activity durations," Omega, Elsevier, vol. 71(C), pages 66-84.

    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:9:y:2021:i:12:p:1404-:d:576533. 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.