Comparison of genetic algorithm and particle swarm optimization algorith for permutation flow shop sequencing problem with criterion of number of tardy jobs

Abstract

Bu çalışmada permütasyon akış tipli atölyelerdeki pozitif gecikmeli iş sayısınıminimuma indirmeyi amaçladık. Pozitif gecikmeli iş sayısı kriteri memnun olmayanmüşterilerin sayısına ait bir ölçüdür. Diğer bir deyişle, bu kriter yöneticilerinperformansına ait bir göstergedir. Minimum sayıda gecikmeli iş sayısı hedefinisağlayabilmek için iki algoritma geliştirdik; biri geleneksel bir genetik algoritma diğeriise kesikli partikül sürü optimizasyonu algoritması. Algoritmalarda Demirkol vediğerleri'nin data setlerindeki teslim tarihleri kullanıldı. Herbir algoritmanın gecikmeliiş sayısına ait değerleri ve işlemci süreleri için istatistiksel ölçümler yapıldı. Her ikialgoritmanın m makinadaki en optimal iş sıralamasını bulmadaki performanslarıkarşılaştırıldı. Yapılan deneylerde partikül sürü optimizasyonu algoritmasının EnKüçük Konum (EKK) sezgisel yöntemi sayesinde umut verici neticeler verdiği sonucunavarıldı.Anahtar Kelimeler: Çizelgeleme, Pozitif Gecikmeli İş Sayısı, Genetik Algoritma, PartikülSürü Optimizasyonu, En Küçük Konum Kuralı, Permutasyon Akış Tipli Atölye

In this study, we aimed to minimize the number of tardy jobs in permutation flowshops. The number of tardy jobs criterion is a measure for the number dissatisfiedcustomers. In other words, it monitors the performance of the managers. In order toachieve the minimum number of tardy objective, we developed two algorithms; one is atraditional genetic algorithm and the latter is a discrete particle swarm optimizationalgorithm. The algorithms are implemented using the due date configurations ofDemirkol et al.?s data sets. The statistical tests are done to measure the fitness and cpuvalues for each algorithm. The performances of both algorithms to find the optimalprocessing sequence for the jobs through m machines are compared. It is concludedfrom the experiments that the particle swarm optimization algorithm gives promisingsolutions by means of the proposed SPV (Smallest Position Value) heuristic rule.Keywords: Scheduling, Number of Tardy Jobs, Genetic Algorithm, Particle SwarmOptimization, Smallest Position Value Rule, Permutation Flow Shop