Developing and applying multi-threaded metaheuristic policies to solve combinatorial industrial engineering problems - Karacan, İsmet (My University, 2023)
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çalı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.

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.
Endüstri mühendisliğindeki kombinatoryal optimizasyon problemlerinin çözümü için çoklu iş parçacıklı metasezgisel politikalar geliştirilmesi ve uygulanması
Keywords: Benzetilmiş tavlama algoritması combinatorial Optimization problem; Çoklu iş parçacığı; Endüstri mühendisliği; Industrial engineering; Kombinatoryal optimizasyon; Metaheuristic algorithm; Multithreading; No-wait flow shop scheduling problem with earliness and tardiness; Optimization; Paralel algoritmalar beklemesiz akış tipi çizelgeleme; Parallel computing; Sezgisel algoritmalar; Simulated annealing