PARALEL MAKİNELİ ÇİZELGELEMEDE TOPLAM TAMAMLANMA ZAMANI VE MAKSİMUM GECİKMENİN ENKÜÇÜKLENMESİ

Authors : Tamer EREN, Ertan GÜNER

Pages : 21-32

View : 21 | Download : 13

Publication Date : 2006-03-01

Article Type : Research Paper

Abstract :Bu çalışmada iki ölçütlü özdeş iki paralel makineli çizelgeleme problemi incelenmiştir. Problemin amaç fonksiyonu toplam tamamlanma zamanı ve maksimum gecikmenin ağırlıklı toplamını en küçüklemektir. Tamamlanma zamanı ve maksimum gecikme çizelgeleme literatüründe en çok göz önüne alınan ölçütlerdendir. NP-zor yapıda olan bu problemin çözümü için, 2/2/32/ 23 nnn ++ değişkenli ve 23n kısıtlı bir tamsayılı programlama modeli geliştirilmiştir (burada n iş sayısını ifade etmektedir). Tam sayılı programlama modelinin hesaplama zamanı ve yüksek hesaplama karmaşıklığı dolayısı ile 20 işe kadar olan problemlerin çözümleri gerçekleştirilebilmiştir. Problemin daha büyük boyutlu çözümlerini gerçekleştirmek için çizelgelemede iyi bilinen dağıtım kurallarına göre belirlenen sıralar başlangıç çözümü olarak alınarak tabu arama yöntemleri (Tabu I, Tabu II ve Tabu III) ve rassal arama yöntemi geliştirilmiş ve problemin 1000 işe kadar çözümleri bu yöntemlerle belirlenmiştir.
Keywords : Paralel makineli çizelgeleme, iki ölçüt, tamsayılı programlama, sezgisel yöntemler