Multilevel heuristics for task assignment in distributed systems
Dağıtık sistemlerde çok düzeyli görev atama algoritmaları
- Tez No: 79320
- Danışmanlar: DOÇ. DR. CEVDET AYKANAT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Algoritmalar, Dağıtık sistemler, Task assignment, distributed systems, task clustering, multilevel task assignment methods, Kernighan-Lin Heuristic, Algorithms
- Yıl: 1998
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
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ı
Özet (Çeviri)
Task assignment problem deals with assigning tasks to processors in order to minimize the sum of execution and communication costs in a distributed sys tem. In this work, we propose a novel task clustering scheme which considers the differences between the execution times of tasks to be clustered as well as the communication costs between them. We use this clustering approach with proper assignment schemes to implement two-phase assignment algorithms which can be used to find suboptimal solutions to any task assignment prob lem. In addition, we adapt the multilevel scheme used in graph/hypergraph partitioning to the task assignment. Multilevel assignment algorithms reduce the size of the original problem by collapsing tasks, find an initial assignment on the smaller problem, and then projects it towards the original problem by successively refining the assignment at each level. We propose several clus tering schemes for multilevel assignment algorithms. The performance of all proposed algorithms are evaluated through an experimental study where the as signment qualities are compared with two up-to-date heuristics. Experimental results show that our algorithms substantially outperform both of the existing heuristics.
Benzer Tezler
- Independent task assignment for heterogeneous systems
Heterojen sistemler için bağımsız iş atama
ERTUĞRUL KARTAL TABAK
Doktora
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Bölümü
PROF. DR. CEVDET AYKANAT
- Kan tedarik zinciri ağ tasarımı ve süreç yönetiminde çok aşamalı stokastik programlama modelleri ve çözüm yaklaşımı
Multi-stage stochastic programming models and solution approach for blood supply chain network design and management
GÜL İMAMOĞLU
Doktora
Türkçe
2024
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. Y. İLKER TOPÇU
PROF. DR. NEZİR AYDIN
- Robotik süreç otomasyonu için iş çizelgeleme algoritması
Job scheduling algorithm for robotic process automation
GÜLŞAH DORUK
Yüksek Lisans
Türkçe
2022
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
DOÇ. DR. OSMAN KAAN EROL
- İşgören performansı dikkate alınarak U-tipi montaj hatlarının dengelenmesi
Balancing U-shaped assembly lines by considering worker performance
MEHMET KÜRŞAT ÖKSÜZ
Yüksek Lisans
Türkçe
2015
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ŞULE ITIR SATOĞLU
- Uzman sistem teknolojisi ve çizelgeleme uygulaması
The technology of expert system and applications of scheduling
TARIK ÇAKAR
Yüksek Lisans
Türkçe
1991
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiY.DOÇ.DR. ORHAN KURUÜZÜM