Event and clock based representations of time in mathematical optimization
Matematiksel eniyilemede zamanın olay ve saat tabanlı gösterimi
- Tez No: 356940
- Danışmanlar: PROF. DR. İSMAİL KUBAN ALTINEL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Zamanın gösterimi işlem süresi ve verim açısından matematiksel programlamada en önemli konulardan biridir. Kesikli zaman gösterimi problemlerin çözüm süresini etkileyen pek çok sayıda ikili değişken içermektedir. Zamanın geleneksel eş uzunluklu aralıklar kullanılarak kesiklenmesi yerine, olay tabanlı gösterim uzun zaman planına sahip örnekler için önerilmektedir. Olay tabanlı yaklaşımda, olaylar dizgede değişiklik yaratan durumlardır ve matematiksel model bu olay noktalarına göre kurulur. Bu çalışmada ilk olarak iki yaklaşımın temel özelliklerini gözden geçirdik ve her iki yaklaşımın artı ve eksilerini özetledik. Daha sonra iki problemin olay tabanlı gösterimlenmesine odaklandık: kablosuz duygaç ağlarında yer seçimi-çizelgeleme ve rıhtım paylaştırma problemlemleri. Olay tabanlı gösterimi değişik problemlerde uygulamak üzere genelleştirmeye çalıştık ve geliştirmek için güçlendirici kısıtlar önerdik. Son olarak, modelleri olaylara göre ayrıştıran yeni bir dal-eder algoritması geliştirdik. Olağan gösterimin doğrusal program gevşetmesinden daha iyi olan bir sınır bulsa da, dal-eder algoritmasının başarımı sınırlıdır. Ayrıca iyi olurlu sonuçlar elde etmek için basit sezgisel yöntemler de önerdik. Deneylerimizde, her iki yaklaşımı bir karışık tam sayılı programlama çözücüsü ile çözerek karşılaştırdık ve dal-eder algoritmasının doğruluğunu sınadık. Deneylerimize göre, genel olarak olay tabanlı gösterim daha az çözüm süresine gereksinmektedir. Ancak, en iyi çözümü veren olay sayısını bulmak bilgisayısal anlamda çok emek isteyen bir iştir. Karar verici en iyi gösterimi her iki yaklaşımın artı ve eksilerini çözmek istediği problem özelinde karşılaştırarak seçmelidir.
Özet (Çeviri)
Time representation is one of the most important issues in mathematical optimization in terms of computational time and efficiency. The discrete time formulation requires large number of binary variables which affects the solution time of the problems. Instead of relying on the traditional uniform discretization of the time horizon, the event-based formulations are proposed to deal with the instances that have a long horizon. In the event-based approach, events are the situations that cause a change in the system and mathematical model is constructed based on the events. In this study, first, we briefly review the main characteristics of the two approaches and outline their advantages and disadvantages. Then, we focus on the event-based formulations of the two problems: location and scheduling problem (LASP) in wireless sensor networks (WSN) and berth allocation problem (BAP). We try to generalize the event-based formulations for different types of problems. In order to enhance the event-based formulations, we strengthen the constraints. Finally, we propose a branch and price algorithm by decomposing the models based on events. Although it provides bounds, which are better than the linear programming relaxation of original formulation, the branch and price algorithm is not very efficient. We also propose simple heuristics to find good feasible solutions. In our experiments, we compare two modeling approaches by solving the formulations using a state-of-the-art solver on the generated test bed. Then, we assess the performance of the branch and price algorithm. According to our experiments, generally the event-based formulations require less computational time. However, finding an optimum event number can require considerable computational effort. The decision maker should choose the best representation of time based on the advantages and disadvantages of the two approaches.
Benzer Tezler
- Gömülü sistemlerde sesli komut tanıma
Voice command recognation in embedded systems
CAN ÇETİN
Yüksek Lisans
Türkçe
2020
Mekatronik Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
PROF. DR. MUSTAFA DOĞAN
- Ege bölgesi keçi liflerinin bazı önemli fiziksel, kimyasal özellikleri ve değerlendirme imkanları
Başlık çevirisi yok
NİLÜFER ERDEM
Doktora
Türkçe
1985
Tekstil ve Tekstil MühendisliğiEge ÜniversitesiTekstil Mühendisliği Ana Bilim Dalı
PROF. DR. GÜLSEREN YAZICIOĞLU
- Karıştırıcılar ve karıştırma kabındaki akım olaylarının incelenmesi
Başlık çevirisi yok
NADİR İLTEN
Yüksek Lisans
Türkçe
1986
Makine MühendisliğiUludağ ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
DOÇ.DR. ÖMER SAMİH MERTBAŞ
- 1,3-difenil-4,5-bis(hidroksiimino)-imidazolidin ve Ni(II), Cu(II), Pd(II), UO2(VI) komplekslerinin sentezi
Başlık çevirisi yok
VEFA AHSEN
Doktora
Türkçe
1984
Kimya MühendisliğiUludağ ÜniversitesiKimya Mühendisliği Ana Bilim Dalı
PROF. DR. ÖZER BEKAROĞLU
- Tekstil boyamacılığında atık flottede boyama imkanları üzerine araştırma
Başlık çevirisi yok
MEHMET YAKARTEPE
Yüksek Lisans
Türkçe
1985
Tekstil ve Tekstil MühendisliğiEge ÜniversitesiTekstil Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. KERİM DURAN