Algoritma heuristik untuk masalah penugasan dalam sistim terdistribusi

SUJALWO, Drs. Retantyo Wardoyo, MSc.,PhD

2001 | Tesis | S2 Komputer

Masalah penugasan task (task assignment) dengan himpunan k task yang berkomunikasi untuk dieksekusi pada sistem terdistribusi dengan n buah prosessor merupakan salah satu permasalahan dalam sistem terdistribusi. Setiap task diberikan pada salah satu prosessor, dengan hubungan tiap — tiap task bersifat bebas. Pada penelitian ini faktor penentu distribusi melibatkan bobot pekerjaan yang didasarkan pada biaya eksekusi dan biaya komunikasi. Untuk model network flow dengan pendekatan graf dan menggunakan algoritma heuristik yang mendasarkan biaya komunikasi dan eksekusi mempunyai kecenderungan Ice prosessor yang sama, dalam arti distribusi kurang optimal. Penyertaan biaya interferensi mencerminkan tingkat inkompatibilitas antar dua task. Biaya komunikasi yang tinggi berfungsi sebagai daya tank — menarik antar task yang menyebabkan task — task tersebut diproses ke prosessor yang sama. Sedangkan biaya interferensi berfungsi sebagai daya tolak antar task, yang menyebabkan task — task itu menjadi terdistribusi ke banyak prosessor. Hasil simulasi algoritma heuristik menunjukkan pada konfigurasi 5 task dengan 3 prosessor untuk data acak berturut turut adalah sebagai berikut : Weibull 44%, Exponensial 24%, Poisson 4% dan Uni from 0% terdistribusi optimal (semua prosessor terpakai).

Task assignment problem with a set of k tasks in communication to be executed in a distributed system with n processors is a problem in a distribution system. Every task is a assigned to a processor in which every task is independent from the others. In this research, the determining factor for the distribution involves the work load based on the execution and communication costs. Network flow models using graph approach and heuristic algorithm based on the execution and communication cost tends to the same processor, i.e. the distribution is less optimum. The involvement of interference cost shows incompatibilty level between two tasks. High communication costs make the tasks are assigned to the same processor. On the other hand, interference costs make the tasks are assigned to different and many processors. The result of the heuristic algorithm simulation shows a configuration of 5 tasks with 3 processors from the random data is as follows : Weibull 44%, Exponential 24%, Poisson 4% and Uniform 0% are optimally distributed (All processors are used).

Kata Kunci : Sistem terdistribusi, task assignment, distributed system