Comparison of genetic algorithm and particle swarm optimization algorithm for bicriteria fermutation flowshop scheduling problem

Abstract

İKİ KRİTERLİ PERMÜTASYONLU AKIŞ TİPİ ÜRETİM ÇİZELGELEMESİ PROBLEMİ İÇİN GENETİK ALGORİTMA VE PARÇACIK SÜRÜ OPTİMİZASYONU YÖNTEMLERİNİN KARŞILAŞTIRILMASI Akış tipi üretim çizelgeleme problemi, üzerinde çok çalışılmış olan alanlardan biridir. Problemin çapı büyüdükçe, analitik çözüm bulmak imkansızlaşır ve burada sezgisel yaklaşımlar devreye girer. Literatüre bakıldığında, bu problem için genelde tek kriterli yaklaşımlar geliştirildiği görülür; toplam yapım zamanı en çok kullanılmış olan kriterdir. Az sayıda makine için çok kriterli sezgisel yöntemler bulunsa da, ikiden fazla makine için genelde sadece tek kriter dikkate alınmıştır. Bu tez çalışmasında, 50 iş – 20 makine gibi büyük çaplı problemler için, toplam yapım zamanı ve en büyük pozitif gecikme zamanı kriterleri birlikte dikkate alınmıştır. Bu amaçla, bir Partikül Sürü Optimizasyonu (PSO), bir de Genetik Algoritma (GA) sezgisel yöntemi geliştirilmiş ve standart test problemlerine uygulanmıştır. PSO ve GA’nın sadece yalın şekilleri değil, aynı zamanda Değişken Komşuluk Arama isimli bir yerel arama yöntemiyle melezlenmiş olan şekilleri de denenmiş, ve iki algoritmanın performansları birbirleriyle karşılaştırılmıştır. Elde edilen sonuçlara göre, en büyük pozitif gecikme zamanı kriterinin ağırlıklı olduğu durumlarda PSO daha iyi sonuç vermiş; toplam yapım zamanı kriterinde ise GA daha başarılı olmuştur. İşlem sürelerinde ise, her durumda PSO daha çabuk sonuca ulaşmıştır. Yerel arama katılmış melez algoritmalar, yalın hallerine göre daha iyi sonuçlara ulaşmış; ancak, işlem süresi ciddi oranda artmıştır.

COMPARISON OF GENETIC ALGORITHM AND PARTICLE SWARM OPTIMIZATION ALGORITHM FOR BICRITERIA PERMUTATION FLOWSHOP SCHEDULING PROBLEM Flowshop scheduling problem is a well known research field for fifty years. As the problem size gets bigger, an analytical solution becomes impossible. Here, heuristic solutions come to the stage. In the literature, generally solutions regarding a single criterion are developed; and makespan is the most common objective used. There are some multi objective solutions for one or two machines; but, only one criterion is generally used for more than two machines. In this thesis, makespan and maximum tardiness criteria are used concurrently, for big problem sizes like 50 jobs-20 machines. For this purpose, a Particle Swarm Optimization (PSO), and a Genetic Algorithm (GA) is developed and applied to standard test problems. Not only the pure versions of PSO and GA, but also their hybrid versions – i.e. with a local search called Variable Neighborhood Search (VNS) embedded - are tested; and the relative performances of the two algorithms are compared. As a result, PSO performed better for the situations where the weight of maximum tardiness criterion was greater, while GA surpassed PSO when the makespan objective was dominant. Regarding the CPU times, PSO found a solution more quickly, for all occasions. The with-VNS versions of the algorithms found better solutions compared to the pure versions; but, it took them much longer.