SavedAdd your journal

Journals / Endüstri Mühendisliği / 2026 / Cilt: 37 Sayı: 1

A STOCHASTIC PROGRAMMING APPROACH TO THE SINGLE MACHINE MAKESPAN PROBLEM WITH RANDOM BREAKDOWNS

TEK MAKİNE MAKESPAN PROBLEMİNE RASTGELE ARIZALARLA STOKASTİK PROGRAMLAMA YAKLAŞIMI

Taık Gürel(ORTA DOĞU TEKNİK ÜNİVERSİTESİ)0000-0000-0000-0000
Meral Azizoğlu(ORTA DOĞU TEKNİK ÜNİVERSİTESİ, MÜHENDİSLİK FAKÜLTESİ, ENDÜSTRİ MÜHENDİSLİĞİ BÖLÜMÜ)0000-0000-0000-0001
Sakine Batun(ORTA DOĞU TEKNİK ÜNİVERSİTESİ)0000-0002-7503-8172
Pages
210–240
Publication Date
2026-04-22
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

Our computational results show that the stochastic programming models are effective for solving small-sized instances, while the branch-and-bound algorithm efficiently solves medium-sized instances within reasonable computation time.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:In this study, we address the single-machine makespan scheduling problem under random breakdowns.
📊
Key Findings & Data:To improve the performance of the branch-and-bound algorithm, we incorporate an efficient branching scheme and strong lower bounds.
💡
Conclusion & Impact:Our computational results show that the stochastic programming models are effective for solving small-sized instances, while the branch-and-bound algorithm efficiently solves medium-sized instances within reasonable computation time.
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Tek Makine · Makespan · Rastgele Bozulma

Abstract

In this study, we address the single-machine makespan scheduling problem under random breakdowns. Our objective is to minimize the expected makespan, and to this end, we propose a stochastic programming approach. We develop two-stage stochastic programming models and a branch-and-bound algorithm. To improve the performance of the branch-and-bound algorithm, we incorporate an efficient branching scheme and strong lower bounds. Our computational results show that the stochastic programming models are effective for solving small-sized instances, while the branch-and-bound algorithm efficiently solves medium-sized instances within reasonable computation time.

Özet

Bu çalışmada, rastgele arızalar altında tek makine makespan planlama problemini ele alıyoruz. Amacımız beklenen makespan'ı minimize etmektir ve bunun için bir stokastik programlama yaklaşımı öneriyoruz. İki aşamalı stokastik programlama modelleri ve bir dal-ve-sınır algoritması geliştiriyoruz. Dal-ve-sınır algoritmasının performansını iyileştirmek için verimli alt sınırlar entegre ediyoruz. Deneysel sonuçlarımız, stokastik programlama modellerinin küçük ölçekli örnekler için etkili olduğunu, dal-ve-sınır algoritmasının ise orta ölçekli örnekleri makul bir çözüm süresi içinde çözdüğünü göstermektedir.

🔖

Cite This Article

Gürel, T., Azizoğlu, M., Batun, S. (2026). A STOCHASTIC PROGRAMMING APPROACH TO THE SINGLE MACHINE MAKESPAN PROBLEM WITH RANDOM BREAKDOWNS. Endüstri Mühendisliği, Cilt: 37 Sayı: 1, 210–240. https://doi.org/10.46465/endustrimuhendisligi.1833014

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (29)

  1. Abdul Halim, N. N., Shariff, S. S., & Zahari, S. M. (2020). Single machine integrated production preventive maintenance scheduling: A simheuristic approach. Matematika, 36(2), 113–126. Doi: https://doi.org/10.11113/ matematika.v36.n2.1168.
  2. Al-Khamis, T., & M’Hallah, R. (2011). A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity. Computers & Operations Research, 38(12), 1747–1757. Doi: https://doi.org/10.1016/j.cor.2011.01.017.
  3. Atakan, S., Bülbül, K., & Noyan, N. (2016). Minimizing value-at-risk in single machine scheduling. Annals of Operations Research, 248(1–2), 25–73. Doi: https://doi.org/10.1007/s10479-016-2251-z.
  4. Batun, S., & Azizoğlu, M. (2009). Single machine scheduling with preventive maintenances. International Journal of Production Research, 47(7), 1753–1771. Doi: https://doi.org/10.1080/00207540701636348.
  5. Birge, J. R., & Louveaux, F. (2011). Introduction to stochastic programming. New York, NY: Springer. Cassady, C. R., & Kutanoglu, E. (2005). Integrating preventive maintenance planning and production scheduling for a single machine. IEEE Transactions on Reliability, 54(2), 304–309. Doi: https://doi.org/10.1109/TR.2005.845967.
  6. Chen, W. (2009). Minimizing number of tardy jobs on a single machine subject to periodic maintenance. Omega, 37(3), 591–599. Doi: https://doi.org/ 10.1016/j.omega.2008.02.003.
  7. Chen, Y., Huang, C., Chou, F. D., & Huang, S. (2020). Single-machine scheduling problem with flexible maintenance and non-resumable jobs to minimise makespan. IET Collaborative Intelligent Manufacturing, 2(4), 174–181. Doi: https://doi.org/10.1049/iet-cim.2020.0014.
  8. Dasgupta, S., Papadimitriou, C. H., & Vazirani, U. V. (2008). Algorithms. New York, NY: McGraw-Hill.
  9. Liu, M., Wang, S., Chu, C., & Chu, F. (2015). An improved exact algorithm for single-machine scheduling to minimise the number of tardy jobs with periodic maintenance. International Journal of Production Research, 54(12), 3591–3602. Doi: https://doi.org/10.1080/00207543.2015.1108535.
  10. Low, C., Ji, M., Hsu, C.-J., & Su, C.-T. (2010). Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance. Applied Mathematical Modelling, 34(2), 334–342. Doi: https://doi.org/10.1016/j.apm.2009.04.014.
  11. Özçelik, F., Ertem, M., & Saraç, T. (2021). A stochastic approach for the single-machine scheduling problem to minimize total expected cost with client-dependent tardiness costs. Engineering Optimization, 54(7), 1178–1192. Doi: https://doi.org/10.1080/0305215X.2021.1919098.
  12. Pan, E., Liao, W., & Xi, L. (2010). Single-machine-based production scheduling model integrated preventive maintenance planning. The International Journal of Advanced Manufacturing Technology, 50(1–4), 365–375. Doi: https://doi.org/10.1007/s00170-009-2514-9.
  13. van den Akker, M., Hoogeveen, H., & Stoef, J. (2018). Combining two-stage stochastic programming and recoverable robustness to minimize the number of late jobs in the case of uncertain processing times. Journal of Scheduling, 21(6), 607–617. Doi:https://doi.org/10.1007/s10951-018-0559-z.
  14. Wang, S., & Liu, M. (2013). A branch and bound algorithm for single-machine production scheduling integrated with preventive maintenance planning. International Journal of Production Research, 51(3), 847–868. Doi: https://doi.org/10.1080/00207543.2012.676683.
  15. Wu, H., & Zheng, H. (2023). Single-machine scheduling with periodic maintenance and learning effect. Scientific Reports, 13(1). Doi: https://www.nature.com/articles/s41598-023-36056-w.
  16. Abdul Halim, N. N., Shariff, S. S., & Zahari, S. M. (2020). Single machine integrated production preventive maintenance scheduling: A simheuristic approach. Matematika, 36(2), 113–126. Doi: https://doi.org/10.11113/ matematika.v36.n2.1168.
  17. Al-Khamis, T., & M’Hallah, R. (2011). A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity. Computers & Operations Research, 38(12), 1747–1757. Doi: https://doi.org/10.1016/j.cor.2011.01.017.
  18. Atakan, S., Bülbül, K., & Noyan, N. (2016). Minimizing value-at-risk in single machine scheduling. Annals of Operations Research, 248(1–2), 25–73. Doi: https://doi.org/10.1007/s10479-016-2251-z.
  19. Batun, S., & Azizoğlu, M. (2009). Single machine scheduling with preventive maintenances. International Journal of Production Research, 47(7), 1753–1771. Doi: https://doi.org/10.1080/00207540701636348.
  20. Birge, J. R., & Louveaux, F. (2011). Introduction to stochastic programming. New York, NY: Springer. Cassady, C. R., & Kutanoglu, E. (2005). Integrating preventive maintenance planning and production scheduling for a single machine. IEEE Transactions on Reliability, 54(2), 304–309. Doi: https://doi.org/10.1109/TR.2005.845967.
  21. Chen, W. (2009). Minimizing number of tardy jobs on a single machine subject to periodic maintenance. Omega, 37(3), 591–599. Doi: https://doi.org/ 10.1016/j.omega.2008.02.003.
  22. Chen, Y., Huang, C., Chou, F. D., & Huang, S. (2020). Single-machine scheduling problem with flexible maintenance and non-resumable jobs to minimise makespan. IET Collaborative Intelligent Manufacturing, 2(4), 174–181. Doi: https://doi.org/10.1049/iet-cim.2020.0014.
  23. Liu, M., Wang, S., Chu, C., & Chu, F. (2015). An improved exact algorithm for single-machine scheduling to minimise the number of tardy jobs with periodic maintenance. International Journal of Production Research, 54(12), 3591–3602. Doi: https://doi.org/10.1080/00207543.2015.1108535.
  24. Low, C., Ji, M., Hsu, C.-J., & Su, C.-T. (2010). Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance. Applied Mathematical Modelling, 34(2), 334–342. Doi: https://doi.org/10.1016/j.apm.2009.04.014.
  25. Özçelik, F., Ertem, M., & Saraç, T. (2021). A stochastic approach for the single-machine scheduling problem to minimize total expected cost with client-dependent tardiness costs. Engineering Optimization, 54(7), 1178–1192. Doi: https://doi.org/10.1080/0305215X.2021.1919098.
  26. Pan, E., Liao, W., & Xi, L. (2010). Single-machine-based production scheduling model integrated preventive maintenance planning. The International Journal of Advanced Manufacturing Technology, 50(1–4), 365–375. Doi: https://doi.org/10.1007/s00170-009-2514-9.
  27. van den Akker, M., Hoogeveen, H., & Stoef, J. (2018). Combining two-stage stochastic programming and recoverable robustness to minimize the number of late jobs in the case of uncertain processing times. Journal of Scheduling, 21(6), 607–617. Doi:https://doi.org/10.1007/s10951-018-0559-z.
  28. Wang, S., & Liu, M. (2013). A branch and bound algorithm for single-machine production scheduling integrated with preventive maintenance planning. International Journal of Production Research, 51(3), 847–868. Doi: https://doi.org/10.1080/00207543.2012.676683.
  29. Wu, H., & Zheng, H. (2023). Single-machine scheduling with periodic maintenance and learning effect. Scientific Reports, 13(1). Doi: https://www.nature.com/articles/s41598-023-36056-w.