YOHANA SILVIA
K.2012.1.31942
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…..
- 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
|
- 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
|
- 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.
- 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
|
- 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.
- 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.
- 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
|
- 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
- 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