Generating robust and stable machine schedules from a proactive standpoint
Proaktif bir bakış açısından gürbüz ve kararlı makine çizelgeleri oluşturulması
- Tez No: 246730
- Danışmanlar: PROF. DR. İHSAN SABUNCUOĞLU
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Çizelgeleme, Scheduling
- Yıl: 2009
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Bölümü
- Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Özet
Endüstride kullanılan çizelgeleme sistemleri işletme ortamlarındaki şartlar gereği ciddi miktarda değişkenlik ve belirsizlik etkisi altında çalışmaktadırlar. Çizelgeleme sırasında karşılaşılabilecek çeşitli belirsizliklerle baş edebilme niteliği günümüz koşullarında giderek önem kazanmaktadır. Bu tez çalışmasında proaktif bir yaklaşımla iki çeşit belirsizlik etkisindeki (işlem süresi değişkenliği ve makine arızalanması) ortamlarda gürbüz ve kararlı çizelgeler üretilmesi problemleri ele alınmaktadır. Belirsizlik hakkındaki bilgi, olasılık dağılımları aracılığıyla modellenmekte ve olasılık kuramı kullanılarak sistem hakkında çeşitli çıkarımlara ulaşılmaktadır.İlk olarak tek makineli bir ortam ele alınmaktadır. İki gürbüzlük (beklenen toplam akış zamanı ve beklenen toplam gecikme) ve üç kararlılık (iş tamamlanma zamanları arasındaki farkların kareleri ve mutlak değerleri toplamı, iş tamamlanma zamanlarının toplam varyansı) ölçütü tanımlanmakta, bu ölçütlerin fazla zorlukla karşılaşmadan eniyilenebileceği özel durumlar tespit edilmektedir. Gürbüzlük ölçütlerinden biri için bir üstünlük kuralı, iki alt sınır ve problemi çözmek için bunları kullanan bir dal-sınır algoritması geliştirilmiştir. Her beş ölçüt için de büyük boyuttaki problemleri çözmek için kullanılabilecek bir demet taraması sezgiseli geliştirilmiş, kapsamlı sayısal deneylerle geliştirilen yöntemlerin performansları incelenmiştir.Çalışılan ikinci problem tek makine ortamında kararlık ve gürbüzlüğün eşzamanlı eniyilenmesidir, Bütün Pareto optimum noktaları üreten bir epsilon-kısıt yöntemi incelenmektir. Yöntemin gereksinim duyduğu alt problemler formüle edilmiş ve hesapsal karmaşıklıkları tespit edilmiştir. Yöntemin sadece tek bir cins alt probleme ihtiyaç duyan iki varyasyonu ele alınmış, bu varyasyonlardan birini güçlendirecek bir üstünlük kuralı ve bu kuralın değişik formülasyonları geliştirilmiştir. Önerilen tekniklerin performansları deneysel bir çalışmayla değerlendirilmiştir. Üretilen toplam nokta sayısını sınırlandırırken, noktaların dağılımını mümkün olduğunca eşit aralıklı tutacak bir yaklaşım da önerilmiştir.Son olarak, işlem süresi değişkenliği ve rassal makine arızalanmalarına maruz atölye tipi işliklerde kararlı çizelgelerin oluşturulması problemi ele alınmaktadır. Kullanılan kararlılık ölçütü, iş tamamlanma zamanlarının varyansları toplamıdır. Bu problem NP sınıfında olmadığından vekil bir kararlılık ölçütü kullanılmıştır. Problemin bu halinin, makine arızalanmaları göz ardı edilse bile, NP?zor olduğu gösterilmiş ve tam çözüm yöntemi olarak iki dal-sınır algoritması geliştirilmiştir. Makine arızalanmalarını göz önüne alan ve büyük boyutlu örnekleri çözebilen biri demet taraması ve diğeri tabu araması olmak üzere iki sezgisel yöntem geliştirilmiştir. Geliştirilen yöntemler kapsamlı hesapsal deneylerle test edilmiştir.
Özet (Çeviri)
In practice, scheduling systems are subject to considerable uncertainty in highly dynamic operating environments. The ability to cope with uncertainty in the scheduling process is becoming an increasingly important issue. In this thesis we take a proactive approach to generate robust and stable schedules for the environments with two sources of uncertainty: processing time variability and machine breakdowns. The information about the uncertainty is modeled using cumulative distribution functions and probability theory is utilized to derive inferences.We first focus on the single machine environment. We define two robustness (expected total flow time and expected total tardiness) and three stability (the sum of the squared and absolute differences of the job completion times and the sum of the variances of the realized completion times) measures. We identify special cases for which the measures can be optimized without much difficulty. We develop a dominance rule and two lower bounds for one of the robustness measures, which are employed in a branch-and-bound algorithm to solve the problem exactly. We also propose a beam-search heuristic to solve large problems for all five measures. We provide extensive discussion of our numerical results.Next, we study the problem of optimizing both robustness and stability simultaneously. We generate the set of all Pareto optimal points via epsilon-constraint method. We formulate the sub-problems required by the method and establish their computational complexity status. Two variants of the method that works with only a single type of sub-problem are also considered. A dominance rule and alternative ways to enforce the rule to strengthen one of these versions are discussed. The performance of the proposed technique is evaluated with an experimental study. An approach to limit the total number of generated points while keeping their spread uniform is also proposed.Finally, we consider the problem of generating stable schedules in a job shop environment with processing time variability and random machine breakdowns. The stability measure under consideration is the sum of the variances of the realized completion times. We show that the problem is not in the class NP. Hence, a surrogate stability measure is developed to manage the problem. This version of the problem is proven to be NP-hard even without machine breakdowns. Two branch-and-bound algorithms are developed for this case. A beam-search and a tabu-search based two heuristic algorithms are developed to handle realistic size problems with machine breakdowns. The results of extensive computational experiments are also provided.
Benzer Tezler
- Güç transformatörleri sfra tarama frekans cevabı analizi sonuçlarının yapay zeka uygulamaları ile karşılaştırılması
Comparison of power transformer sfra sweep frequency response analysis results with artificial intelligence applications
HAKAN ÇUHADAROĞLU
Doktora
Türkçe
2025
Elektrik ve Elektronik MühendisliğiSakarya ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. YILMAZ UYAROĞLU
- How cryptographic implementations affect mobile agent systems
Şifreleme gerçekleştirmelerinin gezgin aracı internet sistemlerini nasıl etkilediği
İSMAİL ULUKUŞ
Yüksek Lisans
İngilizce
2003
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolBoğaziçi ÜniversitesiSistem ve Kontrol Mühendisliği Ana Bilim Dalı
PROF. DR. EMİN ANARIM
- Hasta aciliyet seviyesinin belirlenmesi için büyük dil modeli ve makine öğrenmesi tabanlı akıllı triyaj sistemi
An intelligent triage system for hospital emergency services based on large language models and machine learning
OMAR SAEED
Yüksek Lisans
Türkçe
2026
BiyomühendislikErciyes ÜniversitesiBiyomedikal Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET EMİN YÜKSEL
- Gelişmiş makine öğrenmesi ile sermaye piyasalarında kısa vadeli yön tahmini ve dinamik TP/SL analizi
Short-term direction forecasting in capital markets with advanced machine learning and dynamic TP/SL analysis
EMRE ARI
Doktora
Türkçe
2026
İstatistikİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ALP ÜSTÜNDAĞ
- Veri madenciliğinde eksik verilerin doldurulmasında makine öğrenmesi yöntemlerinin karşılaştırmalı analizi ve özgün bir model önerisi
Comparative evaluation of machine learning imputation methods in data mining with the proposal of a novel model
ÜMİT TERZİOĞLU
Yüksek Lisans
Türkçe
2026
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDicle ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. CAFER BUDAK