Ortak teslim tarihli ve ağırlıklı toplam erkenlik, gecikme, birim erkenlik ve sabit atama maliyetli paralel makine çizelgeleme

Abstract

This thesis addresses the parallel machine scheduling problem with a common due date, aiming to minimize total weighted earliness, tardiness, unit earliness and fixed assignment costs. The objective function introduces a novel cost structure by extending traditional earliness and tardiness penalties with two additional components: (i) unit earliness costs, and (ii) fixed machine assignment costs. These extensions are motivated by practical considerations in production systems, such as inventory holding costs, quality preservation, and work-in-process (WIP) stocking costs. A mixed-integer linear programming (MILP) formulation is proposed to optimally solve small-sized instances and serve as a benchmark for evaluating heuristic methods. Due to the NP-hard nature of the problem, exact methods become computationally infeasible for larger instances. To address this, a problem-specific Genetic Algorithm (GA) is developed, incorporating a tailored solution representation, one-point crossover and cusromized mutation operators, and the revised V-shaped scheduling property to guide sequencing decisions. A comprehensive experimental study is implemented to assess the GA's performance across various problem sizes and parameter settings. GA parameters are tuned through preliminary testing to ensure a problem adaptive convergence behavior. Extensive computational experiments are conducted using both benchmark problems from the literature and newly generated datasets. Results indicate that the proposed GA consistently achieves near-optimal solutions in significantly less time than the MILP model, especially in larger instances. The algorithm demonstrates strong performance in terms of solution quality and computational efficiency making it a promising approach for solving complex scheduling problems in practical manufacturing environments.

Bu tez, ortak teslim tarihli paralel makine çizelgeleme problemini ele almakta ve toplam ağırlıklı erkenlik, gecikme, birim erkenlik ve sabit makine atama maliyetlerini en aza indirmeyi amaçlamaktadır. Amaç fonksiyonu, geleneksel erkenlik ve gecikme maliyetlerine iki ek bileşen ekleyerek özgün bir maliyet yapısı sunmaktadır: (i) birim erkenlik maliyetleri ve (ii) sabit makine atama maliyetleri. Bu genişletilmiş yapı; üretim sistemlerinde karşılaşılan stok tutma maliyetleri, kalite koruma gereklilikleri ve yarı mamul stoklama gibi unsurlar göz önünde bulundurularak oluşturulmuştur. Küçük ölçekli problemlerin optimal şekilde çözülebilmesi ve sezgisel yöntemlerin değerlendirilmesinde referans olması amacıyla bir tamsayılı doğrusal programlama (MILP) modeli geliştirilmiştir. Ancak, problemin NP-zor yapısı nedeniyle büyük boyutlu örneklerde kesin çözüm yöntemleri hesaplama açısından uygulanabilirliğini kaybetmektedir. Bu durumu aşmak amacıyla, probleme özgü bir Genetik Algoritma (GA) tasarlanmıştır. Önerilen GA, yeni bir birey gösterimi, tek-nokta çaprazlama ve probleme özel mutasyon operatörleri ile birlikte, iş sıralamasını belirlemek üzere revize edilmiş V-şekilli çizelgeleme özelliğinden yararlanmaktadır. GA'nın farklı problem boyutları ve parametre ayarları altında gösterdiği performansı değerlendirmek amacıyla kapsamlı bir deneysel çalışma yürütülmüştür. Algoritmanın probleme uyarlanabilir bir yakınsama davranışı göstermesi için GA parametreleri ön testlerle optimize edilmiştir. Literatürdeki standart test problemleri ve bu çalışma kapsamında oluşturulan yeni veri kümeleri üzerinde kapsamlı deneyler gerçekleştirilmiştir. Elde edilen sonuçlar, önerilen GA'nın özellikle büyük ölçekli örneklerde MILP modeline kıyasla çok daha kısa sürede neredeyse optimal çözümler ürettiğini ortaya koymaktadır. Algoritma, çözüm kalitesi ve hesaplama verimliliği açısından güçlü bir performans sergilemekte olup, gerçek üretim ortamlarında karşılaşılan karmaşık çizelgeleme problemlerini çözmek için umut vadeden bir yaklaşım sunmaktadır.