A lagrangean heuristic for the two-stage modular capacitated facility location problem
İki seviyeli modüler kapasiteli tesis yerleşimi problemi için bir lagrange sezgiseli
- Tez No: 176880
- Danışmanlar: YRD. DOÇ. DR. SEDEF MERAL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2008
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 168
Özet
Bu çalışmada iki seviyeli modüler kapasiteli bir tesis yerleşim problemi için Lagrange gevşetimi ve altgradyan optimizasyonu tekniklerine dayanan bir Lagrange sezgiseli sunulmuştur. Problemin amacı, fabrika ve depoların yerleştirilmesi ve işletilmesi ile müşterilerin taleplerini karşılamak üzere ürünlerin fabrikalardan müşterilere taşınması sonucu ortaya çıkan maliyetlerin toplamını asgariye indirmektir. Çalışmamızın kapasiteli tesis yerleşimi probleminden farkı, her fabrika yeri seçeneği için birden fazla kapasite seviyesi seçeneğinin bulunmasıdır. Ayrıca her kapasite seviyesinin açılabilmesi için sağlanması gereken farklı bir minimum üretim kapasitesi bulunmaktadır. Açılacak bir tesis mekanı için sadece bir kapasite seviyesi belirlenebilir. Problemin ikinci seviyesinde, fabrikalardan farklı olarak her depo için sadece tek bir kapasite seviyesi vardır ve açılıp işletilebilmesi için bir sabit ve değişken maliyete sahiptir. Her iki seviyede de çok kaynaklılığa izin verilmiştir; yani bir depo birden fazla fabrikadan ürün alabilirken, aynı şekilde ikinci seviyedeki bir müşterinin talebi, gerekli durumlarda birden fazla depodan karşılanabilir.Bu çalışmada söz konusu iki seviyeli modüler kapasiteli tesis yerleşimi problemi için bir karmaşık tamsayılı programlama modeli geliştirilmiş ve sonra bu problemi etkin bir şekilde çözmek için bir Lagrange sezgiseli önerilmiştir. Bu Lagrange sezgiseli; Lagrange gevşetimi, altgradyan optimizasyonu ve üç-aşamalı bir ana sezgiselden oluşmaktadır. Lagrange sezgiselinde, Lagrange gevşetimi alt sınırı bulmakta, altgradyan optimizasyonu her yinelemede Lagrange çarpanlarını güncellemekte ve üç-aşamalı sezgisel de problemin üst sınırını bulmakta kullanılır.Üç-aşamalı sezgiselin birinci aşamasında, fabrikaların ve depoların toplam fizibiliteleri kontrol edilmekte ve toplam fizibilitenin olmaması durumunda bir açgözlü sezgisel çalıştırılmaktadır. İkinci aşamada ise tahsis sezgiseli önce müşterileri depolara ve sonra da depoları fabrikalara atamaktadır. Üst sınır sezgiselinin son aşamasında, her fabrikanın lokal fizibilitesi kontrol edilmekte ve yerel fizibilitesi olmayan fabrikaların kapasite seviyelerini ayarlamaktadır.Geliştirilen Lagrange sezgiselinin etkinliğini göstermek için rassal fakat sistematik bir biçimde oluşturulan 280 test problem örneği yaratıldı ve sezgisel yaklaşım bu örnekler üzerinde denendi. Deneylerin sonuçları, geliştirilen sezgiselin çözüm kalitesi ve hesaplama güçlüğü açısından özellikle büyük problemlerde verimli ve etkili olduğunu gösterir.
Özet (Çeviri)
In this study, a Lagrangean heuristic based on Lagrangean relaxation and subgradient optimization is proposed for the two-stage modular capacitated facility location problem. The objective is to minimize the cost of locating and operating plants and warehouses, plus the cost of transporting goods at both echelons to satisfy the demand of customers. The difference of our study from the two-stage capacitated facility location problem is the existence of multiple capacity levels as a candidate for each plant in the problem. Each capacity level has a minimum production capacity which has to be satisfied to open the relevant capacity level. Obviously, a single capacity level can be selected for an opened facility location. In the second echelon, the warehouses are capacitated and have unique fixed and variable costs for opening and operating. Multiple sourcing is allowed in both transportation echelons.Firstly, we develop a mixed integer linear programming model for the two-stage modular capacitated facility location problem. Then we develop a Lagrangean heuristic to solve the problem efficiently. Our Lagrangean heuristic consists of three main components: Lagrangean relaxation, subgradient optimization and a primal heuristic. Lagrangean relaxation is employed for obtaining the lower bound, subgradient optimization is used for updating the Lagrange multipliers at each iteration, and finally a three-stage primal heuristic is created for generating the upper bound solutions.At the first stage of the upper bound heuristic, global feasibility of the plants and warehouses is inspected and a greedy heuristic is executed, if there is a global infeasibility. At the next stage, an allocation heuristic is used to assign customers to warehouses and warehouses to plants sequentially. At the final stage of the upper bound heuristic, local feasibilities of the plants are investigated and infeasible capacity levels are adjusted if necessary.In order to show the efficiency of the developed heuristic, we have tested our heuristic on 280 problem instances generated randomly but systematically. The results of the experiments show that the developed heuristic is efficient and effective in terms of solution quality and computational effort especially for large instances.
Benzer Tezler
- Disaster mitigation and humanitarian relief logistics
Afet zararlarını azaltma ve insani yardım malzemeleri lojistiği
ALPER DÖYEN
Doktora
İngilizce
2012
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. GÜLAY BARBAROSOĞLU
PROF. NECATİ ARAS
- A Heuristic algorithm for the multi-item capacitated lotsizing problem
Başlık çevirisi yok
SİBEL TARMAN
Yüksek Lisans
İngilizce
1991
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiPROF.DR. GÜNDÜZ ULUSOY
- Bicriteria scheduling of unit processing time jobs on a single machine
Birim işlem zamanlı işlerin tek makinada iki ölçütlü çizelgelenmesi
ELİF EMRE
Yüksek Lisans
İngilizce
1994
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. SUNA KONDAKÇI KÖKSALAN
- Optimal server placement, service deployment, and resource allocation in next-generation computer networks
Yeni nesil bilgisayar ağlarında sunucu yerleştirme, servis dağıtımı ve kaynak tahsisi eniyilemesi
BETÜL AKTEL
Doktora
İngilizce
2022
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA NECATİ ARAS
PROF. DR. İSMAİL KUBAN ALTINEL
- Kesme ve yükleme problemleri için lagrange fonksiyonları temelli çözüm yöntemleri
Lagrange function based solution methods for cutting and packing problems
BANU İÇMEN ERDEM
Doktora
Türkçe
2021
Endüstri ve Endüstri MühendisliğiEskişehir Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. REFAİL KASIMBEYLİ