BİLDİRİLER

BİLDİRİ DETAY

Melda HAŞILOĞLU, Zehra KAMIŞLI ÖZTÜRK
TEK MAKİNE ÇİZELGELEME PROBLEMİNİN GENETİK ALGORİTMA İLE ÇÖZÜMÜ
 
Çizelgeleme problemleri kombinatoryal problemler sınıfındadır. Çözüm yaklaşımları problemin yapısına ve atölye şekline bağlı olarak değişir. Tek makine çizelgeleme problemi çizelgeleme problemleri sınıfındaki en temel problemlerden biridir. N tane iş tek makinede işlenmek üzere tek işlemden geçer. Her bir işin işlem süresi ve termin süreleri bellidir. En büyük gecikmenin en küçüklenmesi için, en erken teslim süresi (earliest due date) kuralı bu problemin çözümünde en sık kullanılan yöntemlerdendir. Son yıllarda yapılan çalışmalarda bu tür optimizasyon problemleri, genetik algoritma kullanılarak da çözülmektedir. Ancak bu tür problemlerde, genetik algoritmanın çözüm performansında etkili olan operatör ve parametrelerin belirlenmesi önemli araştırma konularındandır. Bu çalışmada tek makine çizelgeleme problemlerinin genetik algoritma ile çözümünde uygun çaprazlama ve mutasyon operatörü değerlendirilmiş ve yapılan deneyler sonucunda öneriler geliştirilmiştir. Yine bu süreçte iki farklı iş sayısı için problem verileri türetilmiş ve önerilen operatörlerle popülasyon boyutu ve iterasyon sayıları değiştirilerek algoritma çözdürülmüş ve sonuçları karşılaştırılmıştır. Yapılan deney sonucunda 40 iş ve 60 iş olmak üzere iki farklı test verileri için sağdan tek nokta sıra çaprazlama ve mutasyon operatörü olarak insert kullanılan algoritmada en iyi sonuçtan uzaklaşma riskinin daha düşük olduğu bulunmuştur. Buradan bu ikili ile kurulan algoritmalarda performansın daha yüksek olduğu sonucu çıkarılabilir. Problem türleri olarak kıyaslandığında ise iterasyon sayısındaki artışın algoritmanın performansını iyi yönde etkilediği tespit edilmiştir. Bunun yanında mutasyon operatörü olarak 2-opt ve 3-opt kullanıldığı zaman çalışmada ele alınan problemin test verilerinin en iyi sonucuna ulaşılamamıştır. Bu nedenle 2-opt ve 3-opt bu problemin çözümünde kullanıldığında önerilen genetik algoritmanın performansını düşürdüğü kabul edilebilir. Buna bağlı olarak bu iki mutasyon operatörünün çalışmadaki problem için uygun olmadığı sonucuna ulaşılmıştır.

Anahtar Kelimeler: Tek Makine Çizelgeleme, Genetik Algoritma, Sezgisel Yöntemler



 


Keywords: