Beklemesiz akış tipi çizelgeleme problemleri için hibrit gri kurt optimizasyon algoritması
Hybrid gray wolf optimization algorithm for no-wait flow shop scheduling problems
Yazar: CENGİZ KINA
Danışman: DOÇ. DR. İBRAHİM BERKAN AYDİLEK
Harran Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2022
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin: Doğrusal programlama = Linear programming ; Gri kurt optimizasyon algoritması = Grey wolf optimizer algorithm ; Çizelgeleme = Scheduling

Özet:
Günümüzde giderek artan rekabet ortamında siparişlerin zamanında teslim edilmesi ve kaynakların verimli kullanılması ihtiyacı, üretim çizelgelemeyi önemli bir hale gelmiştir. Akış tipi çizelgeleme problemleri gerçek yaşam uygulamalarında yer edinen önemli çizelgeleme türlerinden biridir. Beklemesiz akış tipi çizelgeleme (BATÇ) ilaç sanayi, plastik sanayi, demir çelik sanayi gibi alanlarda bir makinede işlenen bir ürünün bir sonraki işlenecek makineye geçtiğinde makineler arasında herhangi bir beklemenin müsaade edilmediği bir çizelgeleme türüdür. İşler makineler arasında beklediğinde yapısında bozulmalar meydana gelebileceği gibi üretim sürecini olumsuz etkileyip maliyetleri arttırabilmektedir. Makine sayısı iki veya daha az olan problemlerde en iyi çözümü bulmak mümkündür. Ancak makine sayısının fazla olduğu problemlerde en iyi çizelgelemeyi bulmak imkânsız hale gelebilir. Bu tür problemlere literatürde NP-Zor problemler denilmektedir. Kesin yöntemler bu tür problemlerin çözümünde yetersiz kaldığı için metasezgisel yöntemler tercih edilmektedir. Metasezgisel yöntemler kesin sonucu garanti etmemekle birlikte kısa bir süre içirisinde optimum çözüme yakın çözümler sunabildiği için literatürde sıklıkla kullanılmaktadır. Bu çalışmada BATÇ problemlerinin çözümü için birçok çizelgeleme probleminde kullanılan Gri kurt optimizasyon (GKO) algoritması kullanılmıştır. Tez çalışmasında GKO algoritması literatürde iyi bilinen ve BTAÇ için üretilmiş 192 test problemi üzerinde test edilmiştir. Algoritmanın performansını arttırmak amacıyla başlangıç popülasyonuna Nawaz, Enscore, Ham (NEH) ve Sıralı İşlem Süresi (SİS) yöntemlerine göre üretilen çözümler eklenmiştir. Ayrıca algoritmanın sömürü yeteneğini arttırmak için yerel arama algoritması olarak Değişken Komşuluk Arama algoritması ile hibrit hale getirilmiştir. Elde edilen sonuçlar önerilen algoritmanın BATÇ problemleri için oldukça etkili ve verimli olduğunu ortaya koymuştur.

Abstract:
These days, in an increasingly competitive environment, the need for timely delivery of orders and efficient use of resources has made production scheduling important. Flow scheduling problems are one of the important scheduling types in real life applications. No-wait flow shop scheduling (NWFSS), is a type of scheduling in which no waiting is allowed between machines when a product processed in one machine passes to the next machine. In fields such as the pharmaceutical industry, plastics industry, iron and steel industry. When jobs waits between the machines, deterioration in its structure may occur, as well as negatively affecting the production process and increasing costs. It is possible to find the best solution for problems with two or less machines. However, it may become impossible to find the best scheduling in problems with a large number of machines. Such problems are called NP-hard problems in the literature. Metaheuristic methods are preferred because exact methods are insufficient in solving such problems. Although metaheuristic methods do not guarantee the exact result, they are frequently used in the literature because they can provide solutions close to the optimum solution in a short time. In this study, Gray Wolf Optimization (GWO) algorithm, which is used in many scheduling problems, is used to solve NWFSS problems. The GWO was tested on 192 test problems that are well known in the literature and produced for NWFSS. In order to increase the performance of the algorithm, solutions produced according to Nawaz, Enscore, Ham (NEH) and Sorted Processing Time (SPT) methods were added to the initial population. In addition, it has been hybridized with the Variable Neighborhood Search algorithm as a local search algorithm to increase the exploitation ability of the algorithm. The results revealed that the proposed algorithm is quite effective and efficient for NWFSS problems.