IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v247y2022ics0925527322000482.html
   My bibliography  Save this article

Evaluation of VaR and CVaR for the makespan in interval valued blocking job shops

Author

Listed:
  • Meloni, Carlo
  • Pranzo, Marco
  • Samà, Marcella

Abstract

The paper deals with the job shop scheduling problem with complex blocking constraints (BJSS) under uncertainties. It proposes a method for the evaluation of the risk that the makespan of a deterministic feasible schedule assumes worse extreme values, considering uncertain activity durations represented by intervals. An interval-valued network approach is proposed to model the feasible solutions characterized by uncertain values for jobs’ releases, processing and setup times. The study assumes the Value-at-Risk (VaR) and the Conditional Value-at-Risk (CVaR) as risk measures for the makespan of the feasible solutions, and addresses both modeling and computational issues. They include the implementation and test of a network-based model used with an innovative algorithm for the first time applied to complex BJSS problems to provide an accurate, rapid and viable computation of both risk indices. The impact of different sources of uncertainty (including setups, releases and processing times) on the overall performance of the proposed approach are analyzed. The results of a wide experimental campaign show that the method, for both the computational time and the quality of the evaluations, has broad applicability. It can support the decision-makers for a wide range of practical scheduling cases taking into account their risk sensibility.

Suggested Citation

  • 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).
    • Handle: RePEc:eee:proeco:v:247:y:2022:i:c:s0925527322000482
    DOI: 10.1016/j.ijpe.2022.108455
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925527322000482
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ijpe.2022.108455?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. Sotskov, Y. & Sotskova, N. Y. & Werner, F., 1997. "Stability of an optimal schedule in a job shop," Omega, Elsevier, vol. 25(4), pages 397-414, August.
    2. 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.
    3. Nicholas G. Hall & Chelliah Sriskandarajah, 1996. "A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process," Operations Research, INFORMS, vol. 44(3), pages 510-525, June.
    4. John W. Fowler & Lars Mönch & Oliver Rose, 2006. "Scheduling and Simulation," International Series in Operations Research & Management Science, in: Jeffrey W. Herrmann (ed.), Handbook of Production Scheduling, chapter 0, pages 109-133, Springer.
    5. Jeffrey W. Herrmann, 2006. "Decision-Making Systems in Production Scheduling," International Series in Operations Research & Management Science, in: Jeffrey W. Herrmann (ed.), Handbook of Production Scheduling, chapter 0, pages 91-108, Springer.
    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. 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).
    8. Mascis, Alessandro & Pacciarelli, Dario, 2002. "Job-shop scheduling with blocking and no-wait constraints," European Journal of Operational Research, Elsevier, vol. 143(3), pages 498-517, December.
    9. Romero-Silva, Rodrigo & Hernández-López, Gabriel, 2020. "Shop-floor scheduling as a competitive advantage: A study on the relevance of cyber-physical systems in different manufacturing contexts," International Journal of Production Economics, Elsevier, vol. 224(C).
    10. Abdelhakim AitZai & Mourad Boudhar, 2013. "Parallel branch-and-bound and parallel PSO algorithms for job shop scheduling problem with blocking," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 16(1), pages 14-37.
    11. Kenneth N. McKay & Vincent C. S. Wiers, 2006. "The Human Factor in Planning and Scheduling," International Series in Operations Research & Management Science, in: Jeffrey W. Herrmann (ed.), Handbook of Production Scheduling, chapter 0, pages 23-57, Springer.
    12. Kim, S. C. & Bobrowski, P. M., 1997. "Scheduling jobs with uncertain setup times and sequence dependency," Omega, Elsevier, vol. 25(4), pages 437-447, August.
    13. Sterna, Małgorzata, 2021. "Late and early work scheduling: A survey," Omega, Elsevier, vol. 104(C).
    14. 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.
    15. Garcia-Gonzalez, Javier & Parrilla, Ernesto & Mateo, Alicia, 2007. "Risk-averse profit-based optimal scheduling of a hydro-chain in the day-ahead electricity market," European Journal of Operational Research, Elsevier, vol. 181(3), pages 1354-1369, September.
    16. Jian Zhang & Guofu Ding & Yisheng Zou & Shengfeng Qin & Jianlin Fu, 2019. "Review of job shop scheduling research and its new perspectives under Industry 4.0," Journal of Intelligent Manufacturing, Springer, vol. 30(4), pages 1809-1830, April.
    17. 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.
    18. Joseph Adams & Egon Balas & Daniel Zawack, 1988. "The Shifting Bottleneck Procedure for Job Shop Scheduling," Management Science, INFORMS, vol. 34(3), pages 391-401, March.
    19. 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.
    20. 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.
    21. Pham, Dinh-Nguyen & Klinkert, Andreas, 2008. "Surgical case scheduling as a generalized job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1011-1025, March.
    22. L Liao & S C Sarin & H D Sherali, 2012. "A scenario generation-based lower bounding approach for stochastic scheduling problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 63(10), pages 1410-1420, October.
    23. Julia Lange & Frank Werner, 2018. "Approaches to modeling train scheduling problems as job-shop problems with blocking constraints," Journal of Scheduling, Springer, vol. 21(2), pages 191-207, April.
    24. Batur, D. & Choobineh, F., 2010. "A quantile-based approach to system selection," European Journal of Operational Research, Elsevier, vol. 202(3), pages 764-772, May.
    25. Daniel Alejandro Rossit & Fernando Tohmé & Mariano Frutos, 2019. "Industry 4.0: Smart Scheduling," International Journal of Production Research, Taylor & Francis Journals, vol. 57(12), pages 3802-3813, June.
    26. 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.
    27. 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.
    28. Sterna, Malgorzata, 2011. "A survey of scheduling problems with late work criteria," Omega, Elsevier, vol. 39(2), pages 120-129, April.
    29. Mogali, Jayanth Krishna & Barbulescu, Laura & Smith, Stephen F., 2021. "Efficient primal heuristic updates for the blocking job shop problem," European Journal of Operational Research, Elsevier, vol. 295(1), pages 82-101.
    30. 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.
    31. 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.
    32. Shi Qiang Liu & Erhan Kozan, 2011. "Scheduling Trains with Priorities: A No-Wait Blocking Parallel-Machine Job-Shop Scheduling Model," Transportation Science, INFORMS, vol. 45(2), pages 175-198, May.
    33. Heckmann, Iris & Comes, Tina & Nickel, Stefan, 2015. "A critical review on supply chain risk – Definition, measure and modeling," Omega, Elsevier, vol. 52(C), pages 119-132.
    34. Icaro Romolo Sousa Agostino & Wesley Vieira da Silva & Claudimar Pereira da Veiga & Adriano Mendonça Souza, 2020. "Forecasting models in the manufacturing processes and operations management: Systematic literature review," Journal of Forecasting, John Wiley & Sons, Ltd., vol. 39(7), pages 1043-1056, November.
    35. 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.
    36. Levner, Eugene & Kats, Vladimir & Levit, Vadim E., 1997. "An improved algorithm for cyclic flowshop scheduling in a robotic cell," European Journal of Operational Research, Elsevier, vol. 97(3), pages 500-508, March.
    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. 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.
    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. 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.
    4. Mogali, Jayanth Krishna & Barbulescu, Laura & Smith, Stephen F., 2021. "Efficient primal heuristic updates for the blocking job shop problem," European Journal of Operational Research, Elsevier, vol. 295(1), pages 82-101.
    5. Jayanth Krishna Mogali & Joris Kinable & Stephen F. Smith & Zachary B. Rubinstein, 2021. "Scheduling for multi-robot routing with blocking and enabling constraints," Journal of Scheduling, Springer, vol. 24(3), pages 291-318, June.
    6. Gabriel Mauricio Zambrano-Rey & Eliana María González-Neira & Gabriel Fernando Forero-Ortiz & María José Ocampo-Monsalve & Andrea Rivera-Torres, 2024. "Minimizing the expected maximum lateness for a job shop subject to stochastic machine breakdowns," Annals of Operations Research, Springer, vol. 338(1), pages 801-833, July.
    7. Samà, Marcella & D’Ariano, Andrea & D’Ariano, Paolo & Pacciarelli, Dario, 2017. "Scheduling models for optimal aircraft traffic control at busy airports: Tardiness, priorities, equity and violations considerations," Omega, Elsevier, vol. 67(C), pages 81-98.
    8. Allahverdi, Ali, 2016. "A survey of scheduling problems with no-wait in process," European Journal of Operational Research, Elsevier, vol. 255(3), pages 665-686.
    9. Dauzère-Pérès, Stéphane & Ding, Junwen & Shen, Liji & Tamssaouet, Karim, 2024. "The flexible job shop scheduling problem: A review," European Journal of Operational Research, Elsevier, vol. 314(2), pages 409-432.
    10. 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.
    11. Zhu, Jie & Li, Xiaoping & Wang, Qian, 2009. "Complete local search with limited memory algorithm for no-wait job shops to minimize makespan," European Journal of Operational Research, Elsevier, vol. 198(2), pages 378-386, October.
    12. Abdelhakim AitZai & Brahim Benmedjdoub & Mourad Boudhar, 2016. "Branch-and-bound and PSO algorithms for no-wait job shop scheduling," Journal of Intelligent Manufacturing, Springer, vol. 27(3), pages 679-688, June.
    13. Mina Aliakbari & Joseph Geunes, 2022. "Multiple Train Repositioning Operations in a Railyard Network," SN Operations Research Forum, Springer, vol. 3(4), pages 1-31, December.
    14. Neil Geismar, H. & Dawande, Milind & Sriskandarajah, Chelliah, 2005. "Approximation algorithms for k-unit cyclic solutions in robotic cells," European Journal of Operational Research, Elsevier, vol. 162(2), pages 291-309, April.
    15. Jacomine Grobler & Andries Engelbrecht & Schalk Kok & Sarma Yadavalli, 2010. "Metaheuristics for the multi-objective FJSP with sequence-dependent set-up times, auxiliary resources and machine down time," Annals of Operations Research, Springer, vol. 180(1), pages 165-196, November.
    16. Chen, Xin & Miao, Qian & Lin, Bertrand M.T. & Sterna, Malgorzata & Blazewicz, Jacek, 2022. "Two-machine flow shop scheduling with a common due date to maximize total early work," European Journal of Operational Research, Elsevier, vol. 300(2), pages 504-511.
    17. 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.
    18. Diarmuid Grimes & Emmanuel Hebrard, 2015. "Solving Variants of the Job Shop Scheduling Problem Through Conflict-Directed Search," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 268-284, May.
    19. Lin, Shih-Wei & Ying, Kuo-Ching, 2013. "Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm," Omega, Elsevier, vol. 41(2), pages 383-389.
    20. Andrea D’Ariano & Marco Pranzo, 2009. "An Advanced Real-Time Train Dispatching System for Minimizing the Propagation of Delays in a Dispatching Area Under Severe Disturbances," Networks and Spatial Economics, Springer, vol. 9(1), pages 63-84, 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:eee:proeco:v:247:y:2022:i:c:s0925527322000482. 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.elsevier.com/locate/ijpe .

    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.