Multilevel heuristics for task assignment in distributed systems

Görev atama probleminin amacı bir dağıtık sistemdeki görevlerin işlemcilere yürütme ve iletişim giderlerinin toplamını en küçük yapacak biçimde atamaktır. Bu çalışmada, görevlerin iletişim zamanlarının yanı sıra yürütme zamanları arasındaki farkı da dikkate alan yeni bir topaklama yöntemi önerilmiştir. Bu topaklama yöntemi uygun atama yöntemleri ile birlikte her türlü görev atama problemine en iyiye yakın çözümler bulabilecek olan iki-evreli atama algo ritmaları oluşturmak için kullanılmıştır. Bunlara ek olarak, çizge/hiperçizge parçalamada kullanılan çok düzeyli çizenek görev atama problemine uyarlan mıştır. Çok düzeyli atama algoritmaları görevleri birleştirerek asıl problemi küçültür, en küçük problem için bir başlangıç ataması bulur, sonra bu ata mayı her düzeyde iyileştirerek asıl probleme doğru yansıtır. Bu çalışmada çok düzeyli atama algoritmaları için bir çok topaklama çizeneği önerilmiştir. Bütün önerilen algoritmalar iki güncel algoritma ile karşılaştırılmış ve başarımları bir deneysel çalışma ile değerlendirilmiştir. Deney sonuçları göstermiştir ki önerilen algoritmalar varolan iki algoritmadan da daha iyi çalışmaktadır. Anahtar kelimeler. Görev atama, dağıtık sistemler, görev topaklama, çok düzeyli görev atama yöntemleri, Kerninghan-Lin algoritması