5.

PENUGASAN

Penugasan (assignment) merupakan suatu bentuk spesial dari problem transpor -

tasi. Perbedaannya ialah dalam model penugasan suplai pada tiap sumber dan
demand pada tiap tujuan dibatasi satu unit.

Aplikasi dalam dunia usaha misalnya penugasan n karyawan untuk

melaksanakan n jenis pekerjaan. Masalah timbul karena terdapat keragaman
karyawan dari faktor umur, pengalaman, pendidikan, dan faktor lainnya. Hetero -
genitas ini dapat mempengaruhi besarnya biaya yang dikeluarkan perusahaan.
Dalam hal ini perusahaan ingin menentukan siapa ditugasi apa, agar total biaya
minimal (problem minimisasi).

5.1. Problem Minimisasi

Metode Hungarian (Kuhn, 1955) adalah salah satu metode pemecahan problem
penugasan. Untuk ini, banyak suplai (misalnya karyawan ) harus sama dengan
banyak demand (misalnya pekerjaan). Bila tidak sama harus ditambahkan suplai/
demand dummy. Setiap karyawan hanya dapat ditugasi satu pekerjaan saja, dan
sebaliknya satu tugas hanya dikerjakan satu karyawan. Seperti problem transpor-
tasi, baris menunjukkan sumber dan kolom menunjukkan demand/tugas. Secara
matematis problem penugasan dapat dirumuskan sebagai :
Minimumkan fungsi tujuan: Z =  Cij Xij

Penugasan seseorang untuk pekerjaan yang berbeda dapat menimbulkan

biaya yang berbeda pula, yang akan disajikan dalam suatu matriks biaya.

Langkah-Langkah Penyelesaian Problem Minimisasi

OPERATIONS RESEARCH – Penugasan/Assignment 33

1. Kurangi setiap elemen suatu baris dengan elemen terkecil pada baris tersebut.
2. Pada kolom yang belum ada angka nol kurangi setiap elemen dengan elemen
terkecil pada kolom tersebut. Matriks hasil langkah 1 dan 2 ini merupakan
matriks opportunity cost .
3. Liput seluruh angka nol dengan garis horisontal atau vertikal, tapi dengan ke -
tentuan banyaknya garis minimal. Penugasan sudah optimal apabila banyak
garis liputan = banyak baris atau kolom. Apabila banyak garisk kurang dari
banyak baris atau kolom, berarti solusi belum optimal, teruskan ke langkah 4.
4. Kurangi seluruh angka yang tidak terkena garis dengan angka terkecil di an -
tara yang tidak terkena garis. Selanjutnya tambahkan angka terkecil tadi ke
tiap elemen pada garis silang (perpotongan garis datar dan tegak), sedangkan
angka lain tidak dirubah. Ulangi langkah 3
5. Bila solusi belum juga optimal ulangi langkah 4.
6. Setelah solusi optimal tentukan penugasan, yaitu tugaskan karyawan untuk
tugas dengan nilai opportunity cost-nya nol. Terakhir hitung nilai Z.

Contoh 5.1
Sebuah perusahaan pengecoran logam empat jenis mesin: M1, M2, M3, M4,
dengan kapasitas yang berbeda-beda. Biaya operasi mesin untuk jenis pekerjaan
yang berbeda (T1, T2, T3, T4) seperti pada Tabel 5.1 berikut.
Tabel 5.1 BIAYA OPERASI EMPAT MESIN UNTUK EMPAT TUGAS (RP)

Tugas
Mesin
T1 T2 T3 T4
M1 210 140 150 200
M2 150 160 175 115
M3 180 200 220 160
M4 130 190 200 190
.
Masalahnya: bagaimana menugaskan keempat mesin tersebut untuk menyele-
saikan empat jenis pekerjaan, agar total biaya pekerjaan minimum.
Langkah Penyelesaian:

33
OPERATIONS RESEARCH – Penugasan/Assignment 34

1. Setiap elemen baris dikurangi biaya terkecil ; hasilnya pada Tabel 5.2 berikut:
Tabel 5.2 HASIL PENGURANGAN BARIS
Tugas
Mesin
T1 T2 T3 T4
M1 70 0 10 60
M2 35 45 60 0
M3 20 40 60 0
M4 0 60 70 60

2. Hanya kolom T3 yang tidak ada angka nol; kurangi semua dengan elemen
terkecil (45), hasilnya pada Tabel 5.3.
Tabel 5.3 HASIL PENGURANGAN KOLOM
Tugas
Mesin
T1 T2 T3 T4
M1 70 0 0 60
M2 35 45 50 0
M3 20 40 50 0
M4 0 60 60 60

3. liput semua angka nol dengan garis datar dan tegak (lihat Tabel 5.3); solusi
belum optimal karena banyak garis tersebut hanya tiga, harusnya empat.
4. Seluruh elemen yang tidak kena garis dikurangi elemen terkecil yang tidak
kena garis, dan elemen pada garis silang ditambah elemen terkecil tersebut.
Elemen terkecil yang tidak kena garis adalah 20. Lakukan langkah 3, hasilnya
pada Tabel 5.4.
Tabel 5.4 HASIL ITERASI LANGKAH KE - 4 & 3
Tugas
Mesin
T1 T2 T3 T4
M1 70 0 0 80
M2 15 25 30 0
M3 0 20 30 0
M4 0 60 60 80

34
OPERATIONS RESEARCH – Penugasan/Assignment 35

Ternyata banyak garis yang meliput angka nol hanya tiga solusi belum optimal.
Ulangi langkah 4 dan uji dengan langkah 3, hasilnya pada Tabel 5.5.
Tabel 5.5 HASIL PENGULANGAN LANGKAH KE - 4 & 3
Tugas
Mesin
T1 T2 T3 T4
M1 90 0 0 100
M2 15 5 10 0
M3 0 0 10 0
M4 0 40 40 80

Karena banyak garis yang meliput angka nol = banyak baris = banyak kolom = 4,
maka penugasan sudah optimal. Lakukan penugasan sebagai berikut:

Mesin => Tugas Biaya

 M1 => T3 150
 M2 => T4 115
 M3 => T1 200
 M4 => T2 130
Total Biaya 595

5.2. Problem Maksimisasi

Dalam kasus lain mungkin perusahaan ingin menentukan penugasan kepada

stafnya untuk beberapa pekerjaan yang akan menghasilkan keuntungan atau
produktivitas yang berbeda-beda pula. Di sini perusahaan ingin memaksi -
mumkan keuntungan atau produktivitas.

Langkah-Langkah Penyelesaian Problem Minimisasi

1. Pada setiap baris elemen –elemennya dikurangi dengan angka terbesar pada
baris yang bersangkutan. Jadi beda dengan problem minimisasi ! Hasilnya
dinyatakan dalam harga mutlak, yaitu positif.
2. Langkah berikutya sama persis dengan masalah minimisasi.

35
OPERATIONS RESEARCH – Penugasan/Assignment 36

5.3. Penyimpangan

Yang dimaksud dengan penyimpangan adalah :

a. Banyak tugas tidak sama dengan banyak karyawan yang ada. Kalau terjadi
demikian maka langkah pertama harus dibuat dummy karyawan atau tugas agar
matriks menjadi bujursangkar dan diisi dengan elemen nol, selanjutnya ikuti
prosedur seperti telah dijelaskan.
b. Ada karyawan dengan alasan tertentu tidak dapat mengerjakan suatu
pekerjaan tertentu, untuk memecahkan masalah ini kita hanya menandai setiap
elemen penugasan yang tidak mungkin dilakukan dengan dengan tanda M-
untuk masalah minimisasi dan M+ untuk masalah maksimisasi. Langkah
berikutnya sama persis dengan metode yang telah dibahas di atas,hanya perlu
perhatian bahwa seseorang untuk pekerjaan tertentu yang elemennya diberi
tanda M- atau M+ harus dihindari.

36