Deterministic and stochastic models for practical scheduling problems
Uygulamalı çizelgeleme problemleri için deterministik ve stokastik modeller
- Tez No: 744471
- Danışmanlar: PROF. DR. ALAN SCHELLER-WOLF
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, İşletme, Industrial and Industrial Engineering, Business Administration
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2012
- Dil: İngilizce
- Üniversite: Carnegie Mellon University
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: İşletme Yönetimi Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği ve İşletme Yönetimi Bilim Dalı
- Sayfa Sayısı: 170
Özet
Bu tez, gerçek yaşam durumlarının motive ettiği üç çizelgeleme problemini analiz eder. Birçok imalat ve hizmet endüstrisinde, çizelgeleme önemli bir karar verme sürecidir. Ne yazık ki, çizelgeleme problemlerinin çözülmesi genellikle hesaplama açısından zordur ve bir çizelgeleme problemini modellemek bile zor olabilir. Bölüm 2, zaman pencereli işlere sahip uzun zaman ufkuna sahip tek makine, bölünmeler olmayan çizelgeleme problemlerini ele almaktadır. Bu problemleri çözmek için kısıtlı programlamayı (CP) ve karma tamsayılı doğrusal programlamayı (MILP) hibrit bir yöntemde, mantık tabanlı Benders ayrıştırması, birleştiriyorum. Problemi takip edilebilir kılmak için önce uzun zaman ufkunu bölümlere ayırıyorum. Bu, tek makine çizelgeleme probleminin iki versiyonuna yol açıyor: bölümlere ayrılmış ve bölümlere ayrılmamış. Bölümlere ayrılmış problemde, her iş bir zaman diliminde tamamlanmalıdır. Bölümlere ayrılmamış problemde ise işler iki veya daha fazla zaman parçası gerektirebilir. Farklı amaç fonksiyonlarını analiz ettim ve ilgili Benders kesimlerini tanıttım. Bölümlere ayrılmış problem için mantık tabanlı Benders ayrıştırmasının her zaman üstün olduğunu ve baştan kullanılması gerektiğini buldum. Bölümlere ayrılmamış problem için, mantık tabanlı Benders ayrıştırmasının mutlaka en hızlı yöntem olmadığını, ancak açıkça en sağlam olduğunu buldum. Bu nedenle, önce CP'yi uygulama stratejisini ve birkaç saniye içinde problemi çözemezse, mantık tabanlı Benders ayrıştırmasına geçmeyi öneriyorum. Bölüm 3, büyük bir bilgi teknolojisi hizmetleri dağıtım organizasyonundan esinlenerek, çapraz eğitimli temsilciler, heterojen müşteriler ve kalite garantileri içeren bir hizmet merkezinde personel sorununa değinmektedir. Temsilciler ya yüksek ya da düşük vasıflıdır ve hem karmaşıklıkları hem de öncelikleri bakımından heterojen olan müşteri isteklerine hizmet ederler: (i) Daha yüksek öncelikli müşteri talepleri, kuyruktaki daha düşük öncelikli müşteri isteklerinin servislerini bölebilirler; ve (ii) Daha az yetenekli temsilciler yalnızca düşük karmaşıklıktaki taleplere hizmet verebilirken, yüksek vasıflı temsilciler ise her türlü isteğe hizmet edebilir. Bu servis merkezinin işlemlerini, bir önceliklendirmeye dayalı bölme servis disiplini altında çok sunuculu bir kuyruk kullanarak ele aldım ve bunu bir Markov zinciri olarak modelledim. Daha sonra, farklı kontrol politikalarını değerlendirmek için yaklaşıklık ve sınırlama teknikleri uyguladım: Sistemdeki her bir istek sınıfının sayısına göre istekleri önceliklendiren eşik tabanlı öncelik politikaları sınıfını dikkate alırım. Yöntemimiz ile dört farklı müşteri talebi türü başarılı bir şekilde analiz edilebilir: simülasyona kıyasla yöntemimizin doğru ve hızlı olduğunu gösterdim. Ayrıca, eşiklerin nasıl belirleneceği, müşterilerle maliyetlerin nasıl görüşüleceği ve hangi temsilci karışımının işe alınacağı gibi servis merkezindeki kapasite sağlama sorunu hakkında yönetimsel bilgiler de sağlanabilmektedir. Eşik tabanlı politikaların basit ama etkili olabileceğini ve servis merkezinde herhangi bir değişiklik yapmadan toplam maliyeti azaltabileceğini gösterdim. Bölüm 4'te, bir projenin görev veya kesintilerinin sürelerinin ve projelerin varışlarının belirsiz olduğu, çapraz eğitimli ajanlar, heterojen projeler ve kalite garantileri içeren bir proje çizelgeleme problemini analiz ettim. Bu sorun, büyük, küresel bir bilgi işlem servis sağlayacısının servis merkezindeki gerçek bir sorundan esinlenmiştir. Gerçek verilerin analizi, sistemdeki belirsizliği yakalamak için görev süreleri ve işlem sürelerindeki gecikmeleri dikkate almanın yeterli olduğunu göstermektedir. Amaç, her temsilci için sağlam ve etkili bir atama ve görev çizelgesi bulmaktır. Belirsizliğin, en az olası sonuçları içermeyebilecek bir belirsizlik kümesi tarafından yakalandığı, mantık tabanlı Benders ayrıştırmasına dayalı gürbüz bir zamanlama modeli geliştirdim. Daha sonra bu gürbüz çizelgeleme modelini ispatladığım dışbükeylik teoremi ile sadeleştirdim. Bölüm 4, belirsizliğin bir belirsizlik seti ile temsil edildiği yeni bir gürbüz çizelgeleme modeli sunarak çizelgeleme literatürüne katkıda bulunur. Ayrıca çokyüzlü belirsizlik kümeleri altında mantık tabanlı Benders ayrıştırmasını basitleştirdim. Bildiğimiz kadarıyla, bu, belirsizlik kümeleri ile gürbüz optimizasyon kullanarak belirsizlik içeren bir proje çizelgeleme problemini çözen ilk çalışmadır. Tezim, üç uygulamalı çizelgeleme problemi için deterministik ve stokastik modeller hakkındaki bilgimizi genişletmektedir. Bildiğimiz kadarıyla, ikinci bölüm, mantık tabanlı Benders ayrıştırmasıyla saf bir çizelgeleme problemini (herhangi bir yan kısıtlama dahil) çözmeye yönelik ilk girişimdir. Üçüncü bölümde, çapraz eğitimli temsilciler, heterojen müşteriler ve kalite garantileri ile bir hizmet merkezinin operasyonları için yönetimsel öngörüler sağlamak için bir yaklaşım yöntemine katkıda bulundum. Mevcut sayısal deneyler, yaklaşım yönteminin doğru ve hızlı olduğunu göstermektedir. Bölüm 4'te, bir servis merkezinin kesintiler, çapraz eğitimli temsilciler, heterojen projeler ve kalite garantileri içeren operasyonlarını yakalamak için yeni bir gürbüz proje çizelgeleme modeline katkıda bulundum. Gelecekte bu problem alanlarının her birinde yapılacak çok iş bulunmaktadır, ancak bu tezin bulgularının benzer, hatta daha karmaşık problemler üzerine gelecekteki çalışmalara rehberlik edeceğinden eminim.
Özet (Çeviri)
This dissertation analyzes three scheduling problems motivated by real life situations. In many manufacturing and service industries, scheduling is an important decision-making process. Unfortunately, scheduling problems are often computationally challenging to solve, and even modeling a scheduling problem can be difficult. Chapter 2 considers single-facility non-preemptive scheduling problems with long time horizons having jobs with time windows (i.e., release times and due dates). I combine constraint programming (CP) and mixed integer linear programming (MILP) using a hybrid method: logic-based Benders decomposition. I first divide the long time horizon into segments to make the problem tractable. This gives rise to two versions of the single-facility scheduling problem: segmented and unsegmented. In the segmented problem, each job must be completed within one time segment. In the unsegmented problem, jobs can overlap two or more segments. I analyze different objective functions, and introduce relevant Benders cuts. I find that for the segmented problem, logic-based Benders decomposition is always superior and should be used from the start. For the unsegmented problem, I find that logic-based Benders decomposition is not necessarily the fastest method, but clearly the most robust. Hence, I suggest a strategy of applying CP first, and if it fails to solve the problem within a few seconds, switching to logic-based Benders decomposition. Chapter 3 addresses the problem of staffing in a service center with cross-trained agents, heterogeneous customers, and quality guarantees, inspired by a large IT services delivery organization. Agents are either high or low skilled, and serve customer requests that are also heterogeneous - with respect to both their complexity and their priority: (i) Higher priority customer requests preempt lower priority customer requests in the queue; and (ii) Less skilled agents can only service low complexity requests, while highly skilled agents can service all types of requests. I capture this service center's operations using a multi-server queue under a preemptive-resume priority service discipline, and model it as a Markov chain. I then apply approximation and bounding techniques to evaluate different control policies: I consider the class of threshold-based priority policies that prioritize the requests according to the number of each class of requests in the system. Four different types of customer requests can be successfully analyzed by our method: our method is accurate and fast when compared to simulation. I also provide managerial insights about the capacity provisioning problem at the service center, such as how to set thresholds, how to negotiate costs with customers, and what mix of agents to hire. I demonstrate that threshold-based policies can be simple but effective, and that they might decrease the total cost without any changes in the service center. In Chapter 4, I analyze a project scheduling problem with disruptions, cross-trained agents, heterogeneous projects and quality guarantees where the durations of a project's tasks/disruptions and the arrivals of the projects are uncertain. This problem is inspired by a real problem at a large, global SDO's service center. Analysis of real data shows that considering delays in the release times and processing times are sufficient to capture the uncertainty in the system. The goal is to find a robust and effective assignment and schedule of tasks for each agent. I develop a robust scheduling model based on logic-based Benders decomposition, in which uncertainty is captured by an uncertainty set which might not include the least likely outcomes. Then, I simplify this robust scheduling model by the convexity theorem I prove. Chapter 4 contributes to the scheduling literature by introducing a novel robust scheduling model in which the uncertainty is represented by an uncertainty set. I also simplify logic-based Benders decomposition under polyhedral uncertainty sets. To the best of our knowledge, this is the first work solving a project scheduling problem with uncertainty using robust optimization with uncertainty sets. My dissertation widens our knowledge of deterministic and stochastic models for three practical scheduling problems. To our knowledge, the second chapter is the first attempt to solve a pure scheduling problem (including any side constraints) with logic-based Benders decomposition. In the third chapter, I contribute an approximation method to provide managerial insights for a service center's operations with cross-trained agents, heterogeneous customers and quality guarantees. Current numerical experiments show that the approximation method is accurate and fast. In Chapter 4, I contribute a novel robust project scheduling model to capture an SDO's service center's operations with disruptions, cross-trained agents, heterogeneous projects and quality guarantees. There is much future work to be done in each of these problem domains but I am confident that the findings of this dissertation will guide future studies on similar, or even more complex problems.
Benzer Tezler
- Bulanık çok modlu kaynak kısıtlı proje çizelgeleme problemlerinin çözümü için matematiksel bir model
A mathematical model for the solution of the fuzzy multi mode resource-constrained project scheduling problems
ÖMER ATLI
Doktora
Türkçe
2012
Endüstri ve Endüstri MühendisliğiHava Harp Okulu KomutanlığıEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. CENGİZ KAHRAMAN
- GT yöntemlerinin sınıflandırması, performans ölçütleri, üretimle ilgili verileri kullanan yeni yöntemlere örnekler ve genetik algoritmalar
Taxonomy of GT methods, performance measures,some new GT methods that is able to incorporate pertinent manufacturing data and genetic algorithms
HATİCE DERİCİ
Yüksek Lisans
Türkçe
1997
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. M. BÜLENT DURMUŞOĞLU
- Comprehensive risk mapping and fire station optimization for forest fire management: An application in Antalya
Orman yangını yönetimi için kapsamlı risk haritalama ve yangın istasyonu optimizasyonu: Antalya uygulaması
ZÜHAL ÖZCAN YAVUZ
Doktora
İngilizce
2024
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ÖZGÜR KABAK
DR. ÖĞR. ÜYESİ İNCİ ÇAĞLAYAN
- Mechanics of nanomaterials consisted of random networks
Rastgele ağ yapılı nano malzemelerin mekaniği
MESUT KIRCA
Doktora
İngilizce
2013
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. ATA MUGAN
YRD. DOÇ. DR. ALBERT C. TO