Sıra bağımlı hazırlık süreli ilişkisiz paralel makine çizelgeleme problemi için yeni bir komşuluk tabanlı DKA algoritması

Online Makale

Online Hizmetlere Toplu Bakış Online Kayıt ve Konaklama Online Bilimsel Program Dernekler İçin... Referanslarımız Telefon ve e-posta Desteği Bildiri özeti nedir? Bildiri özeti nasıl hazırlanır? Bildiri özeti örnekleri Kabul mektubu örnekleri

Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi

Sıra bağımlı hazırlık süreli ilişkisiz paralel makine çizelgeleme problemi için yeni bir komşuluk tabanlı DKA algoritması [Pamukkale Univ Muh Bilim Derg]

Pamukkale Univ Muh Bilim Derg. Baskıdaki Makaleler: PAJES-05935 | DOI: 10.5505/pajes.2025.05935

Sıra bağımlı hazırlık süreli ilişkisiz paralel makine çizelgeleme problemi için yeni bir komşuluk tabanlı DKA algoritması

Günay Kılıç¹, Arzu Organ²
¹Pamukkale Üniversitesi, Rektörlük, Denizli
²Pamukkale Üniversitesi, İktisadi ve İdari Bilimler Fakültesi, İşletme, Denizli

Çizelgeleme, belirli kısıtlar ve kriterler doğrultusunda görevlerin makinelere tahsis edilmesi sürecidir. Çizelgeler oluşturulup işler makinelere atandıkça çeşitli çizelgeleme problemleri ortaya çıkmaktadır. Bu çalışma, işler farklı makinelere göre değişen işlem sürelerine sahipken ve işler arasındaki hazırlık süreleri makineye bağlı olarak değişirken, nihai tamamlanma süresinin (Cmax) en aza indirilmesini amaçlayan Sıra Bağımlı Hazırlık Süreli İlişkili Olmayan Paralel Makine Çizelgeleme Problemi (UPMSPSDT) üzerine odaklanmaktadır. Hesaplama açısından NP-zor bir problem olması nedeniyle, kesin yöntemler UPMSPSDT’yi etkin bir şekilde çözmede yetersiz kalmakta ve bu nedenle araştırmacılar yaklaşık çözümler elde etmek için metasezgisel yaklaşımlara yönelmektedir.
Bu çalışmada, Değişken Komşuluk Arama (VNS) algoritması kullanılarak UPMSPSDT için daha kaliteli çözümler elde edilmesi amaçlanmaktadır. Bu doğrultuda, yengeçlerin kabuk değiştirme davranışından esinlenen ve literatürde mevcut komşuluk yapılarını tamamlayıcı nitelikte yeni bir komşuluk yapısı önerilmektedir. Ayrıca, üç farklı yerel arama yöntemi, komşuluk değişimlerinden elde edilen tamamlanma süresi (Cmax) değerlerine göre değerlendirilmiş ve yerel arama seçim stratejisi kullanılarak iteratif olarak uygulanmıştır. Bunun yanı sıra, literatürdeki açgözlü (greedy) başlangıç çözümüne yönelik bir iyileştirme önerilerek, daha yüksek kaliteli başlangıç çözümlerinin elde edilmesi hedeflenmiştir. Önerilen Yengeç İlhamlı Komşuluk Tabanlı DKA (CNVNS) algoritması, yaygın olarak kullanılan bir test veri seti üzerinde değerlendirilmiş ve sonuçlar analiz edilmiştir. Elde edilen bulgular, önerilen algoritmanın karşılaştırıldığı diğer yaklaşımlara kıyasla daha düşük Cmax değerleri ürettiğini ve UPMSPSDT çözümünde etkinliğini ortaya koyduğunu göstermektedir.

Anahtar Kelimeler: Değişken Komşuluk Arama, Metasezgisel, Sıra Bağımlı Hazırlık Süreli İlişkisiz Paralel Makine Çizelgeleme

A new neighborhood-based VNS algorithm for unrelated parallel machine scheduling problem with sequence-dependent setup times

Günay Kılıç¹, Arzu Organ²
¹Pamukkale University, Rectorate, Denizli
²Pamukkale University, Faculty of Economics and Administrative Sciences, Business Administration, Denizli

Scheduling involves the allocation of tasks to machines under specific constraints and criteria. As schedules are constructed and jobs are assigned to machines, various scheduling challenges arise. This study focuses on the NP-hard Unrelated Parallel Machine Scheduling Problem with Sequence-Dependent Setup Times (UPMSPSDT), where jobs have varying processing times across machines, and setup times between jobs depend on the machine. The objective is to minimize the makespan (Cmax ) of the final schedule. Due to its computational complexity, exact methods are ineffective in solving UPMSPSDT efficiently, leading researchers to explore metaheuristic approaches for near-optimal solutions.
This study aims to enhance solution quality for UPMSPSDT using the Variable Neighborhood Search (VNS) algorithm, a single-solution metaheuristic. To this end, a novel neighborhood structure is introduced, inspired by the shell-changing behavior of crabs, complementing existing structures in the literature. Additionally, three different local search strategies are evaluated based on the makespan values obtained through neighborhood transitions and are applied iteratively using a local search selection strategy. Furthermore, an improved version of a greedy initial solution from the literature is proposed to generate higher-quality starting solutions. The proposed Crab-inspired Neighborhood-based VNS (CNVNS) is tested on a widely used benchmark dataset, and the results are analyzed. Findings indicate that the proposed algorithm outperforms benchmarked approaches in achieving lower Cmax values, demonstrating its effectiveness in solving UPMSPSDT.

Keywords: Variable Neighborhood Search, Metaheuristic, Unrelated Parallel Machine Scheduling Problem with Sequence-Dependent Setup Times

Sorumlu Yazar: Günay Kılıç, Türkiye

ARAÇLAR