MASALAH PENUGASAN
Seperti masalah transportasi, masalah penugasan (assignment problem) merupakan kasus khusus dari masalah linear programming pada umumnya. Dalam dunia usaha (bisnis) dan industri, manajemen sering meng-hadapi masalahmasalah yang berhubungan dengan penugasan optimal dari bermacam-macam sumber yang produktif atau personalia yang mempunyai tingkat efisiensi yang berbeda-beda utk tugas yang berbeda
pula. Metode Hungarian (Hungarian Method) adalah salah satu dari bbrp teknik pemecahan masalah penugasan.
Untuk dapat menerapkan metode Hungarian,jumlah sumber-sumber yg ditugaskan harus sama persis dgn jumlah tugas yang akan diselesaikan. Selain itu, setiap sumber hrs ditugaskan hanya satu tugas. Jadi masalah penugasan akan mencakup sejumlah n sumber yg mempunyai n tugas. Ada n ! (n faktorial) penugasan yg mungkin dlm suatu masalah karena perpasangan satu-satu. Masalah ini dpt dijelaskan dengan mudah oleh bentuk matrik segiempat, dimana baris-barisnya menunjukkan sumber-sumber dan kolom-kolomnya menunjukkan tugas-tugas.
Masalah penugasan dapat dinyatakan secaramatematis dalam suatu bentuk Program Linearsebagai berikut :
Minimumkan (Maksimumkan) :
dengan kendala :
dan Xij 0 (Xij = Xij
2) dimana Cij adlh tetapan
yang telah diketahui.
(1). Masalah Minimisasi
1.1. Jumlah baris = jumlah kolom Suatu perusahaan kecil mempunyai 4 (empat) pekerjaan yg berbeda utk diselesaikan oleh 4 (empat) karyawan. Biaya penugasan seorang karyawan utk pekerjaan yg berbeda karena sifat pekerjaan yg berbeda-beda. Setiap karyawan mempunyai tingkat keterampilan, pengalaman
kerja dan latar belakang pendidikan serta latihan yg berbeda, sehingga biaya penyelesaian pekerjaan yg sama oleh para karyawan yg berlainan juga berbeda. Biaya penugasan karyawan utk masing-masing pekerjaan adalah sbb :
Karena metode Hongarian mensyaratkan perpasangan satu-satu, maka ada 4!=24 kemungkinan penugasan. Langkah-langkah penyelesaian
sebagai berikut :
(a). Merubah matriks biaya menjadi matriks opportunity cost, yaitu dgn memilih elemen terkecil dari setiap baris dari matriks biaya mula-mula utk mengurangi seluruh elemen (bilangan) dlm setiap baris. Tabel Reduced-Cost Matriks
___________________________________________________
Karyawan Pekerjaan (Rp/Unit)
I II III IV
___________________________________________________
A 15-15 20-15 18-15 22-15
B 14-14 16-14 21-14 17-14
C 25-20 20-20 23-20 20-20
D 17-16 18-16 18-16 16-16
___________________________________________________
(b). Reduced Cost Matrix di atas terus dikurangi utk mendapatkan Total Opportunity Cost Matrix. Hal ini dicapai dgn memilih elemen terkecil dari setiap kolom pada reduced cost matrix utk mengurangi seluruh elemen dlm kolom-kolom tsb. Pada contoh, hanya dilakukan pada kolom III karena semua kolom
lainnya telah mempunyai elemen yang bernilai nol. Bila langkah pertama telah menghasilkan paling sedikit satu nilai nol pada setiap kolom, langkah kedua ini dapat dihilangkan.
Total Opportunity Cost Matrix
___________________________________________________
Karyawan Pekerjaan (Rp/Unit)
I II III IV
___________________________________________________
A 0 5 3-2 7
B 0 2 7-2 3
C 5 0 3-2 0
D 1 2 2-2 0
___________________________________________________
Karyawan Pekerjaan (Rp/Unit)
I II III IV
___________________________________________________
A 0 5 1 7
B 0 2 5 3
C 5 0 1 0
D 1 2 0 0
___________________________________________________
(c). Mencari skedul penugasan dgn suatu total opportunity cost nol. Untuk mencapai penugasan ini dibutuhkan 4 “independent” dalam matrix. Ini berarti setiap karyawan hrs ditugaskan hanya utk satu pekerjaan dengan opp-cost- nol atau setiap pekerjaan hrs diselesaikan hanya oleh satu karyawan.
Prosedur praktis utk melakukan test optimalisasi adalah dgn menarik sejlh minimum grs orizontal dan /atau vertikal utk meliput seluruh elemen bernilai nol dlm total-opptcost matrix.
Total Opportunity Cost Matrix
___________________________________________________
Karyawan Pekerjaan (Rp/Unit)
I II III IV
___________________________________________________
A 0 5 1 7
B 0 2 5 3
C 5 0 1 0
D 1 2 0 0
___________________________________________________
(d). Untuk merevisi total-opp-cost matrix, pilih elemen terkecil yg belum terliput garis-garis opp-cost terendah) untuk mengurangi seluruh elemen yg belum terliput. Kemudian tambahkan dgn jlh yg sama pd seluruh elemen-elemen yg mempunyai dua garis yg saling bersilangan. Masukkan hasil ini pada matrix.
Revised Matrix & Test for Optimality
___________________________________________________
Karyawan Pekerjaan (Rp/Unit)
I II III IV
___________________________________________________
A 0 5-1 1-1 7-1
B 0 2-1 5-1 3-1
C 5+1 0 1 0
D 1+1 2 0 0
___________________________________________________
Revised Matrix & Test for Optimality
___________________________________________________
Karyawan Pekerjaan (Rp/Unit)
I II III IV
___________________________________________________
A 0 4 0 6
B 0 1 4 2
C 6 0 1 0
D 2 2 0 0
___________________________________________________
Skedul Penugasan : A - III = 18
B - I = 14
C - II = 20
D - IV = 10
-----------------------------
Total Biaya = 68
1.2. Jumlah baris ≠ jumlah kolom
Syarat untuk menyelesaikan persoalan penugasan dengan metode Hungarian adalah jumlah baris (jumlah pekerjaan) sama dengan jumlah kolom (jumlah karyawan). Pada kasus persoalan dimana jumlah baris
(jumlah pekerjaan) tidak sama dengan kolom (jumlah karyawan) , maka harus menyeimbangkan jumlah baris = jumlah kolom. Tekniknya dengan menambah variabel dummy bernilai nol pada baris atau kolom. Jika baris < kolom maka variabel dummy dummy ditambahkan pada baris, sebaliknya jika kolom < baris, maka variabel dummy ditambahkan pada kolom.
Seperti masalah transportasi, masalah penugasan (assignment problem) merupakan kasus khusus dari masalah linear programming pada umumnya. Dalam dunia usaha (bisnis) dan industri, manajemen sering meng-hadapi masalahmasalah yang berhubungan dengan penugasan optimal dari bermacam-macam sumber yang produktif atau personalia yang mempunyai tingkat efisiensi yang berbeda-beda utk tugas yang berbeda
pula. Metode Hungarian (Hungarian Method) adalah salah satu dari bbrp teknik pemecahan masalah penugasan.
Untuk dapat menerapkan metode Hungarian,jumlah sumber-sumber yg ditugaskan harus sama persis dgn jumlah tugas yang akan diselesaikan. Selain itu, setiap sumber hrs ditugaskan hanya satu tugas. Jadi masalah penugasan akan mencakup sejumlah n sumber yg mempunyai n tugas. Ada n ! (n faktorial) penugasan yg mungkin dlm suatu masalah karena perpasangan satu-satu. Masalah ini dpt dijelaskan dengan mudah oleh bentuk matrik segiempat, dimana baris-barisnya menunjukkan sumber-sumber dan kolom-kolomnya menunjukkan tugas-tugas.
Masalah penugasan dapat dinyatakan secaramatematis dalam suatu bentuk Program Linearsebagai berikut :
Minimumkan (Maksimumkan) :
dengan kendala :
dan Xij 0 (Xij = Xij
2) dimana Cij adlh tetapan
yang telah diketahui.
(1). Masalah Minimisasi
1.1. Jumlah baris = jumlah kolom Suatu perusahaan kecil mempunyai 4 (empat) pekerjaan yg berbeda utk diselesaikan oleh 4 (empat) karyawan. Biaya penugasan seorang karyawan utk pekerjaan yg berbeda karena sifat pekerjaan yg berbeda-beda. Setiap karyawan mempunyai tingkat keterampilan, pengalaman
kerja dan latar belakang pendidikan serta latihan yg berbeda, sehingga biaya penyelesaian pekerjaan yg sama oleh para karyawan yg berlainan juga berbeda. Biaya penugasan karyawan utk masing-masing pekerjaan adalah sbb :
___________________________________________________
Karyawan Pekerjaan (Rp/Unit)
I II III IV
___________________________________________________
A 15 20 18 22
B 14 16 21 17
C 25 20 23 20
D 17 18 18 16
___________________________________________________Karena metode Hongarian mensyaratkan perpasangan satu-satu, maka ada 4!=24 kemungkinan penugasan. Langkah-langkah penyelesaian
sebagai berikut :
(a). Merubah matriks biaya menjadi matriks opportunity cost, yaitu dgn memilih elemen terkecil dari setiap baris dari matriks biaya mula-mula utk mengurangi seluruh elemen (bilangan) dlm setiap baris. Tabel Reduced-Cost Matriks
___________________________________________________
Karyawan Pekerjaan (Rp/Unit)
I II III IV
___________________________________________________
A 15-15 20-15 18-15 22-15
B 14-14 16-14 21-14 17-14
C 25-20 20-20 23-20 20-20
D 17-16 18-16 18-16 16-16
___________________________________________________
(b). Reduced Cost Matrix di atas terus dikurangi utk mendapatkan Total Opportunity Cost Matrix. Hal ini dicapai dgn memilih elemen terkecil dari setiap kolom pada reduced cost matrix utk mengurangi seluruh elemen dlm kolom-kolom tsb. Pada contoh, hanya dilakukan pada kolom III karena semua kolom
lainnya telah mempunyai elemen yang bernilai nol. Bila langkah pertama telah menghasilkan paling sedikit satu nilai nol pada setiap kolom, langkah kedua ini dapat dihilangkan.
Total Opportunity Cost Matrix
___________________________________________________
Karyawan Pekerjaan (Rp/Unit)
I II III IV
___________________________________________________
A 0 5 3-2 7
B 0 2 7-2 3
C 5 0 3-2 0
D 1 2 2-2 0
___________________________________________________
Karyawan Pekerjaan (Rp/Unit)
I II III IV
___________________________________________________
A 0 5 1 7
B 0 2 5 3
C 5 0 1 0
D 1 2 0 0
___________________________________________________
(c). Mencari skedul penugasan dgn suatu total opportunity cost nol. Untuk mencapai penugasan ini dibutuhkan 4 “independent” dalam matrix. Ini berarti setiap karyawan hrs ditugaskan hanya utk satu pekerjaan dengan opp-cost- nol atau setiap pekerjaan hrs diselesaikan hanya oleh satu karyawan.
Prosedur praktis utk melakukan test optimalisasi adalah dgn menarik sejlh minimum grs orizontal dan /atau vertikal utk meliput seluruh elemen bernilai nol dlm total-opptcost matrix.
Total Opportunity Cost Matrix
___________________________________________________
Karyawan Pekerjaan (Rp/Unit)
I II III IV
___________________________________________________
A 0 5 1 7
B 0 2 5 3
C 5 0 1 0
D 1 2 0 0
___________________________________________________
(d). Untuk merevisi total-opp-cost matrix, pilih elemen terkecil yg belum terliput garis-garis opp-cost terendah) untuk mengurangi seluruh elemen yg belum terliput. Kemudian tambahkan dgn jlh yg sama pd seluruh elemen-elemen yg mempunyai dua garis yg saling bersilangan. Masukkan hasil ini pada matrix.
Revised Matrix & Test for Optimality
___________________________________________________
Karyawan Pekerjaan (Rp/Unit)
I II III IV
___________________________________________________
A 0 5-1 1-1 7-1
B 0 2-1 5-1 3-1
C 5+1 0 1 0
D 1+1 2 0 0
___________________________________________________
Revised Matrix & Test for Optimality
___________________________________________________
Karyawan Pekerjaan (Rp/Unit)
I II III IV
___________________________________________________
A 0 4 0 6
B 0 1 4 2
C 6 0 1 0
D 2 2 0 0
___________________________________________________
Skedul Penugasan : A - III = 18
B - I = 14
C - II = 20
D - IV = 10
-----------------------------
Total Biaya = 68
1.2. Jumlah baris ≠ jumlah kolom
Syarat untuk menyelesaikan persoalan penugasan dengan metode Hungarian adalah jumlah baris (jumlah pekerjaan) sama dengan jumlah kolom (jumlah karyawan). Pada kasus persoalan dimana jumlah baris
(jumlah pekerjaan) tidak sama dengan kolom (jumlah karyawan) , maka harus menyeimbangkan jumlah baris = jumlah kolom. Tekniknya dengan menambah variabel dummy bernilai nol pada baris atau kolom. Jika baris < kolom maka variabel dummy dummy ditambahkan pada baris, sebaliknya jika kolom < baris, maka variabel dummy ditambahkan pada kolom.
1 comments:
gaada program c++ nya kah? :3
EmoticonEmoticon