Sıraya bağımlı kurulum süreleri ile tek tip paralel makine çizelgelemesi üzerine bir çalışma

Abstract

Scheduling problems are essential for decision-making in many academic disciplines, including operations management, computer science, and information systems. Since many scheduling problems are NP-hard in the strong sense, there is only limited research on exact algorithms and their efficiency when implemented on parallel computing architectures. This master's thesis considers the uniform parallel machine scheduling problem with sequence-dependent setup times to minimize the maximum completion time (makespan). We present an IP formulation, which clearly describes our problem and can be used to obtain optimal solutions for small-sized problems. As our problem is NP-hard, we propose a randomized heuristic with an improvement subroutine. The performance of the proposed heuristic through a computational study was tested with 320 instances. We created these instances using the full factorial design of experiment (DOE) with five different factors. Our computational study indicates that the proposed mathematical model takes 22.88 minutes on average, and the heuristic algorithm achieves these results only in 0.062 minutes. The average solutions obtained with the heuristic have an approximately 4% Gap value for average CPLEX solutions. Also, the contribution of the improvement subroutine step to the overall performance of the heuristic is 73.34%. Keywords: parallel machine scheduling, sequence-dependent setup time, full factorial design, randomized heuristic, uniform machines, total completion times

Çizelgeleme problemleri; operasyon yönetimi, bilgisayar bilimi ve bilgi sistemleri dahil olmak üzere birçok akademik disiplinde karar vermek için gereklidir. Çoğu çizelgeleme problemi güçlü anlamda NP-zor olduğundan, kesin algoritmalar ve verimliliklerinin nasıl ölçeklendiği konusunda sınırlı araştırma vardır. Bu çalışmada, maksimum tamamlama süresini en aza indirmek için sıraya bağlı kurulum süreleriyle tek tip paralel makine çizelgeleme problemini ele alıyoruz. Problemimizi açık bir şekilde tanımlayan ve küçük boyutlu problemler için en uygun çözümleri elde etmek için kullanılabilecek bir tam sayılı problem formülasyonu sunuyoruz. Sonrasında, problemimiz NP-zor olduğundan, iyileştirme alt rutini ile rastgele bir buluşsal yöntem öneriyoruz. Hesaplamalı bir çalışma yoluyla önerilen sezgisel yöntemin performansı 320 örnekle test edilmiştir. Bu örnekleri, beş farklı faktörlü deneyin tam faktöriyel tasarımını (DOE) kullanarak oluşturduk. Hesaplamalı çalışmamız, önerilen matematiksel modelin ortalama 22.88 dakika sürdüğünü ve sezgisel algoritmanın bu sonuçları yalnızca 0.062 dakikada elde ettiğini göstermektedir. Sezgisel yöntem sonuçları ile matematiksel model sonuçları karşılaştırıldığında, CPLEX yazılımında yapılan sezgisel yöntem ortalama olarak yaklaşık %4 Gap değerine sahiptir. Ayrıca, iyileştirme adımının sezgisel yöntemin genel performansına katkısı %73,34'tür. Anahtar Kelimeler: paralel makine çizelgelemesi, sıraya bağlı kurulum süresi, tam-etkenli tasarım, sezgisel yöntem, tek tip makine, toplam tamamlanma süresi