GI
,'VI AT
l',,)0 017 \
EVALUASI DAN PERBANDINGAN PEMILIHAN FUNGSI-FUNGSI TUJUAN DALAM ALGORITMA LIST SCHEDULING
A. FAUZI FIRDAUS AS
e j
" ::
,. . --·
. .'
JURUSAN MATEMA TIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR
1999
RINGKASAN
A. FAUZI FIRDAUS AS. Evaluasi dau Perbandingau Pelllilihau Fungsi-fungsi Tujuan dalalll Algoritllla List Scheduling (Evaluation and Comparison on Objective Function Selection of List Scheduling A Igorilhl1ls). Dibilllbing oleh F AHREN BUKHARI dau PRAPTO TRI SUPRIYO. Algoritllla list scheduling lllerupakan salall satu algoritllla yang digunakau untuk lllenjadwalkau tugastugas dalalll graf asiklik berarah (directed acyclic graph), sebagai representasi aplikasi kOlllputer, pada sistelll llluitiprosesor. Kunci utaula a1goritllla ini adalall pernilihau fungsi tujuau yang digunakan sebagai
aeuan dalmn memilih pasangan tugas-prosesor. Pelllilihan fungsi tujuau yang tepat dalalll algoritllla list scheduling lllenjadi penting karena sangat lllenentukan kinerja yang dihasilkau. Kinerja algoritllla penjadwalan diukur dari seberapa lama waktu yang diperlukan untnk meI\jadwalkan seluruh tugas dalam graf pada sistem multiprosesor. Masalall yang kellludian muneul adalah, suatu fungsi tujuau yang digunakan untuk melllilih pasaugan tugas-prosesor dalalll algoritllla list-scheduling tidak selalu lllenampakkau kineIja yang baik pada beberapa situasi masalall penjadwalan. Atas dasar inilall, dHlam karya ihniah ini dilakukan perbandingan seeara eksperimental untuk mengevaluasi kinerja dari empat varian algoritllla list scheduling, yang saling berbeda dalam hal fungsi tujnan yang digunakan. Keempat algoritllla tersebut adalah highest-static-Ievel (HSL), highest-dynal1liclevel (HDL). earliest-static-level (EST), dan earliest-jinish-til1le (EFT). Pelllbandingan dilakukan dengau lllengilllplelllentasikan algoritma HSL, BDL. EST, dan EFT, dalmn suatu simulator penjadwalan. Sil11ulasi diIakukan dengan mcmbangkitkan graf-graf tugas secara acak untuk dijadwalkan pada sistem lllultiprosesor virtual lllenggunakan keelllpat metode tersebul. Ukuran kinerja yang diamati dalam hal ini adalah pruljang jadwal (dalam satuan waktu) yang dihasilkau aleh masingmasing algoritm3 dala1l11l1CIljadwaikan graf tugas yang telah dibangkitkan. Hasil simulasi mCllunjukkan. kincrja m3sing-masing aIgoritma sangat sensitif tcrhadap karakteristik graf tugas (rasio antara rata-rata bobot edge dan rata-rata bobot node) dan jumlah prosesor yang digunakan. Dalam kasus dimana rata-rata bobot node lebill besar dari rata-rata bobot edge dan jumlah prosesor yang digunakan tidak terlalu banyak, algoritma HSL dan HDL menunjukkan kinerja yang bagus. Namun dengan semakin mendominasinya rata-rata bobot edge terhadap rata-nIta bobot node dan prosesor tersedia daIam jumlah ellkup banyak. algoritllla EST dau EFT lllenampakkan kinerja yang lebih baik daripada BSL dan HDL. Untuk kasus tcrakhir peningkatan kinerja EST dan EFT sebesar 5%. Dalam kcbanyakan kasus, algoritllla EFT mcnunjukkan kinerja yang paling bagns diantara tiga aigaritllla laillllYa. Kata kunci: graf tugas asiklik berarah, sistem multiprosesor, penJadwalan, list sclzeduling
EVALUASIDAN PERBANDINGAN PEMILIHAN FUNGSI-FUNGSI TUJUAN DALAM ALGORITMA LIST SCHEDULING
A. FAUZI FIRDAUS AS
Skripsi diajukan sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Program Studi Matematika Komputasi
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 1999
Judul
Evaluasi dan Perbandingan Pemilihan FWlgsi-fungsi Tujuan dalam Algorilma List Scheduling
Nama
A. Fauzi Firdaus AS
NIM
G05301663
Menyelujui,
If. Fahren Bukhari. M.Sc. Pembimbing I
Drs. Praplo Tri Suprivo Pcmbimbing II
Mengela1mi,
1
If. Ainril Aman. M. Sc. elua Program Studi
'. 'Ii''it?
Tanggal Lulus : 30 Juli 1999
RIWAYATHIDUP Penulis dilahirkan di Sampang, Madura, pada tanggal 19 Febmati 1976 sebagai anak sulung dati lima bersaudara, dati pasangan H. Asmawidjaya dan St. Fauzah. Tahun 1993, penulis menyelesaikan pendidikan di SMA Negeri Torjun dan pada tahun yang sama diterima sebagai mahasiswa IPB melalui jalur Undangan Seleksi Masuk IPB (USMI). Pada tahun 1994 penulis mulai mengikuti perkuliahan di Jumsan Matematika, Fakultas Matematika dan Ihnu Pengetahuan Alam, dengan bidang minat Matematika Komputasi. Selama mengikuti perkuliahan, penulis menjadi asisten mata kuliah Algoritma dan Bahasa Pernrograman untuk program studi Matematika, Ihnu Komputer, dan Statistika IPB, pada tahun ajaran 199411995 dan 199511996. Tahun 1997 penulis juga pemah melakukan praktek lapang selama dua bulan pada salah satu penyedia jasa internet di Jakarta, PT UniNet Bhaktinusa. Sampai saat karya ilmiah ini dinyatakan layak lulus, penulis bekelja di pemsahaan pengembangan perangkat lunak sistem informasi, PT Mainlofins Global Sytem, bertempat di Jakarta, sebagai programmer sekaligus analis sistem.
