Bibliographic Details
| Title: |
A STOCHASTIC PROGRAMMING APPROACH TO THE SINGLE MACHINE MAKESPAN PROBLEM WITH RANDOM BREAKDOWNS. |
| Alternate Title: |
RASTGELE ARIZALARIN OLDUĞU TEK MAKİNE TAMAMLAMA SÜRESİ PROBLEMİ İÇİN STOKASTİK PROGRAMLAMA YAKLAŞIMI. |
| Authors: |
GÜREL, Tarık1, AZİZOĞLU, Meral2 ma@metu.edu.tr, BATUN, Sakine2 |
| Source: |
Journal of Industrial Engineering (Turkish Chamber of Mechanical Engineers). 2026, Vol. 37 Issue 1, p210-240. 31p. |
| Subjects: |
Stochastic programming, Branch & bound algorithms, Machine part failures, Scheduling, Simulation methods & models, Production scheduling |
| Abstract (English): |
We study the single-machine scheduling problem with non-resumable jobs under random machine breakdowns, where the objective is to minimize the expected makespan. The breakdown occurrence time is modelled using a set of discrete scenarios, each characterized by a breakdown time and an associated probability, and at most one breakdown can occur within the planning horizon. To solve the problem, we propose two alternative two- stage stochastic programming formulations: a precedence-based model and a position-based model, which differ in how sequencing decisions are represented in the first stage. Due to the computational complexity of these formulations, we develop an exact branch-and-bound algorithm that incorporates an effective branching rule and two lower bounding schemes tailored to the breakdown structure. The results of the computational experiments show that stochastic programming models can optimally solve small-sized instances with up to 10 jobs, while the proposed branch-and-bound algorithm can solve instances with up to 200 jobs and 5 scenarios within reasonable times. Moreover, the stochastic solutions consistently outperform their deterministic expected-value counterparts. [ABSTRACT FROM AUTHOR] |
| Abstract (Turkish): |
Rastgele makine arızaları altında, kesintiye uğratılamayan işlerin bulunduğu tek makineli çizelgeleme problemini inceliyoruz; amaç, beklenen tamamlanma süresini en aza indirmektir. Arızanın gerçekleşme zamanı, her biri bir arıza zamanı ve buna karşılık gelen bir olasılık ile tanımlanan ayrık senaryolar aracılığıyla modellenmekte olup, planlama ufku içinde en fazla bir arızaya izin verilmektedir. Problemi çözmek için, iki alternatif iki aşamalı stokastik programlama modeli öneriyoruz: bir öncelik-tabanlı model ve bir pozisyon-tabanlı model. Bu iki model, birinci aşamadaki sıralama kararlarının nasıl temsil edildiği açısından birbirinden ayrılmaktadır. Bu modellerin hesaplama karmaşıklığı nedeniyle, arıza yapısına özel etkili bir dallanma kuralı ve iki alt sınır yöntemi içeren kesin bir dal-ve-sınır algoritması geliştiriyoruz. Deney sonuçları, stokastik programlama modellerinin 10 işe kadar olan küçük boyutlu problemleri optimal olarak çözebildiğini; önerilen dal ve sınır algoritmasının ise 200 işe ve 5 senaryoya kadar olan örnekleri makul süreler içinde çözebildiğini göstermektedir. Ayrıca, stokastik çözümler, deterministik beklenen-değer karşılıklarına kıyasla tutarlı biçimde daha iyi performans sergilemektedir. [ABSTRACT FROM AUTHOR] |
|
Copyright of Journal of Industrial Engineering (Turkish Chamber of Mechanical Engineers) is the property of Turkish Chamber of Mechanical Engineers and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
