Penyelesaian Masalah Assignment (Penugasan) dengan Menggunakan Metode Hungarian

Assignment problem
Assignment problem adalah suatu masalah mengenai pengaturan pada individu (objek) untuk melaksanakan tugas (kegiatan), sehingga dengan demikian biaya yang dikeluarkan untuk pelaksanaan penugasan tersebut dapat diminimalkan. Salah satu dalam menyelesaikan persoalan ini adalah dengan menggunakan algoritma Hungarian. Algoritma Hungarian adalah salah satu algoritma yang digunakan untuk menyelesaikan persoalan masalah assignment.
Versi awalnya, yang dikenal dengan metode Hungarian, 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 Hungarian. Dengan menggunakan algoritma ini, solusi optimum sudah pasti akan ditemukan. Namun untuk hal ini kasusnya dibatasi, yaitu bila ingin menemukan solusi terbaik dengan nilai minimum (least cost search).
Keuntungan terbesar penggunaan algoritma Hungarian adalah kompleksitas algoritmanya yang polinomial. Metode yang digunakan dalam algoritma Hungarian dalam memecahkan masalah sangat sederhana dan mudah dipahami. Penerapannya  bahwa setiap sumber daya harus ditugasklan hanya untuk satu pekerjaan. Untuk suatu masalah penugasan n x n , jumlah penugasan yang mungkin dilakukan sama dengan n! (n faktorial) karena berpasangan satu-satu.
Masalah Minimisasi dalam suatu penugasan pekerjaan
Pada umumnya tingkat keterampilan, pengalaman kerja, latar belakang pendidikan, dan latihan setiap karyawan berbeda-beda.Sehingga dalam waktu penyelesaian pekerjaan yang sama itu berbeda juga. Dalam metode Hungarian sumber daya harus ditugaskan hanya untuk satu pekerjaan. Sebagai contoh, Suatu perusahaan kotak hadiah mempunyai lima pekerjaan yang berbeda, yaitu memotong karton, merekatkan kertas warna, memberi hiasan, merekatkan pita, dan membungkus. Dimana tugas-tugas tersebut akan diselesaikan oleh lima karyawan. Biaya penugasan seorang karyawan untuk masing-masing pekerjaan berbeda-beda.
Data pada table di bawah ini menunjukkan biaya penugasan karyawan perusahaan kotak kado untuk masing-masing  pekerjaan.

Karyawan/ pekerjaan	I(Rp)	II(Rp)	III(Rp)	IV(Rp)	V(Rp)
A	17.000,00	15.000,00	19.000,00	21.000,00	18.00,00
B	15.000,00	17.000,00	22.000,00	18.000,00	14.000,00
C	26.000,00	21.000,00	24.000,00	21.000,00	19.000,00
D	18.000,00	19.000,00	19.000,00	17.000,00	20.000,00
E	15.000,00	20.000,00	23.000,00	19.000,00	17.000,00

Langkah  pemecahannya adalah sebagai berikut :
selengkapnya…..

1. Membuat tabel matriks

Bila disederhanakan, maka tabel datanya dapat diubah menjadi tabel matriks di bawah ini

Karyawan/ pekerjaan	I	II	III	IV	V
A	17	15	19	21	18
B	15	17	22	18	14
C	26	21	24	21	19
D	18	19	19	17	20
E	15	20	23	19	17

1. Mencari nilai opportunity cost (elemen terkecil) tiap baris

Karyawan/ pekerjaan	I	II	III	IV	V
A	17	15	19	21	18
B	15	17	22	18	14
C	26	21	24	21	19
D	18	19	19	17	20
E	15	20	23	19	17

3. Menolkan OC
Nilai OC tiap baris digunakan untuk mengurangi tiap elemen dalam baris tersebut. Sehingga paling sedikit akan diperoleh satu elemen yang bernilai nol sebagai hasilnya. Seperti dalam tabel di bawah ini.

Karyawan/ pekerjaan	I	II	III	IV	V
A	2	0	4	6	3
B	1	3	8	4	0
C	7	2	5	2	0
D	1	2	2	0	3
E	0	5	8	4	2

1. Cek 0 di kolom

Cek setiap kolom, apakah sudah mengandung elemen 0.

Karyawan/ pekerjaan	I	II	III	IV	V
A	2	0	4	6	3
B	1	3	8	4	0
C	7	2	5	2	0
D	1	2	2	0	3
E	0	5	8	4	2

Pada kasus ini, kolom ketiga belum mempunyai elemen 0. Untuk itu, dilakukan langkah selanjutnya.

1. Mencari opportunity cost kolom yang belum mengandung 0 (kolom III)

Karyawan/ pekerjaan	I	II	III	IV	V
A	2	0	4	6	3
B	1	3	8	4	0
C	7	2	5	2	0
D	1	2	2	0	3
E	0	5	8	4	2

Selanjutnya, tiap elemen di kolom III dikurangi dengan OC kolom

Karyawan/ pekerjaan	I	II	III	IV	V
A	2	0	2	6	3
B	1	3	6	4	0
C	7	2	3	2	0
D	1	2	0	0	3
E	0	5	6	4	2

1. Membuat garis bantu

Karyawan/ pekerjaan	I	II	III	IV	V
A	2	0	2	6	3
B	1	3	6	4	0
C	7	2	3	2	0
D	1	2	0	0	3
E	0	5	6	4	2

Jumlah garis harus = jumlah pekerjaan
Jumlah garis pada tabel di atas adalah empat, jadi masih kurang satu.

1. Menentukan elemen yang belum dikenai garis bantu, lalu mencari  OC total

Karyawan/ pekerjaan	I	II	III	IV	V
A	2	0	2	6	3
B	1	3	6	4	0
C	7	2	3	2	0
D	1	2	0	0	3
E	0	5	6	4	2

Elemen yang belum dikenai garis bantu adalah elemen di kolom III baris A,B,C dan di kolom IV baris A, B, dan C. Sedangkan nilai opportunity costnya adalah 2.

1. Menolkan OC

Karyawan/ pekerjaan	I	II	III	IV	V
A	2	0	0	4	3
B	1	3	4	2	0
C	7	2	1	0	0
D	1	2	0	0	3
E	0	5	6	4	2

1. Membuat garis bantu total

Karyawan/ pekerjaan	I	II	III	IV	V
A	2	0	0	4	3
B	1	3	4	2	0
C	7	2	1	0	0
D	1	2	0	0	3
E	0	5	6	4	2

Tabel sudah optimal, karena jumlah garis = jumlah pekerjaan.
Jadi, berdasrkan tabel dapat dilihat bahwa:
Karyawan A cocok untuk pekerjaan I & II
Karyawan B cocok untuk pekerjaan V
Karyawan C cocok untuk pekerjaan IV & V
Karyawan D cocok untuk pekerjaan III & IV
Karyawan E cocok untuk pekerjaan I

1. Penugasan optimal

Karyawan A : pekerjaan II (merekatkan kertas warna)
Karyawan B : pekerjaan V (membungkus)
Karyawan C : pekerjaan IV (merekatkan pita)
Karyawan D : pekerjaan III (memberi hiasan)
Karyawan E : pekerjaan I (memotong karton)
10.  Kesimpulan
Jadi, penugasan di perusahaan kotak kado ialah:
Karyawan A mendapat tugas merekatkan kertas warna dengan biaya Rp15.000,00
Karyawan B mendapat tugas membungkus  dengan biaya Rp 14.000,00
Karyawan C mendapat tugas merekatkan pita dengan biaya Rp21.000,00
Karyawan D mendapat tugas memberi hiasan dengan biaya Rp19.000,00
Karyawan E mendapat tugas memotong karton dengan biaya Rp15.000,00

Sumber :  http:// cupzard.blogspot.com/2010/06/metode-hungarian.html