Atölye Tipi Çizelgeleme Problemlerine Parçacık Sürü Optimizasyonu Yaklaşımı Ve Genetik Algoritma Modeli İle Karşılaştırılması

Abstract

Bu tezde, zor çizelgeleme problemleri arasında yer alan atölye tipi çizelgeleme problemlerinin çözümünde alternatif yeni bir yaklaşım ele alınmıştır. Çözüm yöntemi olarak, son yıllarda hızla gelişen popülasyon temelli yeni sezgisel yöntemlerden biri olan Parçacık Sürü Optimizasyonu (PSO) kullanılmıştır. Bu tezde, ilk olarak atölye tipi çizelgeleme problemleri için PSO ve Genetik Algoritma (GA) modeli tasarlanmış ve tamamlanma zamanı (makespan) başarım ölçütüne göre literatürde yer alan test problemleri üzerindeki performansları incelenmiştir. Daha sonra PSO ve GA modellerinin sonuçları % 5, % 1 ve ‰ 5 anlamlılık düzeylerinde istatistiksel olarak karşılaştırılıp incelenmiştir. Sonuçta, PSO modeli ile GA modelinin birbirine yakın performans gösterdiği, bazı zor problemlerde ise PSO modelinin GA modeline göre daha iyi sonuç verdiği görülmüştür. Bunlara ek olarak, basit ve etkili bir yerel arama yöntemi olan Değişken Komşuluk Arama (VNS) kullanılarak, yerel aramalı PSO ve GA modelleri geliştirilmiş ve literatürdeki bazı zor test problemlerine uygulanmıştır. Daha sonra bu iki model istatistiksel olarak karşılaştırılıp incelenmiştir. Sonuçta, yerel aramalı PSO modelinin, yerel aramalı GA modeline göre % 5 anlamlılık düzeyinde daha iyi olduğu görülmüştür. Ayrıca, yerel aramalı PSO modelinin sonuçları, literatürde ün yapmış diğer sezgisel yöntemlerin sonuçlarıyla karşılaştırılmış, daha iyi veya eşdeğer seviyede olduğu görülmüştür.

In this dissertation, a new meta-heuristic technique called Particle Swarm Optimization (PSO) is applied to Job Shop Scheduling (JSS) problem, which is one of the hardest combinatorial optimization problems. First of all, a PSO and a Genetic Algorithm(GA) model for the JSS problem are developed and applied to the well-known benchmark suites in the literature with the makespan criterion. Then, PSO and GA model results are compared statistically at 5 %, 1 % and 5 ‰ significant levels. It is concluded that, PSO results are competitive and sometimes better than GA results over the 122 benchmark problems. In addition, a simple but efficient local search method called Variable Neighborhood Search (VNS) is embedded to the PSO and GA models and applied to several hardest benchmark suites. Afterwards, PSO and GA model with VNS results are compared statistically and it is concluded that, PSO model with VNS results are better than GA model with VNS at 5 % significant level. The results for the PSO algorithm with VNS are also presented and compared with many efficient meta-heuristic algorithms in literature. As a final result, PSO with VNS results are generally found to be better than other results.