Solving permutation flow shop scheduling problem with adaptive genetic algorithm / Uyarlanabilir genetik algoritma ile permütasyon akış tipi çizelgeleme problemini çözme

Abstract

Permütasyon akış tipi çizelgeleme problemi (PATÇP), bir dizi işin belirli bir sırayla bir dizi makinede işlenmesi gerektiği üretim senaryolarında ortaya çıkan bir problemdir. Tüm işlerin tamamlanması için gereken süreyi en aza indirecek en iyi işlem sırasını bulmak amaçlanır. PATÇP bir NP-Zor kombinatoryel optimizasyon problemidir, dolayısıyla tam çözümü zordur ve hesaplama için önemli miktarda zaman gerektirir. Bu tezde, PATÇP çözümü için yeni bir sezgisel algoritma olan Uyarlanabilir Genetik Algoritma (UGA) önerilmektedir. UGA, geleneksel bir genetik algoritmayı üç farklı yerel arama yöntemini uyarlanabilir bir mekanizmayla birleştirmektedir. Algoritma, her nesil iterasyonunda her yerel aramanın performansını değerlendirir ve önceki performanslarına dayanarak hangisini kullanacağına karar verir. Başarılı olan yerel aramaların seçim olasılığı artar ve başarısız olanların seçim olasılığı azalır. Bu şekilde, UGA algoritması, önceki nesillerde elde ettiği bilgiyle uyarlanır ve yönlendirilir. Önerilen algoritma, çözüm kalitesi açısından diğer en gelişmiş algoritmalardan biri olan GA-BAT'ın performansını geride bırakmış ve ya optimal ya da optimale yakın sonuçlar üretmiştir. UGA algoritması, Permütasyon akış tipi çizelgeleme probleminin çözümü için umut verici bir yaklaşım olup diğer kombinatoryel problemlere de uyarlanabilir. The permutation flow shop scheduling problem (PFSSP) is a problem that arises in manufacturing scenarios where a set of jobs must be processed on a set of machines in a specific order. The problem aims to find the job order that will minimize the makespan of the whole process. It is an NP-Hard combinatorial optimization problem, hence its exact solution is computationally difficult and requires a significant amount of time. This thesis proposes a new heuristic algorithm called the Adaptive Genetic Algorithm (AGA) for solving a PFSSP. The AGA combines a conventional genetic algorithm with an adaptive mechanism that incorporates three different local searches. The algorithm evaluates the performance of each local search at each generational iteration and makes a decision on which one to use based on their previous performances. The experimental results showed that the algorithm outperformed one of the state-of-the-art algorithms (i.e. GA-BAT) in terms of solution quality and found optimal or near-optimal solutions for the selected benchmarks. The AGA algorithm is a promising approach for solving the PFSSP and could be extended to apply to other combinatorial optimization problems.