Beklemesiz akış tipi çizelgeleme problemlerinin bulanık ortamda dağınık arama yöntemi ile çözümü

Abstract

Çizelgeleme problemleri, günümüzde üzerinde çokça durulan önemli bir konudur. Bu çalışmada Akış Tipi Çizelgeleme problemi, işlerin beklemesiz olma kısıtı ile ele alınmıştır. Literatürde, 2 makineden fazla olan Beklemesiz Akış Tipi Çizelgeleme (BATÇ) problemlerini matematiksel bir yöntem ile, kabul edilebilir bir sürede çözebilecek bir metot bulunmamaktadır. Bu yüzden Beklemesiz Akış Tipi Çizelgeleme, NP (Polinomiyel Olmayan)-zor problemler sınıfında yer almaktadır. Bu problemlerin çözümü için, optimum ya da optimuma yakın sonuç verecek meta-sezgisel yöntemler geliştirilmektedir. Bu çalışmada ise literatürde birçok probleme uyarlanmış ve oldukça verimli sonuçlar elde edebilen, evrimsel bir arama tekniği olan Dağınık Arama Yöntemi kullanılmıştır. Çalışma sonuçlarının etkinliğini ispatlamak için, literatürde iyi bilinen 192 adet test problemi çözülmüştür. Elde edilen çalışma sonuçları daha önce Beklemesiz Akış Tipi Çizelgeleme problemi için yapılmış olan Genetik Algoritma (Gen-2), Uyarlanabilir Öğrenme Yaklaşım (UÖY) algoritması ve Hibrit Karınca Kolonileri Optimizasyon (HKKO) algoritması ile kıyaslanmıştır. Gerçek hayatta öngörülemeyen sonuçların teslim tarihlerini belirsiz kılmasından dolayı, mevcut problemlerin teslim tarihleri bulanıklaştırılmıştır ve müşteri tatmin indeksleri hesaplanmıştır. Elde edilen tüm sonuçlar göz önüne alındığında, önerilen Dağınık Arama Yönteminin, literatürdeki diğer sezgisel ve meta-sezgisel yöntemler ile rekabet edebilecek, oldukça verimli bir arama tekniği olduğu görülmüştür.

Scheduling problems are an important topic that is emphasized a lot today. In this study, the Flow Shop Scheduling problem is handled with the constraint of jobs being no-wait. In the literature, there is no method that can solve the No-Wait Flow Shop Scheduling (NWFSS) problems of more than 2 machines with a mathematical method in an acceptable time. Therefore, No-Wait Flow Shop Scheduling is included the class of NP (Non-Polynomial)-hard problems. For the solution of these problems, meta-heuristic methods are being developed that will give optimum or near-optimal results. In this study, the Scatter Search Method, which is an evolutionary search technique that has been adapted to many problems in the literature and can yield very efficient results, has been used. To prove the effectiveness of the study results, 192 well-known test problems in the literature were solved. The results of the study were compared with the Genetic Algorithm (Gen-2), Adaptive Learning Approach (ALA) algorithm and Hybrid Ant Colony Optimization (HACO) algorithm, which were previously made for the No-Wait Flow Shop Scheduling problem. Due to the unpredictable results in real life making the due dates uncertain, the due dates of the existing problems were fuzzed and customer satisfaction indexes were calculated. Considering all the results obtained, it has been seen that the Scattered Search Method is a very efficient search technique that can compete with other heuristics and meta-heuristics in the literature.