Minggu, 04 Januari 2015

QUANTITATIVE MANAGEMENT

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…..
  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