A. Definisi Metode Penugasan
Metode Penugasan
Manajemen produksi sering menghadapi masalah masalah yang berhubungan dengan alokasi optimal dari berbagai sumber daya yang produktif, terutama tenaga kerja atau personalia, yang mempunyai tingkat efisiensi berbeda-beda untuk pekerjaan yang berbeda pula. Masalah ini disebut Masalah Penugasan (Assigment Problem), yang merupakan suatu kasus khusus dari masalah linear programming pada umumnya.
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).
Masalah penugasan adalah sejumlah tugas kepada sejumlah penerima tugas dalam basis satu-satu,
artinya seorang pekerja harus menjalankan satu pekerjaaan. Tujuan untuk memecahkan persoalan, penempatan sumber- sumber yang ada pada kegiatan kegiatan yang dituju, sehingga kerugiannya agak minimal dan keuntungannya maksimal.
Persoalan penugasan (Assigment problem) merupakan salah satu persoalan transportasi dan dapat dinyatakan sebagai berikut : “ Dengan tersedianya fasilitas untuk melaksanakan jenis pekerjaan (jobs) dimana masing-masing fasilitas (mesin, orang, dan tenaga), persoalannya ialah bagaiamana menentukan jenis pekerjaan yang mana, agar jumlah pengorbanan (uang, waktu dan tenaga) minimum ”. Persoalan penugasan luas penggunaannya dalam bidang manajemen khususnya keputusan untuk menentukan jenis pekerjaan apa yang harus di kerjakan.
Salah satu teknik pemecahan masalah-masalah penugasan yang tersedia adalah metoda Hungarian, yang mula-mula di kembangkan oleh seorang ahli matematika berkebangsaan Huangaria bernama D. Konig dalam tahun 1916.
Model-model penugasan bertujuan untuk mengalokasikan “sumber daya” untuk sejumlah sama “pekerjaan” pada biaya total minimum.Penugasan di buat atas dasar bahwa setiap sumber daya harus di tugaskan hanya untuk satu pekerjaan. Untuk suatu masalah penugasan n x n, jumlah penugasan yang mungkin di lakukan sama dengan n ! (n factorial) karena perpasangan satu-satu.
B. Algoritma Metode Penugasan
- Identifikasi dan penyerderhanaan masalah dibuat dalam bentuk table penugasan.
- a. Minimalkan, Untuk kasus minimalisasi, maka perlu mencari nilai terkecil disetiap baris, kemudian mengunakan nilai terkecil tersebut untuk mengurangi semua nilai yang ada pada baris yang sama. b. Maksimalkan, Untuk kasus maksimalisasi, maka perlu mencari nilai tertinggi setiap baris, kemudian nilai tertinggi tersebut dikurangi dengan nilai-nilai yang ada pada baris yang sama
- Memastikan semua baris dan kolom sudah memiliki nilai nol. Apabila masih ada baris atau kolom yang belum memiliki nilai nol, maka dicari terkecil pada baris atau kolom tersebut untuk kemudian digunakan untuk mengurangi semua nilai yang ada pada baris atau kolom tersebut.
- Memastikan tidak terjadi bentrok pada nilai nol. Dengan kata lain, apakah nilai nol (yang mewakili penugasan) mengalami bentrok atau rebutan bagi sumber daya lain? Jika iya, maka masih perlu dioptimalkan.
Setelah semua baris dan kolom memiliki nilai nol, maka langkah selanjutnya adalah memastikan atau mengecek apakah dalam table penugasan tersebut telah berhasil ditemukan nilai nol sebanyak sumber daya (bias karyawan, mesin, alat transportasi, dll) yang juga tercermin dengan jumlah barisnya. Misalnya jika yang akan ditugaskan adalah 4 karyawan, maka harus ditemukan nilai nol sebanyak 4 buah yang terletak di baris dan kolom yang berada. Sebaliknya 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 table penugasan tersebut.
6. Mengurangi nilai di luar garis dan menambah nilai di dalam garis. Selanjutnya, perhatikan nilai-nilai yang belum terkena garis. Pilih nilai yang paling kecil, kemudian pergunakan untuk mengurangi nilai-nilai yang belum terkena garis, dan gunakan untuk menambahkan nilai-nilai yang terkena garis danda (dua kali)
7. Sudah optimal? Dari hasil langkah ke 6 tersebut, apakah sudah didapatkan nilai nol sejulah 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
Post a Comment