A hybrid evolutionary algorithm for multi-objective flexible job shop problems

Abstract

Gerçek hayat uygulamaları arasında yer alan esnek atölye çizelgeleme problemi (FJSSP), atölye çizelgeleme problemlerinin (JSSP) genişletilmiş versiyonudur. Problem esas olarak iki zorluktan oluşmaktadır. Birincisi, işlemi gerçekleştirebilecek bir makine setinden her işlem için bir makinenin atanması, ikincisi ise işlemlerin fizibilite koşulları sağlanırken sıralanmasıdır. Çizelgeleme problemlerini çözmek, iyi bilinen NP-zor problem alanında oldukları için oldukça zordur. Literatür araştırmaları bu iki alt problemi bütünleşik bir yaklaşımla birlikte veya sıralı bir şekilde tek tek ele alarak çözmeye çalışmaktadır. Pazardaki yoğun rekabet nedeniyle, etkin çizelgeleme artık endüstrilerin büyümesi ve hayatta kalması için önemli bir konu haline gelmiştir. Mevcut rekabet ortamında ayakta kalabilmek için, endüstrilerin, üretim süresi, akış süresi ve gecikme gibi performans ölçütlerinin eşzamanlı optimizasyonuna dayalı rmeleri esastır. Tüm çizelgeleme kriterleri iş operasyonu açısından önemli olduğundan, tek bir hedef yerine tüm hedefleri aynı anda optimize etmek hayati önem taşımaktadır. Ayrıca, makine arızaları, arızalar, teslim süreleri veya son teslim tarihleri gibi ek kısıtlamalar getirilirse sorun daha da zorlaşabilir. Bu amaçla, dinamik ortamlarda çalıştıkları için gerçek dünya uygulamaları için sağlam ve esnek çizelgeler bulma sorunu son derece önemlidir. Son zamanlarda, çok amaçlı FJSSP'leri çözmek için birçok çalışma yapılmıştır. Bu çalışmalar, meta-sezgisel, matematiksel programlama, simülasyon tabanlı yöntemler, yapay zeka tabanlı yöntemler veya bunların bir kombinasyonu gibi çeşitli teknikleri kullanan algoritmalar geliştirerek en uygun çözümü belirlemeyi amaçlamaktadır. Bu tez çalışmasında, FJSSP'yi çözmek için GA'yı paralel yürütülen yerel arama prosedürleriyle bütünleştiren verimli bir algoritma önerilmiştir. Başlangıç popülasyonu, arama uzayında daha iyi alanlar ve erken yakınsamayı önlemek için yeterli çeşitlilik sağlamak için gönderme kuralları kullanılarak oluşturulur. Ayrıca, çözümün sağlamlığını, yakınsama ve yürütme süresini iyileştirmek için kritik bir yol tabanlı çoklu arama prosedürü paralel olarak uygulanır ve yürütülür. Hedef fonksiyonlar, Pareto Optimal yaklaşımı ile değerlendirilir ve çözümler, Pareto sıralamasına ve hiperhacim katkı ölçüsüne (Δs) dayalı iki seviyeli bir seçim stratejisi ile seçilir. Önerilen algoritmanın etkinliği ve performansı, literatürde sunulan iyi bilinen veri setleri kullanılarak diğer algoritmalarla kıyaslanır ve karşılaştırılır.

The Flexible Job-Shop Scheduling Problem (FJSSP) is a real-world problem that builds upon the Job Shop Scheduling Problem (JSSP). It involves two main challenges: assigning the appropriate machine for each operation from a set of machines that can perform the operation and arranging the operations in a sequence while meeting feasibility conditions. These scheduling problems are known to be challenging as they fall under the NP-hard category. Researchers have attempted to solve these sub-problems by either addressing them as a combined approach or tackling them individually in a sequential manner. With the market becoming increasingly competitive, effective scheduling has become a crucial aspect for the success and survival of industries. In order to remain competitive, companies must improve their schedules by simultaneously optimizing various performance measures such as makespan, flow time, and tardiness. All of these scheduling criteria are important from a business perspective, therefore it is essential to optimize all objectives at once, rather than just one. Additionally, the problem can become even more complex when additional constraints are introduced, such as machine breakdowns, failures, release times, or deadlines. This is why it is important to find robust and flexible schedules that can adapt to changing conditions in real-world applications, as they often operate in dynamic environments. In recent times, there has been a significant amount of research focused on resolving multi-objective Flexible Job-Shop Scheduling Problems (FJSSPs). These studies aim to identify the optimal solution through the development of algorithms that employ various techniques such as meta-heuristics, mathematical programming, simulation-based methods, artificial intelligence-based methods or a combination of them. This dissertation presents a new algorithm that utilizes a combination of Genetic Algorithm (GA) and parallelized local search procedures to effectively solve the Flexible Job-Shop Scheduling Problem (FJSSP). The initial population is generated using dispatching rules to identify promising regions in the search space and to ensure adequate diversity to prevent early convergence. Additionally, a critical path-based multi-search procedure is applied and executed in parallel to enhance the robustness, convergence, and computational efficiency of the solution. The algorithm evaluates the objective functions using a Pareto Optimal approach and employs a two-level selection strategy that combines Pareto ranking and the hypervolume contribution measure (Δs) to choose solutions. The proposed algorithm has been evaluated and compared to other existing methods using well-known datasets from the literature to demonstrate its effectiveness and performance.