Sıra bağımlı hazırlık süresi ve makine kısıtları ile ilişkisiz paralel makine çizelgeleme problemine değişken komşuluk araması yaklaşımı

Abstract

Bu çalışmada, sıra bağımlı hazırlık süreli ilişkisiz paralel makine çizelgeleme problemi ele alınmıştır. İşlerin birden fazla ilişkisiz paralel makinelerde işlenebileceği ve her işin işlenmeye başlamadan önce bir hazırlık süresine ihtiyaç duyduğu bir üretim ortamı modellenmektedir. Hazırlık süresi, makineye ve işlerin sırasına bağlı olarak değişkenlik göstermektedir. Problem, makinelerin planlı duruşlar nedeniyle belirli bir süre boyunca kullanılamayacağı varsayımı altında incelenmektedir. Çalışmanın amacı, toplam gecikme ve erken teslim sürelerini en aza indirmektir. NP-zor olarak sınıflandırılan problemin uzun çözüm süreleri ve kesin çözüme ulaşmanın zorluğu nedeniyle problemin çözümünde metasezgisel algoritmalar tercih edilmiştir. Çalışmada ele alınan sıra bağımlı hazırlık süreli ilişkisiz paralel makine çizelgeleme problemi için yeni bir Değişken Komşuluk Arama (DKA) algoritması önerilmiştir. Önerilen algoritma, çeşitli başlangıç çözümlerden başlayarak çözüm uzayının farklı alanlarını keşfetmek üzere tasarlanmış üç farklı komşuluk yapısı ve Değişken Komşuluk İniş (DKİ) algoritmasını kullanılmaktadır. Komşuluk dereceleri ile giderek büyüyen bir çözüm uzayı keşfedilmekte olup, mevcut duruma göre adaptif bir şekilde komşuluk yapısı seçimi yapılmaktadır. Bu yaklaşım, algoritmanın arama verimliliğini artırmayı ve global optimuma ulaşma süresini hızlandırmayı amaçlamaktadır. Sentetik veri oluşturma algoritmasıyla üretilen ve gerçek dünya verilerini iyi bir şekilde temsil eden test problemleri kullanılarak, önerilen DKA algoritması matematiksel programlama çözümleri ile karşılaştırıldı. Elde edilen sonuçlar, önerilen algoritmanın problemin çeşitli boyutları ve karmaşıklık düzeyleri için matematiksel programlama çözümlerine kıyasla çözüm süresi ve en iyi çözüme yakınsama yeteneğine göre daha etkin ve verimli bir yöntem olduğunu göstermektedir.In this study, the unrelated parallel machine scheduling problem with sequence-dependent setup times is addressed. A production environment is modeled where jobs can be processed on multiple unrelated parallel machines, and each job requires a setup time before processing. The setup time varies depending on the machine and the job sequence. The problem is examined under the assumption that machines may be unavailable for certain periods due to scheduled downtimes. The objective of the study is to minimize total tardiness and early completion times. Due to the NP-hard classification of the problem, which results in prolonged solution times and the difficulty of achieving exact solutions, metaheuristic algorithms have been employed. This study proposes a new Variable Neighborhood Search (VNS) algorithm for the unrelated parallel machine scheduling problem with sequence-dependent setup times. The proposed algorithm leverages three distinct neighborhood structures and the Variable Neighborhood Descent (VND) algorithm, designed to explore different regions of the solution space from various initial solutions. The neighborhood degrees facilitate the exploration of an increasingly expansive solution space, while the adaptive selection of the neighborhood structure is performed based on the current state of the solution. This approach aims to improve the efficiency of the search process and expedite the attainment of the global optimum. The proposed VNS algorithm was compared with mathematical programming solutions using test problems generated by a synthetic data generation algorithm, which well represents real-world data. The obtained results demonstrate that the proposed algorithm is a more effective and efficient method in terms of solution time and convergence ability to the best solution compared to mathematical programming solutions for various problem sizes and complexity levels.