Assignment Problem

By Nadia Asandimitra,SE.,MM
 Pendahuluan

 Adanya beberapa pekerjaan yang berbeda-beda cara

penyelesaian.
 Karyawan memiliki keahlian dan sifat yang berbeda-
beda.
 Cara alokasi yang berbeda akan memberi konsekuensi
hasil atau pengorbanan yang berbeda.
 Perencanaan penugasan menggunakan Algoritma
atau Hungarian method
 Ada 2 macam Algoritma

 Algoritma dengan tujuan meminimumkan

 Algoritma dengan tujuan memaksimalkan
 Masalah Minimasi

 Meminimumkan pengorbananMeminimumkan
biaya
 Menggunakan matriks atau tabel yang berisi biaya
penugasan karyawan.
 Contoh

 Bagian produksi perusahaan mempunyai 3 jenis

pekerjaan yang berbeda untuk diselesaikan oleh 3
karyawan.
 Ketiga karyawan tersebut mempunyai tingkat
ketrampilan, pengalaman kerja, latar belakang
pendidikan dan latihan yang berbeda pula.
 Karena sifat pekerjaan dan kemampuan karyawan
berbeda, maka biaya penyelesaian pekerjaan
berbeda-beda
 Pekerjaan
Karyawan
D1 D2 D3

A1 20 27 30
A2 10 18 16
A3 14 16 12
Langkah-langkah : membuat opportunity cost matrix

• Nilai tiap baris dikurangi dengan nilai terkecil

dari baris itu.
Pekerjaan
Karyawan
D1 D2 D3
A1 0 7 10
A2 0 8 6
A3 2 4 0
 Membuat Total Opportunity Cost
Matrix

 Jika dalam tabel Opportunity Cost Matrix

masih ada kolom yang tidak memiliki angka
nol maka harus dibuat agar kolom tersebut
memiliki nilai nol dengan mengurangi nilai-
nilai pada kolom itu dengan nilai kolom
yang terkecil.
 Pekerjaan
Karyawan
D1 D2 D3

A1 0 3 10

A2 0 4 6

A3 2 0 0
 Menggambar garis untuk meliputi
angka nol

 Jika jumlah garis minimum yang bisa dibuat kurang

dari jumlah baris atau kolom maka harus diubah lagi
dan
 Jika jumlah garis minimum yang dibuat paling tidak
sama dengan jumlah baris atau kolom maka alokasi
yang optimal sudah bisa diperoleh
 Pekerjaan
Karyawan
D1 D2 D3

A1 0 3 10

A2 0 4 6

A3 2 0 0
 Merubah Total Opportunity Cost
Matrix dengan cara

 Pilih angka terkecil di antara semua angka belum

terliput oleh garis dan semua angka yang belum
terliput garis dikurangi dengan angka terkecil.
 Nilai yang terliput oleh 2 garis yang saling bersilangan
harus ditambah dengan angka terkecil yang belum
terliput garis (yang dipakai untuk mengurangi pada
butir di atas).
 Ulangi lagi langkah ke 3 untuk melakukan tes
optimalisasi.
 Pekerjaan
Karyawan
D1 D2 D3

A1 0 0 7

A2 0 1 3

A3 5 0 0
Membuat alokasi penugasan, caranya

 Letakkan karyawan pada salah satu

pekerjaan yang nilainya pada total
opportunity cost dan satu pekerjaan hanya
bisa diisi oleh satu orang saja.
 Tugaskan dulu karyawan yang hanya
memiliki satu nilai nol.
Skedul penugasan Biaya

A1 ­ D2 Rp. 27.000,-

A2 ­ D1 Rp. 10.000,-

A3 ­ D3 Rp. 12.000,-

Total Rp. 49.000,-

 Masalah Maksimasi

 Sama dengan Algoritma dengan tujuan

meminimumkan, perbedaannya hanya pada langkah
pertama
 Pada langkah pertama dicari dulu selisih data
keuntungan pada tiap-tiap baris dengan keuntungan
terbesar pada baris itu.
 Contoh

 Suatu perusahaan yang akan menugaskan 4 karyawan

yang berbeda kemampuannya untuk 4 pekerjaan
yang berbeda pula.
 Data terperinci tentang kontribusi laba masing-
masing karyawan sebagai berikut
 Pekerjaan
Karyawan
D1 D2 D3 D4

A1 12 14 12 10

A2 16 12 11 17

A3 11 10 9 10

A4 15 17 10 18
Langkah-langkah : Membuat Opportunity Loss Matrix

 Mengurangi nilai-nilai keuntungan tiap baris dengan

nilai terbesar dari baris itu.
 Pekerjaan
Karyawan
D1 D2 D3 D4

A1 2 0 2 4

A2 1 5 6 0

A3 0 1 2 1

A4 3 1 8 0
 Membuat total Opportunity Loss
Matrix

 Dengan merubah nilai pada kolom yang belum

memiliki angka nol dengan bilangan terkecil dari
kolom tersebut.
 Pekerjaan
Karyawan
D1 D2 D3 D4

A1 2 0 0 4

A2 1 5 4 0

A3 0 1 0 1

A4 3 1 6 0
 Membuat garis yang meliputi nilai-nilai nol

Pekerjaan
Karyawan
D1 D2 D3 D4

A1 2 0 0 4

A2 1 5 4 0

A3 0 1 0 1

A4 3 1 6 0
 Merubah Total Opportunity Loss
Matrix

 Angka yang belum terliput garis dikurangi dengan

angka terkecil dari belum yang terliput
 Angka yang terliput garis dua kali harus ditambah
dengan angka pengurangan tersebut.
 Setelah itu lakukan tes optimalisasi.
 Pekerjaan
Karyawan
D1 D2 D3 D4

A1 2 0 0 5

A2 0 4 3 0

A3 0 1 0 2

A4 2 0 5 0
 Membuat alokasi penugasan

Skedul Kontribusi Skedul Kontribusi

penugasan 1 laba penugasan 2 laba
A1­D2 14.000 A1­D3 12.000
A2­D1 16.000 A2­D4 17.000
A3­D3 9.000 A3­D1 11.000
A4­D4 18.000 A4­D2 17.000
Total 57.000 Total 57.000
 JUMLAH BARIS ≠ JUMLAH KOLOM

 Jika jumlah karyawan tidak sama dengan jumlah

pekerjaan maka perlu digunakan bantuan variable
dummy atau variable semu/boneka.
 Guna variable ini untuk mengisi ketidakcocokan tersebut.
 Kalau jumlah baris (karyawan) lebih sedikit maka perlu
ditambahkan baris semu dengan biaya (atau laba)
sebesar 0.
 Sebaliknya bila jumlah kolom (pekerjaan) lebih sedikit
maka perlu ditambahkan kolom semu.
 Pekerjaan
I II III IV V
Karyawan
Tina 20 24 20 16 27
Tini 28 20 18 30 17
Tino 16 18 14 16 25
Toni 26 30 16 32 21
 Karena jumlah baris < jumlah kolom maka perlu
ditambah baris semu sbb:

Pekerjaan I II III IV V
Karyawan
Tina 20 24 20 16 27
Tini 28 20 18 30 17
Tino 16 18 14 16 25
Toni 26 30 16 32 21
Dummy 0 0 0 0 0
 Cara penyelesaiannya seperti langkah-langkah yang
dijelaskan di depan, baik untuk minimisasi maupun
maksimisasi
 LATIHAN SOAL
 Suatu perusahaan akan mengalokasikan 4 orang
karyawan untuk 3 macam tugas.
 Setiap karyawan menyelesaikan 1 tugas. Biaya yang
dibutuhkan untuk tiap tugas (dalam ribuan Rp) adalah:
Keuntungan yang diperoleh
Karyawan
Tugas 1 Tugas 2 Tugas 3
A 10 16 32
B 14 22 40
C 22 24 34
D 14 18 36

 Carilah alokasi karyawan yang bisa meminimumkan

biaya.