Metode Hungaria

Assignment Method (metode/model penugasan) terjadi pada beberapa konteks manajemen. Pada umumnya adalah masalah untuk menentukan penugasan yang optimal (berbiaya total minimal) dari sejumlah orang/agen atau obyek pada sejumlah pekerjaan. Misalnya bagaimana menempatkan beberapa jenis pekerjaan pada beberapa stasiun kerja bila tiap-tiap jenis pekerjaan pada masing-masing stasiun kerja membutuhkan biaya yang berbeda-beda, atau misalnya bagaimana menempatkan sejumlah orang untuk bekerja pada beberapa kota jika masing-masing orang memerlukan tunjangan hidup yang berbeda-beda pada kota yang berlainan. Batasan yang paling penting adalah bahwa setiap agen/orang hanya dapat menempati satu jenis pekerjaan, sehingga biasanya jumlah agen/orang sama dengan jumlah pekerjaan yang tersedia, artinya setiap agen/orang akan menempati satu pekerjaan. Bisa jadi jumlah agen/orang kurang dari jumlah pekerjaan sehingga ada pekerjaan yang tidak dikerjakan oleh siapapun (dikerjakan oleh “agen bayangan” / dummy), atau jumlah agen/orang lebih dari jumlah pekerjaan, artinya akan ada agen/orang yang mengerjakan “pekerjaan bayangan” / dummy alias menganggur. Misalkan ada tiga orang pegawai dari suatu perusahaan yang masing-masing akan ditempatkan untuk menjadi kepala bagian pemasaran di satu kota tertentu. Ada empat kota yang membutuhkan kepala bagian pemasaran, dan masing-masing dari tiga orang yang tersedia, berdasarkan pertimbangan-pertimbangan tertentu menghendaki tunjangan jabatan yang berbeda-beda seandainya ditempatkan pada kota-kota tersebut. Penugasan ini mirip dengan kasus transportasi. Sebagaimana halnya metode transportasi, metode penugasan merupakan pemecahan masalah dengan linear programming yang lebih sederhana dibandingkan metode simpleks. Dalam masalah penugasan ada beberapa syarat lihat selanjutnya. yang harus dipenuhi yaitu : satu tugas diselesaikan oleh satu mesin serta biaya penyelesaian tugas untuk masing-masing mesin diketahui. Tujuan dari penugasan adalah minimalisasi total biaya. Pertimbangkan situasi dimana m pekerjaan (atau pekerja) ke n mesin. Pekerjaan i (i = 1, 2, 3,…m) ketika ditugaskan ke mesin j (j = 1, 2, 3, …n) memerlukan biaya Cij. Tujuannya adalah menugaskan pekerjaan-pekerjaan tersebut ke mesin-mesin (satu pekerja satu mesin) dengan biaya total terendah. Situasi ini dikenal sebagai masalah penugasan. Dengan kata lain, masalah penugasan menyangkut penempatan para pekerja pada bidang yang tersedia atau mesin agar biaya yang ditanggung dapat diminimumkan. Disini pekerjaan mewakili “sumber” dan mesin (bidang yang tersedia) mewakili “tujuan”. Penawaran yang tersedia disumber adalah 1 dan permintaan yang diperlukan oleh tujuan adalah 1. Biaya pekerjaan i ke mesin i adalah Cij. Struktur khusus dari model penugasan memungkinkan pengembangan sebuah teknik pemecahan yang efisien yang disebut metode hungaria. Langkah-langkah dalam Metode Hungaria ini adalah : 1. Langkah pertama mencari solusi pola penugasan adalah menyusun total Opportunity cost table, caranya kurangi elemen pada setiap baris dengan elemen terkecil pada baris yang bersangkutan. Penugasan dapat ditempatkan pada sel yang bernilai nol. Solusi optimum dicapai jika setiap pekerjaan dapat ditugaskan pada setiap mesin dan setiap mesin dikerjakan oleh satu pekerja. Untuk mengetahui apakah opportunity cost table sudah optimum dapat diperiksa melalui cara berikut: tutup semua angka nol dengan menarik garis datar atau tegak dengan jumlah garis paling efisien. Jika jumlah garis itu lebih kecil dari jumlah baris atau kolom, berarti penugasan optimum belum dapat ditemukan. 2. Langkah selanjutnya kurangkan semua angka yang tidak tertutup garis dengan angka terkecil yang tidak tertutup. Tambahkan angka terkecil tersebut pada angka yang menempati posisi silang.Jumlah garis minimum yang diperlukan adalah 3, sehingga penugasan optimum sudah dapat dibuat Masalah penetapan (assignment problem) adalah suatu masalah mengenai pengaturan pada individu (objek) untuk melaksanakan tugas (kegiatan), sehingga dengan demikian biaya yang dikeluarkan untuk pelaksanaan tugas tersebut dapat diminimalkan (N. Soemartojo, 1994 : 309). Masalah ini merupakan salah satu kasus khusus dari masalah transportasi yang penyelesaiannya menggunakan metode Hongaria. Metode Hongaria dikembangkan atas dasar pendekatan VAM (Vogel’s Approximation Method), yaitu dengan cara meminimalkan biaya penalti (opportunity cost) yang tidak memanfaatkan biaya sel termurah. Pendekatan VAM merupakan suatu metode yang menggunakan pendekatan dengan cara meminimalkan biaya penalti akibat gagal memilih pengisian sel yang memiliki alternatif terbaik. Howard Anton (1988 : 59) menyatakan bahwa masalah penetapan tugas mensyaratkan bahwa fasilitas sama banyaknya dengan tugas, katakanlah sama dengan n. Dalam hal ini maka ada n! cara yang berlainan untuk menetapkan tugas kepada fasilitas berdasarkan penetapan satu-satu (one-toone basic). Banyaknya penetapan ini adalah n! karena terdapat n cara untuk menetapkan tugas pertama, n-1 cara untuk menetapkan tugas kedua, n-2 cara untuk menetapkan tugas ketiga, dan seterusnya yang jumlah seluruhnya adalah: n.(n-1).(n-2)…3.2.1 = n! penetapan yang mungkin. Diantara ke n! penetapan-penetapan yang mungkin ini kita harus mencari satu penetapan yang optimal. Hardi Suyitno (1997: 218) menyatakan bahwa langkah-langkah dalam menjalankan metode Hongaria adalah sebagai berikut: 1. Menyusun matriks biaya. 2. Mengurangkan elemen-elemen pada setiap baris dengan elemen terkecil pada baris yang sama. 3. Mengurangkan elemen-elemen pada setiap kolom dengan elemen terkecil pada kolom yang sama. Langkah ini akan menghasilkan biaya opportunity keseluruhan Total Opportunity Cost (TOC). 4. Tutup elemen-elemen bernilai nol pada TOC dengan garis-garis mendatar atau tegak. Misalkan n adalah banyaknya baris atau kolom dan banyaknya garis penutup elemen nol sekurang-kurangnya k, maka: Jika k = n, berarti sudah diperoleh program optimal. Proses dihentikan dan susun penugasan. Jika k < n, maka proses dilanjutkan dengan mengikuti langkah 5. 5. Cari bilangan terkecil dari bilangan-bilangan yang tak tertutup garis, misalkan e. 6. Selanjutnya semua elemen yang tak tertutup garis dikurangi e. 7. Semua elemen yang tertutup oleh satu garis tidak diubah. 8. Semua elemen yang tertutup oleh dua garis ditambah dengan e. 9. Setelah diperoleh tabel baru kembali ke langkah ke-4. Pada umumnya masalah penetapan memiliki karakteristik atau kriteria bahwa cacah baris sama dengan cacah kolom pada tabel penetapan (m = n), karena masalah penetapan mensyaratkan bahwa banyaknya fasilitas sama dengan banyaknya tugas. Penetapan pekerjaan dilakukan dengan tujuan agar penyelesaian semua pekerjaan minimum atau maksimumkan profit dari pekerjaan-pekerjaan tersebut. Telah diketahui bahwa matriks penetapan harus berbentuk bujur sangkar yaitu cacah pekerja sama dengan cacah pekerjaannya. Adapun untuk menyelesaikan masalah tersebut adalah dengan menggunakan langkahlangkah atau prosedur Metode Hongaria. Untuk memudahkan pemahaman penyelesaian masalah penetapan untuk kasus m = n, akan dibahas beberapa contoh kasus sebagai berikut. Contoh 1: Suatu perusahaan otomotif telah menandatangani kontrak untuk memodifikasi tiga jenis sepeda motor yang akan dijadikan sebagai contoh modifikasi dalam pameran otomotif tiga bulan mendatang dan telah menerima bayaran di muka untuk melakukan pekerjaan itu. Perusahaan menginginkan penyelesaian ketiga jenis sepeda motor ini secepat mungkin sehingga dapat mengerjakan pekerjaan yang lain untuk memperoleh keuntungan yang lebih besar. Contoh 2: Sebuah perusahaan ban ‘Blackstone’ mempunyai empat tempat produksi ban yang berlainan lokasinya. Perusahaan tersebut harus mengirimkan satu kontainer ban untuk masing-masing tempat produksi keempat tempat pemasaran yang berlainan sehingga terjadi pemerataan pemasaran untuk masing-masing tempat produksi. METODE HONGARIA UNTUK KASUS-KASUS KHUSUS Selain kasus m = n dalam masalah penetapan juga terdapat beberapa kasus-kasus khusus. Masalah penetapan untuk kasus-kasus khusus ini terdiri dari tiga macam kasus, yaitu: masalah memaksimalkan penetapan, masalah cacah baris dan cacah kolom yang tidak sama (m ≠ n), dan masalah penetapan yang diblokir. Adapun keterangan-keterangan selanjutnya akan diuraikan sebagai berikut: 1. Masalah Memaksimalkan Penetapan Metode Hongaria untuk masalah penetapan dapat juga diaplikasikan kedalam suatu masalah penetapan yang fungsi tujuannya memaksimalkan laba atau sejenisnya. Algoritma penetapan yang diterangkan di bagian depan hanya digunakan untuk masalah minimum, karena dalam masalah penetapan masalahnya haruslah merupakan masalah minimasi. Untuk masalah pemaksimuman cacah entri dari sebuah matriks biaya akan mudah diubah menjadi masalah meminimumkan cacah tersebut dengan mengalikan setiap entri dari matriks biaya dengan -1. Prosedur lainnya, sehingga mencapai penyelesaian optimal adalah sama seperti masalah meminimalkan penetapan. Karakteristik dari masalah memaksimalkan penetapan yang lainnya adalah bahwa nilai penyelesaian optimal merupakan nilai terbesar (hasil evaluasi kelayakan), sedangkan dalam masalah meminimalkan penetapan adalah nilai terkecilnya. 2. Masalah Cacah Baris dan Cacah Kolom yang Tidak Sama (m ≠ n) Pada umumnya, masalah penetapan mempunyai karakteristik atau kriteria bahwa cacah baris harus sama dengan cacah kolom pada tabel masalah penetapan (m = n). Meskipun hal ini jarang terjadi, penyelesaian masalah cacah baris yang tidak sama dengan cacah kolom dapat diatasi dengan cara menambahkan baris atau kolom dummy (baris atau kolom semu) kedalam baris atau kolom penetapan. Apabila cacah baris (m) lebih kecil daripada cacah kolom (n), maka ditambahkan baris dummy dalam tabel penetapan sehingga diperoleh m = n. Demikian juga terhadap masalah dimana m > n, maka ditambahkan kolom dummy dalam tabel penetapan. Biaya setiap sel pada dummy diasumsikan sama dengan nol. Dengan demikian masalah ini dapat diselesaikan dengan prosedur seperti sebelumnya. 3. Masalah Penetapan yang Diblokir Masalah penetapan yang diblokir biasanya timbul akibat pengiriman barang ketempat tujuan akhir tidak dapat dilakukan karena ada kerusakan jalan/jembatan, larangan masuk ketempat tujuan, banjir, longsor, pemogokan buruh, atau lain sebagainya. Untuk mengatasi masalah ini, diasumsikan bahwa biaya angkutan ketempat tujuan tersebut sangat besar (misal milyar rupiah), yang selanjutnya diberi notasi misalkan M. Dengan demikian sel yang memiliki nilai M tidak perlu dievaluasi lebih lanjut karena biayanya sangat tinggi. Atau dengan kata lain, sel tersebut diblokir dan tidak dipertimbangkan dalam proses penyelesaian selanjutnya. Dari tiga contoh kasus di atas, dapat diketahui bahwa langkah-langkah penyelesaian masalah penetapan untuk kasus-kasus khusus hampir sama dengan langkah-langkah penyelesaian masalah penetapan pada kasus m = n. Hanya saja penyelesaian pada masalah penetapan untuk kasus-kasus khusus ini sedikit berbeda. Pada kasus memaksimalkan penetapan, agar penyelesaian masalah dapat menjadi penyelesaian masalah penetapan pada umumnya maka masalah pemaksimuman diubah dahulu menjadi masalah peminimuman. Masalah pemaksimuman cacah entri dari sebuah matriks biaya akan mudah diubah menjadi masalah peminimuman cacah entri tersebut yaitu dengan mengalikan setiap entri dari matriks biaya dengan -1. Langkah yang lain sehingga mencapai penyelesaian optimal adalah sama seperti masalah meminimalkan penetapan. Nilai penyelesaian optimal masalah memaksimalkan penetapan merupakan nilai terbesar (hasil evaluasi kelayakan), sedangkan dalam masalah meminimalkan penetapan adalah nilai terkecilnya. Pada kasus cacah baris dan cacah kolom yang tidak sama, agar masalah dapat diselesaikan dengan metode Hongaria maka cacah baris dan cacah kolom harus disamakan terlebih dahulu dengan cara menambahkan dummy kedalam baris atau kolom penetapan. Apabila cacah baris (m) lebih kecil daripada cacah kolom (n), maka harus ditambahkan baris dummy (baris semu) dalam tabel penetapan (matriks biaya). Demikian juga apabila cacah baris lebih besar daripada cacah kolom, maka harus ditambahkan kolom dummy (kolom semu) dalam tabel penetapan sehingga akan diperoleh m = n. Nilai untuk setiap sel pada dummy diasumsikan sama dengan nol, karena tidak ada nilai yang timbul oleh suatu alokasi semu. Setelah cacah baris sama dengan cacah kolom, maka prosedur penyelesaian selanjutnya adalah sama seperti penyelesaian pada kasus m = n sehingga diperoleh penyelesaian yang optimal. Sedangkan pada kasus penetapan yang diblokir, agar masalah dapat diselesaikan dengan metode Hongaria maka nilai untuk sel yang diblokir diasumsikan bahwa nilai atau biayanya sangatlah besar sehingga tidak perlu di evaluasi lebih lanjut karena biayanya yang sangat tinggi itu. Atau dengan kata lain sel yang diblokir itu tidak dipertimbangkan dalam proses penyelesaian selanjutnya. Jadi prosedur penyelesaiannya sama seperti pada kasus m = n, hanya saja dalam penyelesaian kasus penetapan yang diblokir tidak memperhatikan atau tidak mempertimbangkan sel yang diblokir.

Advertisement