isnaini nurisusilawati...kotak hadiah tersebut memiliki 5 orang sales promotion yang akan ditugaskan...

Isnaini Nurisusilawati

TUJUAN PEMBELAJARAN

Mahasiswa mampu memahami konsep assignment dan

penerapannya

Mahasiswa mampu memahami metode pencarian solusi optimal

Model penugasan merupakan kasus khusus dari model transportasi,dimana sejumlah m sumber ditugaskan kepada sejumlah n tujuan (satusumber untuk satu tujuan) sedemikian sehingga didapat ongkos totalyang minimum.

Biasanya yang dimaksud dengan sumber adalah mesin-mesin,sedangkan yang dimaksud dengan tujuan ialah pekerjaan (atau job).

Terdapat m mesin (M1, M2, …, Mm).

Terdapat n job (J1, J2, …, Jn) yang harus ditugaskan (dikerjakan) padamesin.

Biaya pengerjaan untuk setiap job tergantung pada mesin yangdigunakan.

Biaya pengerjaan job j pada mesin i dinyatakan dengan Cij.

Tiap mesin hanya dapat mengerjakan satu job.

Karena itu, bentuk standar model penugasan ini adalah jumlah mesin(m) sama dengan jumlah job (n) yaitu sama dengan n.

Permasalahannya adalah dengan menentukan penugasan job padamesin yang meminimumkan biaya total.

Minimumkan Z = σ𝑖=1𝑛 σ𝑗=1

𝑛 𝐶𝑖𝑗 𝑋𝑖𝑗

Berdasarkan pembatas:

σ𝑗=1𝑛 𝑋𝑖𝑗 = 1 i = 1, 2, 3, …,n

σ𝑖=1𝑛 𝑋𝑖𝑗 = 1 j = 1, 2, 3, …,n

Xij = 0 atau 1

𝑋𝑖𝑗 = ቊ1, 𝑗𝑖𝑘𝑎 𝑗𝑜𝑏 𝑗 𝑑𝑖𝑡𝑢𝑔𝑎𝑠𝑘𝑎𝑛 𝑝𝑎𝑑𝑎 𝑚𝑒𝑠𝑖𝑛 𝑖0, 𝑦𝑎𝑛𝑔 𝑙𝑎𝑖𝑛

1 2 … n

1 C11 C12 … C1n 1

2 C21 C22 … C2n 1

. . . . .

. . . . .

. . . . .

m Cm1 Cm2 … Cmn 1

1 1 … 1

Tujuan

Sumber

Metode Hungarian adalah metode yang memodifikasi baris dan kolomdalam matriks efektivitas sampai muncul sebuah komponen nol tunggaldalam setiap baris atau kolom yang dapat dipilih sebagai alokasipenugasan.

Persyaratan:

1. Jumlah kolom (sumber daya ) harus sama dengan jumlah baris(tugas) yang harus diselesaikan

2. Setiap sumber daya hanya dapat mengerjakan satu tugas

3. Apabila jumlah sumber tidak sama dengan jumlah tugas atausebaliknya, maka ditambahkan variabel dummy worker atau dummy job

Masalah penugasan

Minimalisasi

Pengalokasian tugaskepada sumber dayasehingga diperoleh

biaya total minimum

Maksimalisasi

Pengalokasian tugaskepada sumber dayasehingga diperolehkeuntungan yang

maksimum

1. Identifikasi dan penyederhanaan masalah dalam bentuk tabel penugasan

2.1 Kasus minimalisasi: cari biaya terkecil untuk setiap baris, dan kemudianmenggunakan biaya terkecil tersebut untuk dikurangi oleh semua biaya yang adapada baris yang sama

2.2 Kasus maksimasi: cari nilai tertinggi untuk setiap baris, yang kemudian nilaitertinggi tersebut sebagai pengurang semua nilai yang ada dalam baris tersebut

2.3 Kasus tidak normal: bila jumlah sumber tidak sama dengan jumlah tugas atausebaliknya, maka di dalam tabel penugasan perlu ditambahkan variabel dummyyang nilainya nol (0)

Suatu perusahaan kotak hadiah mempunyai empat pekerjaan yang berbeda, yaitumemotong karton, merekatkan kertas warna, memberi hiasan, danmembungkus. Perusahaan kotak hadiah tersebut hanya memiliki empat orangkaryawan yaitu Hana, Karin, Helmi, dan Rossy. Upah seorang karyawan untukmasing-masing pekerjaan berbeda-beda seperti berikut:

Tentukan besarnya biaya optimal yang dikeluarkan perusahaan kotak hadiahtersebut dengan kondisi satu pekerjaan hanya dikerjakan oleh satu karyawan?

Hana Karin Helmi Rossy

Memotong karton Rp 15.000 Rp 14.000 Rp 18.000 Rp 17.000

Merekatkan kertas warna Rp 21.000 Rp 16.000 Rp 18.000 Rp 22.000

Memberi hiasan Rp 21.000 Rp 21.000 Rp 24.000 Rp 19.000

Membungkus Rp 22.000 Rp 18.000 Rp 20.000 Rp 16.000

Identifikasi dan penyederhanaan masalah ke dalam tabel penugasan

Tujuan: mencari biaya optimal kasus minimasi

Jumlah pekerjaan = jumlah karyawan (kasus normal)

Tabel Penugasan:

I II III IV

A 15 14 18 17

B 21 16 18 22

C 21 21 24 19

D 22 18 20 16

Cari biaya terkecil untuk setiap baris, lalu menggunakan biaya terkeciltersebut untuk menjadi pengurang semua biaya pada baris yang sama.

I II III IV

A 15 14 18 17

B 21 16 18 22

C 21 21 24 19

D 22 18 20 16

I II III IV

A 15 – 14 14 - 14 18 - 14 17 - 14

B 21 – 16 16 – 16 18 – 16 22 – 16

C 21 - 19 21 - 19 24 - 19 19 - 19

D 22 - 16 18 - 16 20 - 16 16 - 16

Apabila ditemukan nol maka tarik garis seminimum mungkin. Jika jumlahgaris sama dengan jumlah baris/kolom berarti pemecahan sudah optimal.

Jumlah garis yang dapat ditarik hanya 2, tidak sama dengan jumlah baris/kolomyang ada (4) = belum optimal

I II III IV

A 1 0 4 3

B 5 0 2 6

C 2 2 5 0

D 6 2 4 0

Pada kolom tak terkena garis, pilih nilai terkecil, kemudian kurangi nilai lainpada kolom yang sama dengan nilai kecil tersebut.

I II III IV

A 1 0 4 3

B 5 0 2 6

C 2 2 5 0

D 6 2 4 0

I II III IV

A 1 – 1 0 4 - 2 3

B 5 – 1 0 2 – 2 6

C 2 – 1 2 5 – 2 0

D 6 – 1 2 4 - 2 0

Tarik garis seminimum mungkin, baik ke arah vertikal maupun horizontalyang meliputi semua yang bernilai nol. Jika jumlah garis sama denganjumlah baris/kolom berarti pemecahan optimal.


I II III IV

A 0 0 2 3

B 4 0 0 6

C 1 2 3 0

D 5 2 2 0

Revisi tabel yaitu dengan mengurangi sel-sel yang tidak terkena dengan nilaiterkecil, kemudian tambahkan nilai sel terkecil itu pada sel yang terkenagaris 2x sedang nilai yang terkena garis 1x tetap.


I II III IV

A 0 0 2 3 + 1 = 4

B 4 0 0 6 + 1 = 7

C 1 - 1 2 - 1 3 – 1 0

D 5 - 1 2 - 1 2 - 1 0

Tentukan apakah sudah terdapat nilai nol pada baris dan kolom yang berbeda.Apabila sudah terdapat nilai nol di setiap baris dan kolom yang berbeda makasudah didapatkan hasil yang optimal. Atau jika jumlah garis sama denganjumlah baris/kolom berarti pemecahan sudah optimal.

Jumlah garis yang dapat ditarik = 4 = jumlah baris/kolom yang ada (4) = optimal

I II III IV

A 0 0 2 4

B 4 0 0 7

C 0 1 2 0

D 4 1 1 0

Alokasi pekerjaan untuk masing-masing karyawan adalah:

Pekerjaan A, menggunting karton dikerjakan oleh Karin, dengan upah sebesarRp 14.000

Pekerjaan B, merekatkan kertas warna dikerjakan oleh Helmi dengan upahsebesar Rp 18.000

Pekerjaan C, memberi hiasan dikerjakan oleh Hana dengan upah sebesar Rp21.000

Pekerjaan D, membungkus dikerjakan oleh Rossy, dengan upah sebesar Rp16.000

Pekerjaan Karyawan Biaya

Memotong karton Karin Rp 14.000

Merekatkan kertas warna Helmi Rp 18.000

Memasang hiasan Hana Rp 21.000

Membungkus Rossy Rp 16.000

Total biaya upah Rp 69.000

Suatu perusahaan kotak hadiah mempunyai 5 lokasi penjualan untuk produknyayaitu di Stroberry, Naughty, Cindy, Toko Kado Unik, dan Gramedia. Perusahaankotak hadiah tersebut memiliki 5 orang sales promotion yang akan ditugaskan kemasing-masing lokasi tersebut. Berdasarkan kemampuan masing-masing sales dankondisi pasar, berikut ini hasil penjualan yang diperkirakan akan diperoleh denganpenugasan masing-masing sales ke lokasi.

Tentukan besarnya pendapatan perusahaan bila satu lokasi hanya dijaga oleh satusales!

Fitri Dian Mieky Amanda Suzan

Stroberry Rp 100.000 Rp 120.000 Rp 100.000 Rp 80.000 Rp 150.000

Naughty Rp 140.000 Rp 100.000 Rp 90.000 Rp 150.000 Rp 130.000

Cindy Rp 80.000 Rp 80.000 Rp 70.000 Rp 90.000 Rp 120.000

Toko Kado

Unik

Rp 130.000 Rp 150.000 Rp 80.000 Rp 160.000 Rp 110.000

Gramedia Rp 100.000 Rp 130.000 Rp 140.000 Rp 110.000 Rp 170.000

Identifikasi dan penyederhanaan masalah dalam tabel penugasan.

Tujuan: mencari pendapatan optimal = kasus maksimasi

Jumlah lokasi = jumlah sales kasus normal

Tabel Penugasan:

I II III IV V

A 10 12 10 8 15

B 14 10 9 15 13

C 8 8 7 9 12

D 13 15 8 16 11

E 10 13 14 11 17

Cari nilai terbesar untuk setiap baris, kemudian gunakan nilai terbesartersebut untuk mengurang semua biaya yang ada pada baris yang sama.

I II III IV V

A 10 12 10 8 15

B 14 10 9 15 13

C 8 8 7 9 12

D 13 15 8 16 11

E 10 13 14 11 17

I II III IV V

A 15 - 10 15 - 12 15 - 10 15 - 8 15 - 15

B 15 - 14 15 - 10 15 - 9 15 - 15 15 - 13

C 12 - 8 12 - 8 12 - 7 12 - 9 12 - 12

D 16 - 13 16 - 15 16 - 8 16 - 16 16 - 11

E 17 - 10 17 - 13 17 - 14 17 - 11 17 - 17

Pastikan semua baris dan kolom sudah memiliki nilai nol.

Ternyata masih terdapat kolom yang belum memiliki nilai nol. Maka, pada setiapkolom, pilih nilai terkecil, kemudian gunakan nilai terkecil tersebut sebagaipengurang setiap nilai yang ada pada kolom yang sama.

I II III IV V

A 5 - 1 3 – 1 5 – 3 7 0

B 1 – 1 5 – 1 6 – 3 0 2

C 4 – 1 4 – 1 5 – 3 3 0

D 3 – 1 1 – 1 8 – 3 0 5

E 7 - 1 4 - 1 3 – 3 6 0

Tarik garis seminimum mungkin, baik ke arah vertical maupun horizontalyang meliputi semua yang bernilai nol. Jika jumlah garis sama dengan jumlahbaris/kolom berarti pemecahan sudah optimal.

Jumlah garis yang dapat ditarik hanya 4, tidak sama dengan jumlah baris/kolomyang ada (5) = belum optimal.

I II III IV V

A 4 2 2 7 0

B 0 4 3 0 2

C 3 3 2 3 0

D 2 0 5 0 5

E 6 3 0 6 0

Revisi tabel, yaitu dengan mengurangi sel-sel yang tidak terkena garis dengannilai terkecil. Kemudian tambahkan nilai sel terkecil itu pada sel yang terkenagaris 2x sedang nilai yang terkena garis 1x tetap.

Jumlah garis yang dapat ditarik hanya 4, tidak sama dengan jumlah baris/kolomyang ada (5) = belum optimal.

I II III IV V

A 4 - 2 2 - 2 4 – 2 7 - 2 0

B 0 4 3 0 2 + 2

C 3 - 2 3 - 2 2 - 2 3 - 2 0

D 2 0 5 0 5 + 2

E 6 3 0 6 0 + 2

Tentukan apakah sudah terdapat nilai nol pada baris dan kolom yang berbeda,apabila sudah terdapat nilai nol di setiap baris dan kolom yang berbeda makasudah didapatkan hasil yang optimal. Atau jika jumlah hgaris yang samadengan jumlah baris/kolom berarti pemecahan sudah optimal.

Jumlah garis yang dapat ditarik = 5 = jumlah baris/kolom = optimal.

I II III IV V

A 2 0 0 5 0

B 0 4 3 0 4

C 1 1 0 1 0

D 2 0 5 0 7

E 6 3 0 6 2

Toko Sales Biaya

Stroberry Dian Rp 120.000

Naughty Fitri Rp 140.000

Cindy Suzan Rp 120.000

Toko Kado Unik Amanda Rp 160.000

Gramedia Mieky Rp 140.000

Total biaya upah Rp 680.000

Seorang kepala tukang mendapat proyek sebuah rumah. Target proyek ini selesai 6 bulan.Pekerja yang dibutuhkan adalah sebagai tukang kayu, tukang cat, pembantu tukang,tukang bangunan. Kepala tukang kesulitan dalam memilih para pekerja karena semuapekerja memiliki keahlian yang tidak jauh berbeda, tariff, atau permintaan ongkos satusama lain juga tidak jauh berbeda. Dalam hal ini, kepala tukang ingin meminimalkanbiaya keluar untuk ongkos para pekerja agar mendapatkan keuntungan yang lebihbesar. adapun pekerja yang mengajukan diri sebagai pekerja dalam proyek tersebutbeserta ongkos yang mereka inginkan tertera dalam tabel berikut:

Toni Tono Toto

Tukang kayu 70 85 50

Tukang cat 45 60 55

Pembantu tukang 60 65 70

Tukang bangunan 60 50 55

Identifikasi masalah

Jumlah pekerja dengan pekerja tidak sama = kasus tidak normal

Perlu adanya variabel dummy di kolom pekerja

Yang dicari adalah biaya optimum, kasus minimasi

Tabel Penugasan

Toni Tono Toto Dummy

Tukang kayu 70 85 50 0

Tukang cat 45 60 55 0

Pembantu tukang 60 65 70 0

Tukang bangunan 60 50 55 0

Karena di tiap baris sudah memiliki angka nol yang berasal dari dummy, maka yangharus dicari adalah nilai terkecil pada kolom lainnya. Untuk kemudian dikurangidengan nilai lain pada kolom tersebut.


Tukang kayu 70 – 45 85 - 50 50 - 50 0

Tukang cat 45 – 45 60 – 50 55 – 50 0

Pembantu tukang 60 – 45 65 – 50 70 – 50 0

Tukang bangunan 60 – 45 50 - 50 55 - 50 0

Tiap baris dan kolom sudah memiliki nilai nol

Jumlah garis yang ditarik = jumlah baris dan kolom

Optimal



Tukang cat 0 10 5 0



Alokasi pekerjaan:

- Toto tukang kayu

- Toni tukang cat

- Tono tukang bangunan

- Dummy pembantu tukang



Tukang cat 0 10 5 0



Jadi total ongkos pekerja yang harus dikeluarkan kepala tukang sebesar Rp 145.000dan pekerjaan pembantu tukang ditugaskan kepada dummy yang diasumsikan tidakada yang mengerjakan.

Pekerjaan Pekerja Ongkos (Rp dalam ribuan)

Tukang kayu Toto 50

Tukang cat Toni 45

Tukang bangunan Dummy 0

Pembantu tukang Tono 50

Total ongkos pekerja 145

Dummy ada untuk menyeimbangkan antara banyaknya tugas dengan banyaknyapenerima tugas

Apabilapenerima tugas mendapatkan pekerjaan dummy, berarti diasumsikanbahwa penerima tugas tersebut menganggur

Apabila tugas tersebut diberikan kepada Dummy, diasumsikan pekerjaan itu tidakada yang mengerjakan.

Penugasan empat job dan empat mesin dengan biaya penugasan

J1 J2 J3 J4

M1 10 9 8 7

M2 3 4 5 6

M3 2 1 1 2

M4 4 3 5 6

Reduksi Baris

- Cari nilai minimum tiap baris.

- Kurangkan masing-masing nilai biaya dengan biaya minimum tiap baris.

J1 J2 J3 J4

M1 10 9 8 7

M2 3 4 5 6

M3 2 1 1 2

M4 4 3 5 6

J1 J2 J3 J4

M1 10 – 7 9 – 7 8 - 7 7 – 7

M2 3 – 3 4 – 3 5 – 3 6 – 3

M3 2 – 1 1 – 1 1 – 1 2 – 1

M4 4 - 3 3 - 3 5 – 3 6 - 3

- Periksa nilai 0

- Solusi dikatakan layak jika terdapat nilai 0 yang memasangkan masing-masing 1 mesin terhadap 1 job.

- Buat garis yang melalui nilai 0

- Jumlah garis harus sama dengan jumlah mesin/job.

J1 J2 J3 J4

M1 3 2 1 0

M2 0 1 2 3

M3 1 0 0 1

M4 1 0 3 3

Biaya penugasan total, Z = 7 + 3 + 1 + 3 = 14

M1 J4

M2 J1

M3 J3

M4 J2

J1 J2 J3 J4

M1 3 2 1 0

M2 0 1 2 3

M3 1 0 0 1

M4 1 0 3 3

J1 J2 J3 J4

M1 10 9 8 7

M2 3 4 5 6

M3 2 1 1 2

M4 4 3 5 6

Penugasan empat job dan empat mesin dengan biaya penugasan

J1 J2 J3 J4

M1 10 9 7 8

M2 5 8 7 7

M3 5 4 6 5

M4 2 3 4 5

Reduksi Baris

- Cari nilai minimum tiap baris.


J1 J2 J3 J4

M1 10 9 7 8

M2 5 8 7 7

M3 5 4 6 5

M4 2 3 4 5

J1 J2 J3 J4

M1 10 – 7 9 – 7 7 - 7 8 – 7

M2 5 – 5 8 – 5 7 – 5 7 – 5

M3 5 – 4 4 – 4 6 – 4 5 – 4

M4 2 - 2 3 - 2 4 – 2 5 - 2

- Periksa nilai 0

- Solusi dikatakan layak jika terdapat nilai 0 yang memasangkan masing-masing 1 mesin terhadap 1 job.

J1 J2 J3 J4

M1 3 2 0 1

M2 0 3 2 2

M3 1 0 2 1

M4 0 1 2 3

Solusi belum layak

Reduksi Kolom

- Cari nilai minimum tiap kolom.


J1 J2 J3 J4

M1 3 2 0 1

M2 0 3 2 2

M3 1 0 2 1

M4 0 1 2 3

J1 J2 J3 J4

M1 3 - 0 2 – 0 0 – 0 1 – 1

M2 0 – 0 3 – 0 2 – 0 2 – 1

M3 1 – 0 0 – 0 2 – 0 1 – 1

M4 0 - 0 1 - 0 2 - 0 3 – 1

Modifikasi Matriks

- Tarik garis (horizontal/vertikal) yang menghubungkan nilai-nilai nol.

- Buat garis seminimum mungkin (biasanya jumlah kolom - 1)

- Tandai elemen terkecil yang tidak tertutup garis

- Tambahkan nilai elemen yang berada pada titik potong dua garis dengan nilai elementerkecil yang tidak tertutup baris

J1 J2 J3 J4

M1 3 2 0 0

M2 0 3 2 1

M3 1 0 2 0

M4 0 1 2 2

J1 J2 J3 J4

M1 3 + 1 2 0 0

M2 0 3 - 1 2 – 1 1 - 1

M3 1 + 1 0 2 0

M4 0 1 - 1 2 - 1 2 - 1

J1 J2 J3 J4

M1 4 2 0 0

M2 0 2 1 0

M3 2 0 2 0

M4 0 0 1 1

J1 J2 J3 J4

M1 4 2 0 0

M2 0 2 1 0

M3 2 0 2 0

M4 0 0 1 1

Biaya penugasan total, Z = 7 + 5 + 5 + 3 = 20

M1 J3

M2 J1

M3 J4

M4 J2

J1 J2 J3 J4

M1 10 9 7 8

M2 5 8 7 7

M3 5 4 6 5

M4 2 3 4 5

isnaini nurisusilawati...kotak hadiah tersebut memiliki 5 orang sales promotion yang akan ditugaskan...

Documents