Penyelesaian Matching Graf Dengan Menggunakan Metode Hungarian dan Penerapannya Pada Penempatan Karyawan di Suatu Perusahaan

Abstract

Semakin meningkatnya kompetisi global menuntut setiap perusahaan untuk meningkatkan kualitas serta efektifitas kinerja karyawannya yang pada akhirnya diharapkan dapat meningkatkan keuntungan. Penempatan sejumlah X karyawan pada Y pekerjaan dimana masing-masing karyawan mempunyai kompetensi untuk menyelesaikan semua pekerjaan dengan mempertimbangkan beberapa aspek seperti memaksimalkan keuntungan yang diperoleh atau meminimalkan waktu yang diperlukan sebagai akibat dari penempatan karyawan pada pekerjaan dikenal dengan Optimal Assignment Problem. Tujuan dari penulisan ini adalah untuk mencari solusi pada Optimal Assignment Problem dimana aspek yang akan dioptimalkan adalah keuntungan dari penempatan sejumlah karyawan pada pekerjaan yang dapat diperoleh dengan menerapkan konsep teori graf. Dalam hal ini permasalahan dinyatakan sebagai graf bipartit khususnya graf bipartit lengkap berbobot yang menerapkan konsep matching, yaitu pencarian matching sempurna dengan bobot paling optimal. Untuk mencari matching sempurna dengan bobot paling optimal maka dapat digunakan sebuah algoritma optimasi yaitu metode Hungarian. Dengan menggunakan metode Hungarian, diperoleh matching sempurna dengan bobot yang optimal pada graf bipartit lengkap berbobot. Matching dikatakan sempurna jika telah memenuhi semua himpunan simpul dan . Matching yang dihasilkan merupakan solusi dari Optimal Assignment Problem yakni memasangkan seorang karyawan tepat satu dengan sebuah pekerjaan dan bobotnya menyatakan keuntungan optimal yang akan diperoleh oleh suatu perusahaan.