Tez No İndirme Tez Künye Durumu
268430
Multi resource agent bottleneck generalized assignment problem / Darboğaz çok kaynaklı genelleştirilmiş atama problemi
Yazar:ÖZLEM KARABULUT
Danışman: PROF. DR. MERAL AZİZOĞLU
Yer Bilgisi: Orta Doğu Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Bölümü
Konu:Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin:
Onaylandı
Yüksek Lisans
İngilizce
2010
136 s.
Bu çalışmada, Darboğaz Çok Kaynaklı Genelleştirilmiş Atama Problemi ele alınmıştır. Amacımız, temsilcilere dönemler üzerinden atanan en büyük toplam iş yükünü enazlamaktır.Problemin doğrusal programlama gevşetmesini çalıştık. Optimal doğrusal programlama gevşetmesi çözümlerini önerdiğimiz dal-sınır yönteminde alt ve üst sınır ve dallandırma yöntemini belirlemekte kullandık. Dal-sınır yöntemimizin büyüklüğü temsilci sayısı 5 iken 60 işe ve temsilci sayısı 10 iken 30 işe kadar olan problemleri 20 dakikadan daha kısa sürede çözdüğünü gördük.Yaklaşık çözümler bulmak için, bir tabu arama algoritması ve ? yaklaşıklama algoritması geliştirdik. Deneylerimizin sonuçları bu yöntemlerin büyük boyuttaki problemlere kısa sürede yüksek kaliteli çözümler bulduğunu göstermiştir.
In this thesis, we consider the Multi Resource Agent Bottleneck Generalized Assignment Problem. We aim to minimize the maximum load over all agents.We study the Linear Programming (LP) relaxation of the problem. We use the optimal LP relaxation solutions in our Branch and Bound algorithm while defining lower and upper bounds and branching schemes. We find that our Branch and Bound algorithm returns optimal solutions to the problems with up to 60 jobs when the number of agents is 5, and up to 30 jobs when the number of agents is 10, in less than 20 minutes.To find approximate solutions, we define a tabu search algorithm and an ? approximation algorithm. Our computational results have revealed that these procedures can find high quality solutions to large sized instances very quickly.