IDEAS home Printed from https://ideas.repec.org/a/spr/flsman/v32y2020i3d10.1007_s10696-019-09358-3.html
   My bibliography  Save this article

Expected shortfall for the makespan in activity networks under imperfect information

Author

Listed:
  • Carlo Meloni

    (Politecnico di Bari)

  • Marco Pranzo

    (Università di Siena)

Abstract

This paper deals with the evaluation of the expected shortfall or the conditional value-at-risk for the makespan in scheduling problems represented as temporal networks under incomplete and uncertain information. We consider temporal activity network representations of scheduling problems affected by uncertainties related to the activity durations and we assume that for these uncertainties only incomplete or imperfect information is available. More precisely, for each activity only the interval for its integer valued duration is known to the scheduler. We address the evaluation of the expected shortfall associated to a feasible schedule discussing its importance in scheduling applications. We propose lower and upper bounds, heuristics to determine a fast computational estimation of the expected shortfall, and an exact method for a class of activity networks. The experimental results show that the proposed method can enable to use the expected shortfall as optimization criterion for wide classes of scheduling approaches considering risk-aversion in different practical contexts.

Suggested Citation

  • Carlo Meloni & Marco Pranzo, 2020. "Expected shortfall for the makespan in activity networks under imperfect information," Flexible Services and Manufacturing Journal, Springer, vol. 32(3), pages 668-692, September.
    • Handle: RePEc:spr:flsman:v:32:y:2020:i:3:d:10.1007_s10696-019-09358-3
    DOI: 10.1007/s10696-019-09358-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10696-019-09358-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10696-019-09358-3?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. Michael H. Rothkopf, 1966. "Scheduling with Random Service Times," Management Science, INFORMS, vol. 12(9), pages 707-713, May.
    2. Sabuncuoglu, I. & Bayiz, M., 2000. "Analysis of reactive scheduling problems in a job shop environment," European Journal of Operational Research, Elsevier, vol. 126(3), pages 567-586, November.
    3. Hartmann, Sonke & Kolisch, Rainer, 2000. "Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 127(2), pages 394-407, December.
    4. Elmaghraby, Salah E., 1990. "Project bidding under deterministic and probabilistic activity durations," European Journal of Operational Research, Elsevier, vol. 49(1), pages 14-34, November.
    5. Bertsimas, Dimitris & Lauprete, Geoffrey J. & Samarov, Alexander, 2004. "Shortfall as a risk measure: properties, optimization and applications," Journal of Economic Dynamics and Control, Elsevier, vol. 28(7), pages 1353-1381, April.
    6. Elmaghraby, Salah E., 2005. "On the fallacy of averages in project risk management," European Journal of Operational Research, Elsevier, vol. 165(2), pages 307-313, September.
    7. D. R. Fulkerson, 1962. "Expected Critical Path Lengths in PERT Networks," Operations Research, INFORMS, vol. 10(6), pages 808-817, December.
    8. Carlo Meloni & Dario Pacciarelli & Marco Pranzo, 2004. "A Rollout Metaheuristic for Job Shop Scheduling Problems," Annals of Operations Research, Springer, vol. 131(1), pages 215-235, October.
    9. Liangyan Tao & Desheng Dash Wu & Sifeng Liu & Alexandre Dolgui, 2018. "Optimal due date quoting for a risk-averse decision-maker under CVaR," International Journal of Production Research, Taylor & Francis Journals, vol. 56(5), pages 1934-1959, March.
    10. James E. Kelley, 1961. "Critical-Path Planning and Scheduling: Mathematical Basis," Operations Research, INFORMS, vol. 9(3), pages 296-320, June.
    11. Catalão, J.P.S. & Pousinho, H.M.I. & Contreras, J., 2012. "Optimal hydro scheduling and offering strategies considering price uncertainty and risk management," Energy, Elsevier, vol. 37(1), pages 237-244.
    12. Kolisch, Rainer & Hartmann, Sonke, 2006. "Experimental investigation of heuristics for resource-constrained project scheduling: An update," European Journal of Operational Research, Elsevier, vol. 174(1), pages 23-37, October.
    13. Marco Pranzo & Dario Pacciarelli, 2016. "An iterated greedy metaheuristic for the blocking job shop scheduling problem," Journal of Heuristics, Springer, vol. 22(4), pages 587-611, August.
    14. Chanas, Stefan & Zielinski, Pawel, 2002. "The computational complexity of the criticality problems in a network with interval activity times," European Journal of Operational Research, Elsevier, vol. 136(3), pages 541-550, February.
    15. Chang, Zhiqi & Song, Shiji & Zhang, Yuli & Ding, Jian-Ya & Zhang, Rui & Chiong, Raymond, 2017. "Distributionally robust single machine scheduling with risk aversion," European Journal of Operational Research, Elsevier, vol. 256(1), pages 261-274.
    16. Semih Atakan & Kerem Bülbül & Nilay Noyan, 2017. "Minimizing value-at-risk in single-machine scheduling," Annals of Operations Research, Springer, vol. 248(1), pages 25-73, January.
    17. De, Prabuddha & Ghosh, Jay B. & Wells, Charles E., 1992. "Expectation-variance analyss of job sequences under processing time uncertainty," International Journal of Production Economics, Elsevier, vol. 28(3), pages 289-297, December.
    18. Rune Larsen & Marco Pranzo, 2019. "A framework for dynamic rescheduling problems," International Journal of Production Research, Taylor & Francis Journals, vol. 57(1), pages 16-33, January.
    19. Herroelen, Willy & Leus, Roel, 2005. "Project scheduling under uncertainty: Survey and research potentials," European Journal of Operational Research, Elsevier, vol. 165(2), pages 289-306, September.
    20. Hartmann, Sönke & Kolisch, R., 2000. "Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 11180, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    21. Thomas B. Crabill & William L. Maxwell, 1969. "Single machine sequencing with random processing times and random due‐dates," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 16(4), pages 549-554, December.
    22. Richard L. Daniels & Panagiotis Kouvelis, 1995. "Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production," Management Science, INFORMS, vol. 41(2), pages 363-376, February.
    23. T-C Lai & Y N Sotskov, 1999. "Sequencing with uncertain numerical data for makespan minimisation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(3), pages 230-243, March.
    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. Meloni, Carlo & Pranzo, Marco & Samà, Marcella, 2022. "Evaluation of VaR and CVaR for the makespan in interval valued blocking job shops," International Journal of Production Economics, Elsevier, vol. 247(C).
    2. Meloni, Carlo & Pranzo, Marco & Samà, Marcella, 2021. "Risk of delay evaluation in real-time train scheduling with uncertain dwell times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(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. Meloni, Carlo & Pranzo, Marco & Samà, Marcella, 2022. "Evaluation of VaR and CVaR for the makespan in interval valued blocking job shops," International Journal of Production Economics, Elsevier, vol. 247(C).
    2. Meloni, Carlo & Pranzo, Marco & Samà, Marcella, 2021. "Risk of delay evaluation in real-time train scheduling with uncertain dwell times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    3. Hartmann, Sönke & Briskorn, Dirk, 2010. "A survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 1-14, November.
    4. Zhu, Xia & Ruiz, Rubén & Li, Shiyu & Li, Xiaoping, 2017. "An effective heuristic for project scheduling with resource availability cost," European Journal of Operational Research, Elsevier, vol. 257(3), pages 746-762.
    5. Hartmann, Sönke & Briskorn, Dirk, 2008. "A survey of variants and extensions of the resource-constrained project scheduling problem," Working Paper Series 02/2008, Hamburg School of Business Administration (HSBA).
    6. Hartmann, Sönke & Briskorn, Dirk, 2022. "An updated survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 297(1), pages 1-14.
    7. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    8. Weglarz, Jan & Józefowska, Joanna & Mika, Marek & Waligóra, Grzegorz, 2011. "Project scheduling with finite or infinite number of activity processing modes - A survey," European Journal of Operational Research, Elsevier, vol. 208(3), pages 177-205, February.
    9. Cédric Verbeeck & Vincent Peteghem & Mario Vanhoucke & Pieter Vansteenwegen & El-Houssaine Aghezzaf, 2017. "A metaheuristic solution approach for the time-constrained project scheduling problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(2), pages 353-371, March.
    10. F. Perez & T. Gomez, 2016. "Multiobjective project portfolio selection with fuzzy constraints," Annals of Operations Research, Springer, vol. 245(1), pages 7-29, October.
    11. Adam Kasperski & Paweł Zieliński, 2019. "Risk-averse single machine scheduling: complexity and approximation," Journal of Scheduling, Springer, vol. 22(5), pages 567-580, October.
    12. Van Peteghem, Vincent & Vanhoucke, Mario, 2014. "An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances," European Journal of Operational Research, Elsevier, vol. 235(1), pages 62-72.
    13. Lova, Antonio & Tormos, Pilar & Cervantes, Mariamar & Barber, Federico, 2009. "An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes," International Journal of Production Economics, Elsevier, vol. 117(2), pages 302-316, February.
    14. Grzegorz Waligóra, 2016. "Comparative Analysis of Some Metaheuristics for Discrete-Continuous Project Scheduling with Activities of Identical Processing Rates," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(03), pages 1-32, June.
    15. Zhenyuan Liu & Lei Xiao & Jing Tian, 2016. "An activity-list-based nested partitions algorithm for resource-constrained project scheduling," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4744-4758, August.
    16. Trietsch, Dan & Mazmanyan, Lilit & Gevorgyan, Lilit & Baker, Kenneth R., 2012. "Modeling activity times by the Parkinson distribution with a lognormal core: Theory and validation," European Journal of Operational Research, Elsevier, vol. 216(2), pages 386-396.
    17. Guo, Weikang & Vanhoucke, Mario & Coelho, José, 2023. "A prediction model for ranking branch-and-bound procedures for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 579-595.
    18. Rodrigues, Sávio B. & Yamashita, Denise S., 2010. "An exact algorithm for minimizing resource availability costs in project scheduling," European Journal of Operational Research, Elsevier, vol. 206(3), pages 562-568, November.
    19. Evgeny Gafarov & Alexander Lazarev & Frank Werner, 2014. "Approximability results for the resource-constrained project scheduling problem with a single type of resources," Annals of Operations Research, Springer, vol. 213(1), pages 115-130, February.
    20. Peteghem, Vincent Van & Vanhoucke, Mario, 2010. "A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 201(2), pages 409-418, March.

    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:spr:flsman:v:32:y:2020:i:3:d:10.1007_s10696-019-09358-3. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.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.