BAB 1
PENDAHULUAN
1.1 Latar Belakang Dalam dunia informatika, assignment Problem yang biasa dibentuk dengan matriks berbobot merupakan salah satu masalah terbesar, dimana masalah ini merupakan masalah yang metode penyelesaiannya cukup kompleks. Assignment Problem adalah suatu masalah mengenai pengaturan pada individu (objek) untuk melaksanakan tugas atau pekerjaan, sehingga dengan demikian biaya atau waktu yang dipergunakan untuk pelaksanaan tugas atau pekerjaan tersebut dapat diminimalkan.
Masalah penugasan (Assignment Problem), seperti juga
masalah
transprotasi merupakan salah satu kasus-kasus yang ditemui dalam program linier (linier programming). Dalam masalah penugasan akan didelegasikan sejumlah tugas (assignment) kepada sejumlah penerima tugas (Assignee) dalam basis satusatu. Jadi masalah penugasan ini diasumsikan bahwa jumlah assignment sama dengan jumlah assignee. Sehingga data pokok yang harus dimiliki untuk menyelesaikan suatu masalah penugasan adalah jumlah assignment dan assignee.
Algoritma Brute Force adalah salah satu algoritma yang disarankan untuk digunakan dalam menyelesaikan persoalan ini, yang mana dalam algoritma ini seluruh kemungkinan solusi diperhitungkan sebagai kandidat solusi. Dan algoritma penyelesaian menggunakan kompleksitas faktorial. Tentu saja hal ini sangat menggunakan resource yang besar dan penyelesaian dengan metode ini menjadi tidak efisien.
Universitas Sumatera Utara
Metode lain untuk menyelesaikan masalah assignment problem adalah dengan menggunakan Algoritma Hungari. Algoritma Hungari adalah salah satu algoritma yang digunakan untuk menyelesaikan persoalan assignment. Awalnya dikenal dengan metode Hungarian , yang ditemukan dan dipublikasikan oleh Harold Kuhn pada tahun 1955. Algoritma ini kemudian diperbaiki oleh James Munkres pada tahun 1957. Oleh karena itu, algoritma ini kemudian dikenal juga dengan nama algoritma Kuhn-Munkres. Algoritma yang dikembangkan oleh Kuhn ini didasarkan pada hasil kerja dua orang matematikawan asal Hungaria lainnya, yaitu Denes Konig dan Jeno Egervary.
Keberhasilan Kuhn menggabungkan dua buah penemuan matematis dari Jeno Egervary menjadi satu bagian merupakan hal utama yang menginspirasikan lahirnya Algoritma Hungari. Dengan menggunakan algoritma ini, solusi optimum sudah pasti ditemukan. Namun untuk hal ini kasusnya dibatasi , yaitu apabila ingin menemukan solusi terbaik dengan nilai minimum (least ost search).
Tujuan yang ingin dicapai dalam memecahkan persoalan penugasan adalah berusaha untuk menjadwalkan setiap assignee pada suatu assignment sedemikian rupa sehingga kerugian yang ditimbulkan minimal atau keuntungan yang didapatkan maksimal. Yang dimaksud kerugian dalam hal ini adalah biaya, jarak atau waktu, sedangkan keuntungan adalah pendapatan, laba atau nilai kemenangan. Sehingga jelas dalam persoalan penugasan ada dua jenis masalah yaitu masalah minimalisasi dan masalah maksimalisasi.
Keuntungan terbesar penggunaan algoritma Hungari adalah kompleksitas algoritmanya yang polynomial. Metode yang digunakan dalam algoritma Hungari dalam memecahkan masalah sangat sederhana dan mudah dipahami. Metode ini akan diaplikasikan penulis dalam pemecahan masalah matriks berbobot, dimana masalah yang ingin dipecahkan adalah mencari solusi terbaik minimum waktu pada tim renang estafet “Tirta Prima - Medan” gaya ganti 4 x 100 meter.
Universitas Sumatera Utara
1.2 Perumusan Masalah Sesuai dengan latar belakang yang telah dikemukakan penulis pada pendahuluan, maka yang menjadi pokok permasalahan adalah bagaimana cara menyelesaikan assignment problem pada kasus jumlah baris sama dengan jumlah kolom (m = n). dalam hal ini adalah bagaimana mencari waktu minimal oleh Tim renang estafet “Tirta Prima - Medan”, sehingga diperoleh hasil yang optimal (waktu yang minimal) dengan menggunakan metode Hungari.
1.3 Batasan Masalah Untuk lebih fokus dan tidak menyimpang dari tujuan, maka penulis mengadakan pembatasan masalah, yaitu : a. Metode yang digunakan adalah Metode Hungari b. Masalah yang dibahas dalam assignment problem pada kasus m = n. dalam hal ini adalah bagaimana mencari waktu minimal oleh Tim renang estafet “Tirta Prima - Medan” dalam menghadapi lomba renang estafet gaya ganti 4 x 100 meter. c. Hasil akhir yang akan ditemukan adalah solusi optimal assignment problem dengan metode Hungari pada minimalisasi waktu tim renang “Tirta Prima - Medan”, dimana waktu yang digunakan tim tersebut dapat lebih minimum.
1.4 Tujuan Penelitian Tujuan dari penelitian ini terkait dengan pokok permasalahan yang telah diuraikan diatas adalah sebagai berikut : 1. Menjelaskan bagaimana cara menyelesaikan masalah penugasan pada kasus m = n menggunakan metode Hungari 2. Menjelaskan bagaimana cara menyelesaikan masalah penugasan pada kasus-kasus khusus menggunakan metode Hungari.
Universitas Sumatera Utara
1.5 Manfaat Penelitian Adapun manfaat dari penelitian ini adalah : 1. Memberikan tambahan wawasan dan pengetahuan tentang masalah penugasan. 2. Menjelaskan cara penyelesaian masalah penugasan pada kasus m = n dengan metode Hungari 3. Memperoleh waktu minimal yang digunakan tim renang estafet “Tirta Prima - Medan” pada lomba renang estafet. 4. Menjelaskan cara penyelesaian masalah penugasan pada kasus-kasus khusus dengan metode Hungari.
1.6 Metodologi Penelitian Metode penelitian yang akan digunakan adalah penelitian literature dan studi kasus, dengan prosedur sebagai berikut : a. Menguraikan teori dasar yang menunjang terhadap pembahasan yang diperoleh dari jurnal, buku, dan internet. b. Melakukan survei untuk mengumpulkan data kecepatan perenang tiap gaya dari tim renang estafet “Tirta Prima - Medan”. c. Mengolah data dengan mencari solusi optimal assignment problem dengan menggunakan metode Hungari pada kasus m = n. d. Menyusun rangkuman e. Penarikan kesimpulan.
Universitas Sumatera Utara
1.7 Tinjauan Pustaka Sebagai pendukung dalam penulisan tugas akhir ini, penulis menggunakan beberapa buku atau jurnal antara lain sebagai berikut :
(J. Supranto, “Linier Programming”, 1983;280). Membahas tentang efisiensi metode Hungari dibandingkan dengan metode yang telah ada. Persoalan penugasan (Assignment Problem) termasuk jenis persoalan transportasi. Dengan demikian persoalan penugasan dapat dipecahkan dengan metode-metode yang dapat dipergunakan untuk memecahkan masalah transportasi. Selain ada metode transportasi untuk memecahkan persoalan transportasi juga ada metode penugasan untuk memecahkan masalah penugasan. Metode ini untuk beberapa hal merupakan metode yang lebih efisien apabila dibandingkan dengan metode simpleks.
(Fien Zulfikarijah, “Operation Research”). Tentang syarat-syarat dalam metode penugasan dan model matematis dalam metode penugasan. Persyaratan Metode Penugasan : 1. Jumlah sumber (m) yang ditugaskan harus sama dengan jumlah tugas (n) yang harus diselesaikan. 2. Setiap sumber hanya mengerjakan satu tugas 3. Apabila jumlah sumber tidak sama dengan jumlah tugas, maka ditambahkan variable dummy 4. Terdapat
dua
permasalahan
yang
bisa
diselesaikan
yaitu
memaksimumkan keuntungan atau meminimumkan kerugian (biaya, waktu atau jarak) Secara matematis masalah penugasan dapat dinyatakan dalam bentuk linier programming dengan variable keputusannya adalah :
=
Universitas Sumatera Utara
Dengan mengasumsikan Z sebagai biaya total, maka model masalah penugasan menjadi n
minimumkan z = ∑∑ cij xij =i 1 =j 1
Dengan batasan :
n
∑x i =1
ij
= 1 , i = 1,2, , n
ij
= 1 , j = 1,2, , n ,
n
∑x j =1
x ij = 0 or 1
0, untuk semua i dan j. (
adlah biner untuk semua i dan j)
Dimana :
adalah tetapan yang telah ditentukan
(Johnsonbaugh Richard,2001; 265) Graf G adalah pasangan himpunan (V,E) dimana V adalah himpunan dari simpul (vertex) dan E adalah himpunan dari sisi yang menghubungkan sepasang simpul.
(Munir Rinaldi,2003). Algoritma Branch and Bounds merupakan metode pencarian dalam ruang solusi yang ditransformasikan dalam bentuk ruang pohon pencarian.
Universitas Sumatera Utara