Buletin Ilmiah Mat. Stat. danTerapannya (Bimaster) Volume 04, No. 3 (2015), hal 363 - 370
OPTIMALISASI MASALAH PENUGASAN MENGGUNAKAN METODE HUNGARIAN (Studi kasus pada PT Pos Indonesia (Persero) Pontianak) Erlinda Rahmawati, Neva Satyahadewi, Fransiskus Frans INTISARI Salah satu bagian dari program linear yang dapat dijumpai dalam kehidupan sekitar adalah masalah penugasan (assignment problem). Masalah umum penugasan meliputi n tugas yang harus ditetapkan kepada m pekerja dimana setiap pekerja memiliki kompetensi yang berbeda dalam menyelesaikan setiap tugas. Salah satu metode dalam menyelesaikan persoalan ini adalah metode Hungarian. Untuk dapat menerapkan metode Hungarian, matriks biaya berbentuk persegi (Jumlah sumber-sumber yang ditugaskan harus sama dengan jumlah tugas yang akan diselesaikan ). Tujuan dari penelitian ini adalah menganalisis penerapan metode Hungarian dalam menentukan waktu optimal pengantaran barang pada PT Pos Indonesia (Persero) Pontianak. Langkah pertama dalam menyelesaikan masalah penugasan yaitu dengan mengambil data yang meliputi nama karyawan, alamat tujuan, dan waktu perjalanan karyawan dalam mengantar barang. Selanjutnya adalah membentuk model matematika dari masalah penugasan ke dalam program linear dan diselesaikan dengan metode Hungarian. Berdasarkan hasil penelitian, menunjukkan bahwa optimalisasi perhitungan menggunakan metode Hungarian diperoleh total waktu optimal yaitu 93 menit, dibandingkan dengan hasil yang diperoleh sebelum menggunakan metode Hungarian yaitu 98 menit. Dalam hal ini terjadi efisiensi waktu sebanyak 5 menit apabila perusahaan melakukan penempatan karyawan dalam pengantaran barang pada PT Pos Indonesia (Persero) yaitu Rimba ditugaskan ke Tanjung Pura, Wahyu ditugaskan ke Sei Raya Dalam, Hendra ditugaskan ke Gajah Mada, Agus ditugaskan ke Jeruju, Riki ditugaskan ke Ayani, Oki ditugaskan ke Sungai Jawi, dan terakhir Lukman ditugaskan ke Imam Bonjol. Kata Kunci: Matriks Biaya, Harold Kuhn, Program Linear.
PENDAHULUAN Pemrograman linear (linear programming) merupakan bagian dari matematika terapan yang dapat dijadikan pertimbangan untuk pengambilan keputusan. Program linear merupakan suatu model yang dapat digunakan untuk pemecahan masalah pengalokasian sumber-sumber yang terbatas secara optimal [1]. Salah satu bagian dari program linear yang dapat dijumpai dalam kehidupan sekitar adalah masalah penugasan (assignment problem). Masalah umum penugasan meliputi n tugas yang harus ditetapkan kepada m pekerja, dimana setiap pekerja memiliki kompetensi yang berbeda dalam menyelesaikan setiap tugas. Tujuan dari masalah penugasan adalah untuk menetapkan setiap tugas yang sesuai pada pekerja sehingga total pengeluaran sumber daya untuk menyelesaikan semua tugas dapat dioptimalkan. Pada penelitian ini diterapkan pada kasus penugasan karyawan dalam mengantar barang ke lokasi tujuan pada PT Pos Indonesia (Persero). PT Pos Indonesia merupakan sebuah Badan Usaha Milik Negara (BUMN) Indonesia yang bergerak dibidang layanan jasa pengiriman barang dan surat menyurat. Saat ini, bentuk badan usaha pos Indonesia merupakan perseroan terbatas dan sering disebut PT Pos Indonesia (Persero). Sebagai penyedia jasa pengantaran barang ataupun surat yang akan dikirim pelanggan untuk dikirim ke tujuannya melalui kantor Pos, PT Pos Indonesia menerapkan beberapa sistem pengiriman barang agar dalam pengirimannya dapat tepat sesuai dengan tujuan kirim. Oleh karena itu, untuk mengoptimalkan total waktu dalam pengantaran barang akan digunakan metode Hungarian. Metode Hungarian adalah metode yang digunakan untuk menyelesaikan masalah penugasan (assignment problem) yang ditemukan dan dipublikasikan oleh Harold Kuhn pada tahun 1955. Untuk dapat menerapkan metode Hungarian, matriks biayanya berbentuk persegi (jumlah sumber-sumber
363
364
E. RAHMAWATI, N.SATYAHADEWI, F. FRANS
yang ditugaskan harus sama dengan jumlah tugas yang akan diselesaikan) dan entri-entri pada matriks biaya merupakan bilangan bulat. Tujuan penelitian ini adalah menganalisis penerapan metode Hungarian dalam menentukan waktu optimal pengantaran barang pada PT Pos Indonesia (Persero) Pontianak. Langkah pertama dalam menyelesaikan masalah penugasan yaitu dengan mengambil data yang meliputi nama karyawan, alamat tujuan, dan waktu perjalanan karyawan dalam mengantar barang. Selanjutnya adalah membentuk model matematika dari masalah penugasan ke dalam program linear dan diselesaikan dengan metode Hungarian. MASALAH PENUGASAN Masalah penugasan adalah masalah yang hanya mempunyai satu tujuan optimasi, yaitu memaksimalkan atau meminimalkan suatu sumber daya (pendapatan, biaya, jarak atau waktu) yang digunakan untuk menyelesaikan tugas. Masalah penugasan merupakan kasus khusus pemrograman linear yang mengalokasikan sumber-sumber kepada kegiatan-kegiatan atas dasar satu-satu (one to one basic). Jadi setiap sumber (karyawan, mesin) ditugasi secara khusus kepada suatu kegiatan (pekerjaan, lokasi atau kejadian). Akibatnya akan ada suatu biaya yang berkaitan dengan petugas yang melakukan tugas . Dengan demikian tujuan masalah penugasan adalah untuk menetapkan setiap tugas yang sesuai pada pekerja sehingga total pengeluaran sumber daya untuk menyelesaikan semua tugas dapat dioptimalkan [2]. Masalah penugasan mensyaratkan terdapat sumber-sumber yang sama banyaknya dengan tugastugas yang harus selesaikan, misalnya masing-masing sebanyak n. Dalam hal ini, terdapat tepat n! cara yang berbeda untuk menetapkan tugas-tugas pada sumber-sumber dengan korespondensi satu-satu. Hal ini disebabkan terdapat n cara untuk menetapkan tugas pertama, cara untuk menetapkan tugas kedua, cara untuk menetapkan tugas ketiga, dan seterusnya sehingga keseluruhan terdapat penugasan yang mungkin. Diantara n! kemungkinan penugasan, ditentukan suatu penugasan yang optimal. Untuk mendefinisikan rumusan tentang penugasan optimal secara tepat, diperkenalkan sejumlah istilah berikut. Misalkan menyatakan biaya untuk menetapkan tugas ke-j pada sumber kei ( i, j = 1, 2, . . ., n). Satuan untuk bisa berupa rupiah, km, jam atau apapun yang sesuai dengan masalah yang dihadapi. Didefinisikan matriks biaya (cost matrix) sebagai matriks n × n:
[ ] Berdasarkan matriks C, terdapat persyaratan bahwa tiap sumber dikenai oleh sebuah tugas atas dasar korespondensi satu ke satu adalah ekuivalen dengan syarat bahwa tidak ada dua yang berasal dari baris atau kolom yang sama. Hal ini mengarah pada definisi berikut ini [3]. Definisi 1 [3] Jika C adalah suatu matriks biaya n × n, maka penugasan adalah himpunan dari n posisi-posisi entri, dengan syarat tidak terdapat dua entri yang terletak di dalam baris atau kolom yang sama. Berdasarkan Definisi 1 suatu penugasan yang optimal dapat didefinisikan berikut ini: Definisi 2 [3] Jumlah n entri dari sebuah penugasan disebut biaya penugasan tersebut. Penugasan dengan biaya terkecil yang mungkin disebut penugasan optimal (optimal assignment). Suatu masalah umum penugasan yang hanya berkaitan dengan biaya operasi dapat direpresentasikan pada Tabel 1. Ada n yang ditugaskan untuk m pekerja, sedangkan adalah biaya operasi pekerja i untuk melaksanakan tugas j.
Optimalisasi Masalah Penugasan Menggunakan Metode Hungarian....
365
Tabel 1 Matriks Penugasan Tujuan 1 1 2
m Kapasitas
2
c11 x11
3
c12
c1n
x12
x1n
c21 x21
c22
c2n
x22
x2n
cm1 xm1
cm 2
cmn
xm 2 1
Kapasitas
4
xmn 1
1 1
1
1
Dengan:
Dalam hal ini berlaku: 1. + +...+ = 1 untuk i = 1, 2 ..., m. Ini artinya pada tiap sumber i hanya ada satu bernilai 1 sedangkan yang lainnya bernilai 0. 2. + +...+ = 1 untuk j = 1, 2 ..., n. Ini artinya pada tiap tujuan j hanya ada satu bernilai 1 sedangkan yang lainnya bernilai 0. 3. Nilai total dari sumber ke tujuan sangat bergantung pada nilai dan , namun karena bernilai 1 atau 0 maka nilai total tersebut sangat dipengaruhi oleh . Secara matematika, model untuk masalah penugasan dapat ditulis dalam bentuk program sebagai berikut [4]: n
Optimumkan
yang yang hanya linear
n
Z c ij x ij
(1)
i 1 j 1
dengan batasan n
x
ij
x
ij
i 1 n
j 1
1; j 1,2, n 1; i 1,2, n
Keterangan: Z : fungsi tujuan yang dicari nilai optimalnya (maksimal atau minimal). n : jumlah tugas yang akan diselesaikan. : Penugasan dari sumber (pekerja) ke tujuan (tugas) . : Parameter alokasi dari sumber ke tujuan . METODE HUNGARIAN Metode Hungarian ditemukan oleh Harold Kuhn pada tahun 1955 dan kemudian diperbaiki oleh James Munkres pada tahun 1957. Oleh karena itu metode Hungarian biasa disebut juga metode KuhnMunkres. Untuk dapat menerapkan Metode Hungarian, jumlah sumber-sumber yang ditugaskan harus sama dengan jumlah tujuan yang akan diselesaikan. Selain itu, masing-masing sumber harus
366
E. RAHMAWATI, N.SATYAHADEWI, F. FRANS
ditugaskan hanya untuk satu tujuan. Jadi, masalah penugasan akan mencakup sejumlah n sumber yang mempunyai n tujuan [3]. Teorema 3 [3] Jika sebuah bilangan ditambahkan pada atau dikurangkan pada seluruh entri dari sebuah baris atau kolom dalam sebuah matriks biaya, maka penugasan optimal untuk matriks biaya yang dihasilkan adalah juga penugasan optimal untuk matriks biaya semula. Bukti: Diberikan matriks biaya:
[ ] Pada matriks A, menyatakan biaya dari sumber ke tujuan . Selanjutnya untuk (tambahkan) setiap entri pada baris ke dari matriks A dengan
, kurangkan didapat:
. [
]
Didapat bahwa biaya penugasan pada matriks baru adalah tepat dengan biaya penugasan terkait pada matriks semula.
(
lebih sedikit dibandingkan
)
[ ] Terlihat bahwa entri yang telah dikurangkan dengan k terkait dengan matriks biaya semula, sehingga penugasan optimal untuk matriks biaya yang dihasilkan adalah juga penugasan optimal untuk biaya semula. Metode Hungarian merupakan prosedur lima langkah dengan menerapkan Teorema 3 pada sebuah matriks biaya tertentu. Hasilnya adalah matriks biaya dengan entri-entri tak negatif yang mengandung sebuah penugasan yang seluruhnya terdiri dari entri-entri nol. Langkah-langkah metode Hungarian: 1. Kurangkan setiap entri pada masing-masing baris dengan entri terkecil pada baris tersebut. 2. Kurangkan setiap entri pada masing-masing kolom dengan entri terkecil pada kolom tersebut. 3. Tarik garis-garis yang melalui baris dan kolom yang sesuai sehingga seluruh entri-entri nol dari matriks biaya dapat tertutup dan jumlah garis-garis yang digunakan adalah minimum. 4. Uji Optimalitas: a. Jika jumlah minimum dari garis-garis penutup adalah n, maka penugasan optimal dari bilanganbilangan nol mungkin tercapai dan metode Hungarian telah selesai. b. Jika jumlah minimum dari garis-garis penutup kurang dari n, maka penugasan optimal dari bilangan-bilangan nol belum memungkinkan. Lanjutkan kelangkah 5. 5. Tentukan entri terkecil yang tidak tertutup oleh garis manapun. Kurangkan entri ini pada seluruh entri yang tak tertutup dan kemudian tambahkan entri tersebut ke seluruh entri yang tertutup dua kali oleh garis horizontal dan garis vertikal. Kembali ke langkah 3.
Optimalisasi Masalah Penugasan Menggunakan Metode Hungarian....
367
STUDI KASUS Pada PT Pos Indonesia, masalah penugasan yang dialami adalah bagaimana menempatkan karyawan pengantaran barang pada lokasi yang seharusnya, sehingga mendapatkan hasil yang optimal. Jumlah karyawan yang siap untuk ditugaskan sebanyak 7 orang serta lokasi yang harus dituju sebanyak 7 lokasi. Dari masing-masing karyawan memiliki waktu dalam pengantaran barang yang berbeda, sehingga membutuhkan perhitungan untuk menugaskan karyawan pengantaran barang. Untuk mendapatkan hasil optimal dari penugasan karyawan pada PT Pos Indonesia dapat menggunakan metode Hungarian. Data yang digunakan yaitu waktu perjalanan masing-masing karyawan dalam pengantaran barang dari PT Pos Indonesia menuju lokasi. Pada hari kerja efektif (Senin-Jumat) dengan mengasumsikan setiap karyawan menggunakan mobil box yang sama sebagai alat transportasi serta kondisi lalu lintas yang sama. Dalam kasus ini, peneliti ingin meminimumkan nilai total waktu optimal dalam pengantaran barang agar penugasan karyawan dapat bekerja secara efektif dan efisien. Berikut adalah data waktu (dalam menit) perjalanan untuk masing-masing karyawan dalam pengantaran barang. Tabel 2 Hasil Waktu Pengantaran Barang (dalam menit) Sumber Tujuan Tanjung Pura
Rimba
Wahyu
Hendra
Agus
Riki
Oki
Lukman
15
20
11
15
20
30
40
Gajah Mada
30
30
15
20
25
30
20
Ayani Sei.Raya Dalam Imam Bonjol
20
11
40
20
11
11
15
15
15
20
30
30
11
15
40
30
30
15
15
30
11
Sei.Jawi
20
20
30
20
40
15
20
Jeruju
25
25
15
11
15
20
15
Berikut adalah hasil dari perhitungan penugasan sebelum menggunakan metode Hungarian, dengan cara melihat waktu minimum dari masing-masing karyawan: Tabel 3 Hasil Total Waktu sebelum menggunakan metode Hungarian Pekerja Lokasi Tujuan Sei Raya Dalam Rimba Ayani Wahyu Tanjung Pura Hendra Jeruju Agus Imam Bonjol Riki Sungai Jawi Oki Gajah Mada Lukman Total waktu optimal
Waktu (menit) 15 11 11 11 15 15 20 98
Berdasarkan Tabel 2, untuk menyelesaikan optimalisasi masalah penugasan pada PT Pos Indonesia, masalah diformulasikan ke dalam pemrograman linear terlebih dahulu. a. Membentuk Model Matematika Proses penyelesaian masalah penugasan ini hanya mempertimbangkan waktu operasi yaitu bagaimana menetapkan tugas agar total waktu pengantaran barang dapat minimum. Berdasarkan Tabel 2 diperoleh persamaan sebagai berikut: 7
7
Minimumkan T t ij x ij i 1 j 1
(2)
368
E. RAHMAWATI, N.SATYAHADEWI, F. FRANS
Dengan T menyatakan total waktu pengantaran barang dan adalah waktu yang diperlukan oleh karyawan untuk menyelesaikan pengantaran barang ke lokasi . Berdasarkan Persamaan 2 dapat diformulasikan kedalam pemrograman linear sebagai berikut:
Fungsi kendala: Kendala karyawan,
Kendala lokasi,
b. Proses Optimalisasi Masalah Penugasan Menggunakan Metode Hungarian Untuk menyelesaikan masalah penugasan, agar didapatkan penyelesaian yang optimal dapat menggunakan langkah-langkah sebagai berikut: 1. Menentukan entri terkecil dari setiap baris pada Tabel 2, lalu mengurangi semua entri dalam baris tersebut dengan entri terkecil. Matriks waktu untuk masalah ini adalah matriks .
[ ] Kurangkan 11 pada baris pertama, baris ke tiga, baris ke empat, baris ke lima dan baris ke tujuh, selanjutnya kurangkan 15 pada baris ke dua dan ke enam, untuk mendapatkan matriks berikut:
[
]
Optimalisasi Masalah Penugasan Menggunakan Metode Hungarian....
369
2. Memeriksa apakah setiap kolom telah mempunyai entri nol. Karena ke enam kolom matriks telah mengandung entri-entri nol, sehingga hanya perlu mengurangkan 4 (entri terkecil) pada kolom pertama. Hasilnya adalah matriks berikut:
[
]
3. Melakukan penutupan semua nilai nol dengan menggunakan garis vertikal/horizontal seminimal mungkin. Bila jumlah garis sudah sama dengan jumlah baris atau kolom, maka penugasan optimal. Jika jumlah garis belum sama dengan jumlah baris atau kolom, maka dilanjutkan ke langkah selanjutnya.
[ ] 4. Karena jumlah minimum garis-garis yang digunakan pada langkah 3 adalah enam garis, maka penugasan belum optimal dan harus dilakukan langkah selanjutnya. 5. Menentukan entri terkecil dari entri-entri yang tidak tertutup garis, kemudian semua entri yang tidak tertutup garis dikurangkan dengan entri terkecil, tetapi entri yang tertutup oleh dua garis ditambahkan dengan entri terkecil tersebut, kemudian dilakukan penutupan semua nilai 0 dengan menggunakan garis seminimal mungkin.
[
]
6. Matriks pada langkah 5 menunjukkan bahwa jumlah garis yang menutupi semua entri 0 sudah sama dengan jumlah baris/kolom, sehingga penugasan sudah optimal. Oleh karena itu penentuan penugasan sudah dapat dilakukan, dimulai dari baris/kolom yang hanya mempunyai satu nilai 0. Solusi/keputusan yang diperoleh adalah Dengan menyesuaikan variabel hasil keputusan ( , maka diperoleh total waktu optimal (minimal) yang dibutuhkan untuk mengantar barang ke 7 lokasi tersebut yaitu: Berdasarkan hasil perhitungan menggunakan metode Hungarian diperoleh total waktu optimal yaitu 93 menit, dengan penganturan penugasan sebagai berikut:
370
E. RAHMAWATI, N.SATYAHADEWI, F. FRANS
Tabel 4 Hasil Total Waktu Optimal Pekerja Lokasi Tujuan Tanjung Pura Rimba Gajah Mada Hendra Ayani Riki Sei Raya Dalam Wahyu Imam Bonjol Lukman Sungai Jawi Oki Jeruju Agus Total waktu optimal
Waktu (menit) 15 15 11 15 11 15 11 93
PENUTUP Dari hasil penelitian, waktu yang dibutuhkan perusahaan sebelum menggunakan metode Hungarian didapatkan hasil total waktu pengantaran barang pada PT Pos Indonesia (Persero) yaitu 98 menit, sedangkan jika menggunakan metode Hungarian didapatkan total waktu yaitu 93 menit. Jadi dapat disimpulkan bahwa perhitungan menggunakan metode Hungarian mendapatkan waktu yang lebih optimal jika dibandingkan dengan hasil yang diperoleh sebelum menggunakan metode Hungarian. Dalam hal ini, jika dibandingkan antara penempatan karyawan sebelumnya dengan menempatkan karyawan berdasarkan metode Hungarian, ternyata dapat terjadi efisiensi waktu sebanyak 5 menit, apabila perusahaan melakukan penempatan karyawan dalam pengantaran barang terhadap lokasi yang dituju yaitu Rimba ditugaskan ke Tanjung Pura, Wahyu ditugaskan ke Sungai Raya Dalam, Hendra ditugaskan ke Gajah Mada, Agus ditugaskan ke Jeruju, Riki ditugaskan ke Ayani, Oki ditugaskan ke Sungai Jawi, dan Lukman ditugaskan ke Imam Bonjol. DAFTAR PUSTAKA [1]. Taha, A. H. Riset Operasi, Jilid 1, Edisi ke-5. Jakarta: Binarupa Aksara; 1996. [2]. Hillier, S. F. dan Lieberman. Introduction To Operations Research, Eighth Edition, New York: Mc Graw-Hill; 2004. [3]. Anton, H dan Rorres, C.W. Aljabar Linear Elementer Versi Aplikasi. Edisi ke-8 [Indriasari, R. Alih bahasa]. Safitri, A. (ed), Jakarta: Erlangga; 2004. [4]. Aminudin. Prinsip-Prinsip Riset Operasi. Jakarta:Erlangga; 2005. ERLINDA RAHMAWATI : Jurusan Matematika FMIPA Untan, Pontianak,
[email protected] NEVA SATYAHADEWI : Jurusan Matematika FMIPA Untan, Pontianak,
[email protected] FRANSISKUS FRANS : Jurusan Matematika FMIPA Untan, Pontianak,
[email protected]
