Developing and applying multi-threaded metaheuristic policies to solve combinatorial industrial engineering problems
Endüstri mühendisliğindeki kombinatoryal optimizasyon problemlerinin çözümü için çoklu iş parçacıklı metasezgisel politikalar geliştirilmesi ve uygulanması
- Tez No: 790614
- Danışmanlar: PROF. DR. SEROL BULKAN, PROF. DR. ÖZLEM ŞENVAR
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2023
- Dil: İngilizce
- Üniversite: Marmara Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: 99
Özet
Kombinatoryal Optimizasyon Problemleri (KOP) hayatımızı kolaylaştırmakta önemli bir role sahiptir. Bu problemlerin birçoğu gerçek hayat durumlarına dayalı olarak ortayı çıkmıştır. Bu özellikleri KOP'nin rağbet görmesini ve faydalarını açıklamaktadır. Genelleyici yapıda olmaları sayesinde KOP farklı tipte birçok probleme adapte edilebilir. Örneğin, meşhur Gezgin Satıcı Problemi nakliye planlaması, baskı devre delme işlemi, geniş ambarlarda malzeme taşıma ve navigasyon yardımı gibi sayısız uygulamaya sahiptir. Uygulamaların eniyilenmesinde kritik bir role sahip olmakla birlikte KOP birçok durumda NP (Polinomiyel Olmayan)-Tam ya da NP-Zor karmaşıklık seviyesi ile çözümü zor problemlerdir. Bu nedenle KOP'nin çözümüne yönelik olarak çeşitli yaklaşıklık ve metasezgisel algoritmalar önerilmiştir. Bu tezde, metasezgisel algoritmalar için çoklu iş parçacıklı politika geliştirme yöntemlerini tespit edebilmek için literatürde yer alan metasezgisel algoritma paralelleştirme ve çoklu iş parçacıkları ile çalıştırma yöntemleri incelendi. Klasik Benzetilmiş Tavlama algoritması temel alınarak Benzetilmiş Tavlama Çoklu İş Parçacıklı (Simulated Annealing MultiThread - SAMT) algoritması geliştirildi. SAMT algoritması sürekli çalışan ana iş parçacığı ve tamamlandığında tekrarlı bir şekilde yeniden başlayan alt iş parçacığı koşacak şekilde tasarlandı. Alt iş parçacığı, ana iş parçacığına kıyasla daha kısa bir süre ile çalışmakta, ana iş parçacığına geri bildirim sağlamakta ve sonrasında farklı parametreler ile yeniden çalışmaktadır. Farklı başlangıç parametreleri ile çalışan alt iş parçacığı çözüm uzayının daha büyük bir kısmının taranmasına ve ana iş parçacığının yerel minimum bölgelerine ulaşacak şekilde ilerlemesine katkı sağlamaktadır. Kıyaslama için SAMT algoritması, Toplam Erkenlik ve Gecikme ölçütünü en küçükleyen Beklemesiz Akış Tipi Çizelgeleme problemine uygulandı. Algoritma, üç farklı veri setinde problemlerin çözümü sonunda klasik Benzetilmiş Tavlama, Tabu Arama algoritması türleri ve Parçacık Sürü Optimizasyonu algoritması türleri ile karşılaştırıldı. Varyans Analizi (ANOVA) ve çoklu karşılaştırma (post hoc) analizleri SAMT algoritmasının Benzetilmiş Tavlama algoritmasına ve diğer kıyaslama algoritmalarına karşı, bu algoritmalar iki asenkron iş parçacığı çalıştırsa ve daha iyi sonuç değerlendirilse dahi hem çözüm kalitesi hem de çalışma süresi anlamında üstünlük sağladığını ortaya çıkarmaktadır. SAMT algoritması, klasik Benzetilmiş Tavlama algoritmasının uzun çalışma süresi ve düşük yakınsama oranı dezavantajlarını ortadan kaldırmaktadır. SAMT algoritması ayrıca birçok farklı KOP tipine adapte edilebilecek genelleyici bir yapıya sahiptir.
Özet (Çeviri)
Combinatorial optimization problems (COP) have a pivotal role in easing our lives. Many of these problems emerged based on real-world cases. This aspect explains their popularity and utility. COP may be adapted to many different types of problems thanks to their generic structure besides modeling their originally intended problem. For instance, the famous Travelling Salesman Problem has countless different applications such as transportation planning, printed circuit board drilling, material handling in large warehouses, and navigation aids. Even though COP are crucial to optimize applications, they are hard to be solved in most cases with NP-Complete or NP-Hard complexity. Hence, a variety of approximation and metaheuristic algorithms were proposed to solve COP so far. In this thesis, parallelization and multithreading of metaheuristic algorithms in the literature were evaluated to seek ways to develop multithreaded policies for metaheuristics. A new multithreaded metaheuristic, namely the Simulated Annealing MultiThread (SAMT) was developed based on the classical Simulated Annealing algorithm. The SAMT algorithm was designed to run a continuous main thread and a recurring subthread. The subthread runs for a relatively short time compared to the main thread, provides feedback, and restarts with different parameters. With distinct initialization strategies during runtime, the subthread helps to search a larger portion of the search space and hints to direct the main thread toward local minimum regions. The SAMT algorithm was applied to No-Wait Flow Shop Scheduling Problem to Minimize Total Earliness and Tardiness objectives for benchmarking. The algorithm was compared to the classical Simulated Annealing Algorithm, variants of the Tabu Search algorithm, and variants of the Particle Swarm Optimization algorithm by solving problems from three different datasets. Analysis of Variance (ANOVA) and post hoc analysis revealed that the SAMT algorithm outperforms the Simulated Annealing and benchmark algorithm in terms of solution quality and runtime even if they run two asynchronous threads and the better solution is selected. The SAMT algorithm eliminates the long runtime and low convergence ratio drawbacks of the classical Simulated Annealing algorithm. It also has a generic structure that enables adapting the algorithm to many different types of COP.
Benzer Tezler
- Blockchain applications in maritime industry
Deniz lojistiğinde block zincir uygulamaları
MELİS KAŞKA
Yüksek Lisans
İngilizce
2020
DenizcilikGalatasaray ÜniversitesiLojistik ve Finansman Yönetimi Ana Bilim Dalı
DOÇ. DR. A. ÇAĞRI TOLGA
- Çok ölçütlü karar verme yöntemlerinden AHP ve TOPSIS ile araba seçimi
Car selection by applying multi-criteria decision making methods AHP and TOPSIS
KÜBRA AKMAN
Yüksek Lisans
Türkçe
2019
Endüstri ve Endüstri MühendisliğiNecmettin Erbakan ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ AHMET REHA BOTSALI
- Türkiye için dört boyutlu kadastral veri modelinin tasarımı ve uygulaması
Design and implementation of a four-dimensional cadastral data model for turkey
HİCRET GÜRSOY SÜRMENELİ
Doktora
Türkçe
2022
Jeodezi ve FotogrametriYıldız Teknik ÜniversitesiHarita Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET ALKAN
- Çok duyulu tasarımlarda duyu iş birliği kriterinin kullanıcı deneyiminin güçlendirilmesindeki etkisi
The effect of sensory cooperation criteria on enhancing user experience in multi-sensory designs
ÖZEN ŞENTOP
Yüksek Lisans
Türkçe
2023
Endüstri Ürünleri TasarımıEge ÜniversitesiEndüstriyel Tasarım Ana Bilim Dalı
PROF. DR. ZİYNET ÖNDOĞAN
- Taşıyıcı yüzey sistemlerinin girdap kafes yöntemi ile analizi ve genetik algoritma ile eniyilemesi
Analysis and optimization of lifting surface systems using vortex lattice method with genetic algorithm
OSMAN MİRZA DEMİRCAN
Yüksek Lisans
Türkçe
2018
Havacılık Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. MAHMUT ADİL YÜKSELEN