Erken ve Geç Teslim Hedefleriyle Beklemesiz Akış Tipi Atölye Çizelgeleme Problemini Çözmek İçin Kesin Bir Çözüm Algoritması

Abstract

Beklemesiz akış tipi atölye çizelgeleme problemi (BATAÇP), işlerin belirli bir makine sırasını takip ettiği geleneksel akış tipi atölye yapılandırmasının bir uzantısıdır. BATAÇP, akış tipi atölye problemine, ardışık makineler arasında işlerin beklemesine izin vermeyen bir kısıtlama ekleyerek genişletilmiştir. BATAÇP ile ilgili son çalışmalar, genellikle en sona çizelgelenen işin tamamlanma süresi, toplam akış zamanı ve toplam tamamlanma süresi gibi geleneksel hedeflere odaklanmıştır. Ancak, erken tamamlanma ve gecikme hedeflerinin birlikte kullanıldığı çözüm yaklaşımlarına yönelik sınırlı çalışmalar bulunmaktadır. BATAÇP, NP-zor olarak sınıflandırılmakta olup, büyük problem örnekleri için optimal çözümler bulmak hesaplama açısından zorluklar yaratmaktadır. Bunun üstesinden gelmek için, tavlama benzetimi, tabu arama ve parçacık sürüsü optimizasyonu gibi sezgisel ve meta-sezgisel yöntemler yaygın olarak kullanılarak yaklaşık-optimal çözümler bulunmaktadır. Bununla birlikte, mevcut literatürde bu problem için kesin çözüm yöntemleri oldukça azdır. Bu boşluğu doldurmak amacıyla, bu makale BATAÇP için yeni bir karma tam sayılı programlama (KTP) modeli tanıtmaktadır ve erken tamamlanma ve gecikme hedeflerini minimize etmek amacıyla bu yeni model üzerine inşa edilmiş bir dal-kesme (DK) algoritması sunmaktadır. Önerilen DK algoritması, güçlü üst sınırlar elde etmek için bir sezgisel yaklaşım ile birleştirilmiştir. Algoritma, problem alanını sistematik bir şekilde keşfederek ve kesme düzlemi teknikleri kullanarak matematiksel formülasyonları iyileştirmektedir. Algoritmanın performansı, kapsamlı bir kıyaslama problem örnekleri seti kullanılarak test edilmekte ve sonuçlar, literatürde bulunan KTP modeli ile karşılaştırılmaktadır. Hesaplamalı deneyler, önerilen DK algoritmasının hem çözüm kalitesi hem de hesaplama verimliliği açısından etkin olduğunu göstermektedir.