MODEL PENUGASAN MENGGUNAKAN METODE HUNGARIAN

BAB  I

PENDAHULUAN 
1.1 Latar belakang 

Masalah penugasan berkaitan dengan keinginan perusahaan dalam mendapatkan pembagian atau alokasi tugas (penugasan) yang optimal, dalam arti "apabila penugasan tersebut berkaitan dengan keuntungan, maka bagaimana alokasi tugas atau penugasan tersebut dapat memberikan keuntungan yang maksimal, begitu pula sebaliknya jika menyangkut biaya.

MODEL PENUGASAN MENGGUNAKAN METODE HUNGARIAN
Penyelesaian masalah penugasan biasanya dilakukan dengan menggunakan metode hungarian yang pada tahun 1916 dikembangkan oleh seorang ahli matematika berkebangsaan Hungaria bernama D KOnig. 

Secara umum Metode Hungarian dapat diartikan adalah metode yang memodifikasi baris dan kolom dalam matriks efektifitas sampai muncul sebuah komponen nol tunggal dalam setiap baris atau kolom yang dapat dipilih sebagai alokasi penugasan. Sedangkan metode penugasan adalah metode yang digunakan untuk memecahkan masalah-masalah yang berhubungan dengan alokasi optimal dari berbagai macam sumber daya yang produktif. 

1.2 Rumusan Masalah 

Adapun rumusan masalah yang akan dibahas adalah : 

- Apa itu masalah penugasan ?
- Bagaimana langkah-langkah penyelesaian masalah penugasan ?
- Bagaimana penerapan masalah minimisasi ?
- Bagaimana penerapan masalah maksimisasi ?

1.3 Tujuan Masalah 

Adapun tujuan masalah yang akan dibahas adalah: 

- Untuk dapat mengetahui apa pengertian dari masalah penugasan 
- Untuk dapat mengetahui bagaimana langkah-langkah penyelesaian masalah penugasan 
- Untuk dapat mengetahui bagaimana penerapan masalah minimisasi 
- Untuk dapat mengetahui bagaimana penerapan masalah maksimisasi 

BAB II 

PEMBAHASAN 

2.1 Masalah Penugasan 

Seperti masalah transportasi, masalah penugasan (assignment problem) merupakan suatu kasus khusus dari masalah linier programming pada umumnya. Dalam dunia usaha (bisnis) dan industry , manajemen sering menghadapi masalah-masalah yang berhubungan dengan penugasan optimal dari bermacam macam sumber yang produktif atau personali yang mempunyai tingkat efisiensi yang berbeda beda untuk tugas yang berbeda beda pula. 

Metode Hungarian (Hungarian Method) adalah salah satu dari beberapa teknik-teknik pemecahan yang tersedia untuk masalah- masalah penugasan. Metode ini mula-mula dikembangkan oleh seorang ahli matematika berkebangsaan Hungaria yang bernama D. Konig dalam tahun 1916. 

Untuk dapat menerapkan metode hungarian, jumlah sumber-sumber yang ditugaskan harus sama persis dengan jumlah tugas yang akan diselesaikan. Selain itu, setiap sumber harus ditugaskan hanya untuk satu tugas. Jadi, masalah penugasan akan mncakup sejumlah n sumber yang mempunyai n tugas. Ada n ! (n factorial) pesatu nugasan yang mungkin dalam suatu masalah karena perpasangan satu-satu. Masalh ini dapat dijelaskan dengan mudah oelh bentuk matriks segi empat, dimana baris-barisnya menunjukkan sumber-sumber dan kolom-kolomnya menunjukkan tugas-tugas. 

2.2 Langkah-langkah penyelesaian masalah penugasan yang normal adalah: 

1. Identifikasi dan penyederhanaan masalah Dibuat dalam bentuk tabel penugasan 

2. Minimalkan; Untuk kasus minimalisasi, maka perlu mencari nilai terkecil setiap baris, kemudian menggunakan nilai terkecil tersebut untuk mengurangi semua nilai yang ada pada baris yang sama. 

Maksimalkan; Untuk kasus maksimalisasi, maka perlu mencari nilai-nilai tertinggi setiap baris., kemudian nilai tertinggi tersebut dikurangi dengan nilai-nilai yang ada pada baris yang sama. 

3. Memastikan semua baris dan kolom sudah memiliki nilai nol. 

Apabila masih ada baris atau kolom yang belum memiliki nilai nol, maka dicari nilai terkecil pada baris atau kolom tersebut untuk kemudian digunakan untuk mengurangi semua nilai yang ada pada baris atau kolom tersebut. 

4. Memastikan tidak terjadi bentrok pada nilai nol 

Dengan kata lain, apakah nilai nol ( yang mewakili penugasan) mengalami bentrok atau menjadi rebutan bagi sumber daya lain. Jika iya, maka masih perlu dipotimalkan. 

Setelah semua baris dan kolom memiliki nilia nol, maka langkah selanjutnya adalah memastikan atau mengecek apakah dalam tabel penugasan tersebut telah berhasil ditemukan nilai nol sebanyak sumber daya (bisa karyawan, mesin, alat transportasi dll) yang tercermin dengan jumlah barisnya.

Misalnya jika yang akan ditugaskan adalah 4 karyawan, maka harus ditemukan nilai nol 4 buah yang terletak di baris dan kolom yang berbeda. Sebaiknya dimulai dari baris yang hanya memiliki satu nilai nol. Langkah ini mengandung arti bahwa setiap karyawan hanya dapat ditugaskan pada satu pekerjaan saja. 

5. Menarik garis yang menghubungkan nol 

Bila belum, maka langkah selanjutnya adalah menarik garis yang menghubungkan minimal dua buah nilai nol dalam tabel penugasan tersebut. 

6. Mengurangi nilai di luar garis dan menambah nilai di dalam garis 

Selanjutnya, perhatikan nilai-nilaiyang belum terkena garis. Pilih nilai yang paling kecil kemudian pergunakan untuk mengurangi nila-nilai yang belum terkena garis dan gunakan untuk menambah nilai-nilai yang terkena garis ganda (dua kali) 

7. Sudahkah optimal? 

Dari hasil langkah ke-6 tersebut, apakah sudah didapatkan nilai nol sejumlah sumber daya, yang juga tercermin dengan jumlah barisnya. 

Jika sudah, maka masalah penugasan telah optimal, tapi jika belum maka silahkan ulangi langkah penyelesaian ke-5 

Sebagai catatan, kasus penugasan dianggap normal bila jumlah sumber daya yang akan ditugaskan dan jumlah pekerjaan atau tujuan adalah sama. 

2.3 Masalah Minimisasi (untuk kasus normal) 

Suatu perusahaan kecil mempunyai 4 (empat) pekerjaan yang berbeda untuk diselesaikan oleh 4 (empat) orang karyawan. Biaya penugasan seorang karyawan untuk pekerjaan yang berbeda adalah berbeda karena sifat pekerjaan yang berbeda-beda. Setiap karyawan mempunyai tingkat keterampilan, pengalaman kerja dan latar belakang pendidikan serta latihan yang berbeda pula. 

Sehingga biaya penyelesaian pekerjaan yang sama oleh para karyawan-karyawan yang berlainan juga berbeda. Matriks dibawah menunjukkan biaya penugasan karyawan untuk bermam-macam pekerjaan. Sebagai contoh A dapat menyelesaikan pekerjaan I pada biaya Rp. 15.00, pekerjaan II pada biaya Rp. 20.00 dan seterusnya.


*Catatan: nilai-nilai pada tabel tersebut dalam rupiah. 
Dari studi kasus diatas, maka langkah penyelesaiannya adalah: 

Langkah 1 

Langkah pertama adalah mengubah matriks biaya menjadi matriks opportynity cost. Ini dicapai dengan memilih elemen terkecil dari setiap baris dari matriks biaya mula-mula untuk mengurangi seluruh elemen (bilangan) dalam setiap baris.

Sebagai contoh , elemen terkecil baris A (=15) digunakan untuk mengurangi seluruh elemen pada baris A. Sehingga paling sedikit akan diperoleh suatu elemen bernilai nol sebagai hasilnya. Prosedur yang sama diulang untuk setiap baris untuk mendapatkan matriks biaya yang telah dikurangi (reduced-cost matrix)

Dengan langkah ini, maka diperoleh hasil:

Langkah 2 

Reduced cost-matrix di atas terus dikurangi untuk mendapatkan total opportunity cost matrix . Hal ini dapat dicapai dengan memilih elemen terkecil dari setiuap kolom pada reduced cost matrix untuk mengurangi seluruh elemen dalam kolom-kolom tersebut.

Pada contoh diatas 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 dihilangkannya. Berikut matriks total opportunity cost. 

tabel 2

Dalam contoh total opportunity cost matriks pada tabel diatas terdapat paling sedikit satu nilai nol, dalam setiap baris dan setiap kolom.

Langkah 3

Langkah berikutnya adalah mencari skedul penugasan dengan suatu total opportunity cost nol. Untuk mencapai penugasan ini dibutuhkan empat independent zeros dalam matriks. Ini berarti setiap karyawan harus ditugaskan hanya untuk satu pekerjaan dengan opportunity cost nol atau setiap pekerjaan harus diselesaikan hanya oleh satu karyawan.

Prosedur praktis untuk melakukan test optimalisasi adalah dengan menarik sejumlah minimum garuis horizontal dan/atau vertical untuk meliput seluruh elemen bernilai nol dalam total opportunity cost matrix. Bila jumlah garis sama dengan jumlah baris atau kolom penugasan optimal adalah feasible. Bila tidak sama matriks harus direvisi.

tabel 3

Dalam tabel di atas ada tiga baris yang meliputi seluruh nilai nol dibanding empat baris atau kolom, sehingga langkah berikutnya diperlukan untuk merevisi matriks. 

Langkah 4 

Untuk merevisi total opportunity cost matrix pilih elemen terkecil yang belum terliput garis-garis (yaitu opportunity cost terendah, atau pada contoh di atas = 1) untuk mengurangi seluruh elemen yang belum terliput.

Kemudian tambahkan dengan jumlah yang sama (nilai elemen terkecil) pada seluruh elemen-elemen yang mempunyai dua garis yang saling bersilangan (5 pada baris C dan 1 pada baris D), atau sama dengan 6 dan 2 . Masukkan hasil-hasil ini pada matriks, dan menyelesaikan matriks dengan seluruh elemen-elemen yang telah terliput tanpa perubahan, ulangi langkah 3. Berikut dibawah ini matriks yang telah direvisikan.

tabel 4

Dalam tabel diatas dibutuhkan empat garis untuk meliput seluruh nilai nol atau sama dengan jumlah baris atau kolom, sehingga matriks penugasan optimal telah tercapai. Karyawan B ditugaskan untuk pekerjaan I karena baris B hanya mempunyai satu nilai nol pada kolom I.

Kolom II berisi satu nol pada baris C, jadi karyawan C ditugaskan untk pekerjaan II. Kemudian karyawan A ditugaskan untuk pekerjaan III, karena pekerjaan I telah ditugaskan karyawan B. Karyawan D ditugaskan untuk pekerjaan terakhir IV. Skedul penugasan optimal dengan biaya adalah sebagai berikut:

tabel 5

Sehingga, dapat ditarik kesimpulan:
Karyawan A ditugaskan mengerjakan pekerjaan III dengan biaya Rp 18,00
Karyawan B ditugaskan mengerjakan pekerjaan I dengan biaya Rp 14,00
Karyawan C ditugaskan mengerjakan pekerjaan II dengan biaya Rp 20,00
Karyawan D ditugaskan mengerjakan pekerjaan IVdengan biaya Rp 16,00
--------------------------------------------------------------------------------------------------- (+)
Total biaya = Rp.68,00

Jumlah Pekerjaan Tidak Sama Dengan Jumlah Karyawan 

Untuk memenuhi persyaratan suatu matriks segi empat bujur sangkar, agar metode hungarian dapat diterapkan, bila terdapat jumlah pekerjaan lebih besar dari jumlah karyawan, maka harus ditambahkan suatu karyawan semu (dummy worker).

Biaya semu adalah sama dengan nol, karena tidak akan terjadi biaya bila suatu pekerjaan ditugaskan ke karyawan semu. Atau dengan kata lainkarena sebenarnya pekerjaan tersebut tidak dilaksanakan. Sebaliknya bila jumlah karyawan lebih besar dari jumlah pekerjaan, maka harus ditambahkan suatu pekerjaan semu (dummy job). Sebagai contoh, bila jumlah pekerjaan lebih besar dari jumlah karyawan, dapat dilihat pada tabel dibawah ini.


*Catatan: nilai-nilai pada tabel tersebut dalam rupiah 
Prosedur penyelesaian selanjutnya sama dengan langkah-langkah di atas. 

2.4 Masalah Maksimisasi (untuk kasus normal) 


Metode penugasan hungarian untuk minimasi juga dapat diterapkan untuk masalah penugasan yang menyangkut maksimisasi. Dalam masalah maksimisasi, matriks elemen-elemen menunjukkan tingkat keuntungan (atau indeks produktivitas). Efektivias pelaksanaan tugas oleh karyawan-karyawan individual diukur dengan jumlah kontribusi keuntungan. Matriks dibawah ini menunjukkan bahwa karyawan A mempunyai keterampilan yang dibutuhkan untuk mengenai 5 (lima) pekerjaan-pekerjaan yang berlainan.


tabel1


*Catatan: nilai-nilai pada tabel tersebut dalam rupiah.

Dari studi kasus diatas, maka langkah penyelesaiannya adalah:

Langkah 1

Langkah pertama dalam masalah maksimisasi adalah mengubah matriks keuntungan menjadi suatu matriks opportunity-loss. Dalam masalah ini A menyumbang keuntungan tertinggi Rp. 15,00 bila dia ditugaskan pada pekerjaan V. Oleh karena itu, bila A ditugaskan pada pekerjaan I (yang kontribusinya keuntungannya = Rp. 10,00), ada sebesar Rp. 5,00 sebagai opportunity-loss yang terjadi dengan penugasan ini, dan seterusnya. Seluruh elemen dalam setiap baris dikurangi dengan nilai maksimum dalam baris yang sama. Prosedur ini menghasilkan matriks opportunity-lossyang ditunjukkan dalam tabel dibawah ini. Matriks ini sebenarnya bernilai negatif.

tabel2


Seperti sebelumnya, setiap baris akan berisi nilai nol. Langlah berikutnya dengan meminimumkan opportunity-loss akan memaksimumkan kontibusi keuntungan total. Matriks total- opportunity-loss yang ditunjukkan dalam tabel dibawah ini yang didapatkan melalui pengurangan seluruh elemen dalam setiap kolom dengan elemen terkecil dari kolom tersebut.

tabel3

Dalam tabel diatas seluruh elemen bernilai nol dapat diliput hanya dengan empat garis. Jadi, matriks harus dikurangi seperti yang sudah dijelaskan dimuka. Matriks baru ditunjukkan oleh tabel dibawah ini dimana penugasan optimal dapat ditentukan.

tabel4

* Tabel optimal
Skedul penugasan optimal dan keuntungan total untuk dua alternatif penyelesaian adalah:


tabel5


BAB III 

PENUTUP 

3.1 Kesimpulan 

Dalam prakteknya (kehidupan sehari-hari), tidak semua masalah penugasan memiliki matrik biaya atau keuntungan seperti dalam contoh kasus di atas. Ada kalanya seorang karyawan tidak bisa dialokasikan atau ditugaskan untuk sebuah pekerjaan tertentu (karena faktor usia, jenis kelamin, skill, fisik dll.).

Dengan demikian karyawan dengan keterbatasan seperti itu tidak dapat dipaksakan mengerjakan sebuah pekerjaan yang memang tidak mungkin baginya. Untuk mengatasi hal semacam itu, maka dalam proses penyelesaiannnya perlu ditambahkan sebuah bilangan yang sangat besar, dan disebut dengan bilangan M (untuk masalah minimalisasi) dan -M (untuk masalah maksimalisasi).

Proses penyelesaian selanjutnya dapat dilakukan dengan cara yang sama seperti pada kasus penugasan yang normal, hanya saja pada keputusan optimalnya akan dihindari menugaskan karyawan pada tugas yang memiliki bilangan M atau -M tersebut. 

3.2 Saran 

Diharapkan agar semua perusahaan menerapkan model penugasan dengan metode hungarian agar pekerjaan karyawan lebih dapat dperkirakan sesuai dengan job/pekerjaan yang memang seharusnya karyawan kerjakan dan agar pekerjaan yang dilakukan terlihat lebih efektif dan efisien.

0 Response to "MODEL PENUGASAN MENGGUNAKAN METODE HUNGARIAN"

Post a Comment

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel