BAB III. Persoalan Penugasan Multi Kriteria

15

BAB III Persoalan Penugasan Multi Kriteria

A. Pengertian Penugasan Masalah penugasan (assignment problem) adalah suatu masalah mengenai pengaturan objek untuk melaksanakan tugas, dengan tujuan meminimalkan biaya, waktu, jarak, dan sebagainya ataupun memaksimalkan keuntungan yang salah satu penyelesaiannya menggunakan metode Hungaria (Soemartojo, 1997). Masalah umum penugasan meliputi n tugas yang harus ditetapkan kepada m pekerja dimana setiap pekerja memiliki kompetensi yang berbeda dalam menyelesaik an setiap tugasnya.

B. Persoalan Penugasan Sederhana Persoalan penugasan sederhana adalah persoalan penugasan yang hanya memiliki satu tujuan kriteria, yaitu memaksimalkan atau meminimalkan suatu sumber daya (biaya, waktu, kualitas atau jarak) yang digunanakan untuk menyelesaikan tugas. Masalah penugasan merupakan jenis khusus pemrograman linier dimana sumber-sumber dialokasikan kepada kegiatan-kegiatan atas dasar satusatu (one-to-one basis) (Hillir,dkk,1990:242). Jadi setiap sumber atau petugas (assignee) seperti mesin atau karyawan ditugasi secara khusus kepada suatu kegiatan atau tugas. Ada suatu biaya cij yang berkaitan dengan petugas i (i = 1,2,…,m) yang melakukan tugas j (j = 1,2,…,n), sehingga tujuannya adalah untuk menentukan bagaimana semua tugas harus dilakukan untuk meminimumkan total biaya. Jadi persoalan penugasan akan mencakup sejumlah m pekerja yang mempunyai n tugas. Dengan asumsi n = m, sehingga akan ada n! penugasan yang mungkin dalam suatu masalah karena harus berpasangan satu-satu. Apabila pekerja i(i = 1,2,…,m) ditugaskan kepada tugas j(j = 1,2,…n) maka akan muncul biaya penugasan cij, sehingga jelas bahwa tujuan dari penugasan adalah mencari Eka Arifani Putri, 2014 Aplikasi pengambilan keputusan Dalam persoalan penugasan multi kriteria Universitas Pendidikan Indonesia | repository.upi.edu | perpustakaan.upi.edu15

16

penggunaan total biaya yang minimum dari semua pekerja dalam menyelesaikan semua tugas. Banyak cara menyelesaikan persoalan penugasan, salah satunya adalah dengan metode Hungaria.

C. Model Matematis Persoalan Penugasan Sederhana Persoalan penugsan yang sederhana dengan mempertimbangkan situasi penugasan m pekerja ke n tugas. Ketika pekerja i (i = 1, 2, ..., m) ditugaskan ke tugas j ( j = 1, 2, ..., n), maka pekerja i dalam menyelesaikan tugas j memerlukan biaya cij. Sehingga tujuannya adalah menugaskan pekerja - pekerja tersebut ke tugas -tugas (satu pekerja per satu tugas) dengan biaya total terendah. Suatu masalah umum penugasan yang hanya berkaitan dengan biaya operasi dapat direpresentasikan seperti pada Tabel 3.1. Ada n tugas yang akan ditugaskan untuk m pekerja, cij adalah biaya operasi pekerja i untuk melaksanakan tugas j.

Tabel 3.1 Matriks Biaya Operasi Pekerja

Tugas 1

2

3

…

j

…

n

1

c11

c12

c13

…

c1j

…

c1n

2

c21

c22

c23

…

c2j

…

c2n

3

c31

c32

c33

…

c3j

…

c3n

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

i

ci1

ci2

ci3

…

cij

…

cin

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

m

cm1

cm2

cm3

…

cmj

…

cmn

Eka Arifani Putri, 2014 Aplikasi pengambilan keputusan Dalam persoalan penugasan multi kriteria Universitas Pendidikan Indonesia | repository.upi.edu | perpustakaan.upi.edu16

17

Bila pada suatu masalah ditemui adanya jumlah tugas dan pekerja berbeda (jumlah baris ≠ jumlah kolom), maka untuk menyamakan jumlahnya perlu ditambahkan suatu variabel semu (F.S Hillir, dkk:243) , yaitu ditambahkan suatu tugas (kolom) semu jika jumlah tugas (kolom) lebih kecil daripada jumlah pekerja (baris) dan sebaliknya ditambahkan suatu pekerja (baris) semu jika jumlah pekerja (baris) lebih kecil daripada jumlah tugas (kolom). Penambahan baris ataupun kolom semu ini merupakan langkah awal dalam pembuatan tabel matriks penugasan agar dapat diselesaikan menggunakan metode Hungaria. Dengan demikian diasumsikan bahwa jumlah pekerja sama dengan jumlah tugas (m = n). Fungsi objektif pada persolan penugasan ini dapat ditulis sebagai berikut

∑

∑

∑ ∑

x ij = {

(3.1)

Dimana Z adalah jumlah optimum yang hendak dicapai.

D. Metode Hungaria Salah satu metode yang digunakan untuk menyelesaikan masalah penugasan adalah metode Hungaria. Metode ini di temukan oleh Horald Kuhn pada tahun 1955 dan disempurnakan oleh Jones Munkes pada tahun 1957 keduanya berkebangsaaan Hungaria. Oleh karena itu metode Hungaria biasa disebut juga algoritma Kuhn-Munkes. Metode Hungaria ini mempunyai kelebihan dalam segi kesederhaan algoritma dan dari segi kemudahan untuk dipahami. Oleh karena itu metode ini merupakan pilihan para peneliti untuk menyelesaikan masalah penugasan. Eka Arifani Putri, 2014 Aplikasi pengambilan keputusan Dalam persoalan penugasan multi kriteria Universitas Pendidikan Indonesia | repository.upi.edu | perpustakaan.upi.edu17

18

Metode Hungaria adalah metode yang memodifikasi baris dan kolom dalam matriks efektifitas sampai muncul sebuah komponen nol tunggal dalam setiap baris atau kolom yang dapat dipilih sebagai alokasi penugasan (Prawisentono, 2005). Semua alokasi penugasan yang dibuat adalah alokasi yang optimal, dan saat diterapkan pada matriks efektifitas awal, maka akan memberikan hasil penugasan yang paling minimum. Menurut Taha (1996) memaparkan syarat-syarat metode Hungaria, yaitu sebagai berikut: 1. Jumlah baris harus sama dengan jumlah kolom yang harus diselesaikan 2. Setiap sumber harus mengerjakan satu tugas 3. Jika jumlah sumber tidak sama dengan jumlah tugas atau sebaliknya, maka perlu ditambahkan variabel semu sumber atau variabel semu tugas 4. Terdapat dua permasalahan yaitu meminimuman kerugian atau memaksimumkan keuntungan Jadi dalam penyelesaiannya, secara umum persoalan penugasan dibagi dua yaitu

masalah

maksimalisasi

dan

minimalisasi.

Langkah- langkah

proses

penyelesaian masalah penugasan menggunakan metode Hungaria dengan matriks adalah sebagai berikut: a. Masalah Minimalisasi Langkah-langkah untuk masalah minimalisasi adalah sebagai berikut: 1. Identifikasi dan penyederhanaan masalah dalam bentuk tabell matriks penugasan 2. Menentukan nilai terkecil dari setiap baris, kemudian mengurangkan setiap nilai dalam baris tersebut dengan nilai terkecilnya 3. Periksa apakah setiap kolom telah mempunyai nilai nol. Bila sudah dilanjutkan pada langkah ke-4 , jika belum, dilakukan penentuan nilai terkecil dari setiap kolom yang belum mempunyai nilai nol, kemudian setiap nilai pada kolom tersebut dikurangkan dengan nilai terkecilnya 4. Lakukan

penutupan

semua

nilai

nol dengan

menggunakan

garis

vertika/horizontal seminimal mungkin. Bila jumlah garis sudah sama dengan Eka Arifani Putri, 2014 Aplikasi pengambilan keputusan Dalam persoalan penugasan multi kriteria Universitas Pendidikan Indonesia | repository.upi.edu | perpustakaan.upi.edu18

19

jumlah baris atau kolom, maka tabel telah optimal. Jika jumlah garis belum sama dengan jumlah baris atau kolom maka dilanjutkan pada langkah ke-5 5. Ditentukan nilai terkecil dari nilai-nilai yang tidak tertutup garis. Lalu semua nilai yang tidak tertutup garis dikurangkan dengan nilai terkecil tersebut, dan nilai yang tertutup oleh dua garis ditambahkan dengan nilai terkecil tersebut 6. Kembali pada langkah ke-4 (Dodi Rahardjo, 2010:9) Untuk dapat melihat lebih jelas dalam proses minimalisasi, diberikan sebuah contoh sebagai berikut: Table 3.2 Contoh Matriks Masalah Minimalisasi Pekerja P1 P2 P3 P4

Tugas A 4 7 5 6

B 2 8 5 3

C 1 9 4 2

D 3 6 2 4

Tentukan nilai terkecil dari setiap barisnya, lalu kurangkan setiap nilai dalam baris tersebut dengan nilai terkecilnya. Maka diperoleh: Tabel 3.3 Hasil Perhitungan Pertama Pekerja P1 P2 P3 P4

Tugas A 3 1 3 4

B 1 2 3 1

C 0 3 2 0

D 2 0 0 2

Karena pada Tabel 3.3 belum semua kolom memiliki nilai nol, maka tentukan nilai terkecil pada setiap kolomnya lalu kurangkan nilai pada kolom tersebut dengan nilai terkecilnya. Kemudian lakukan penarikan garis seminimal mungkin terhadap nilai nol. Maka diperoleh: Tabel 3.4 Hasil Perhitungan Kedua Eka Arifani Putri, 2014 Aplikasi pengambilan keputusan Dalam persoalan penugasan multi kriteria Universitas Pendidikan Indonesia | repository.upi.edu | perpustakaan.upi.edu19

20

Pekerja P1 P2 P3 P4

Tugas A 2 0 2 3

B 0 1 2 0

C 0 3 2 0

D 2 0 0 2

Berdasarkan Tabel 3.4 jumlah garis sudah sama dengan jumlah baris atau kolom artinya penyelesaian sudah optimal. Maka diperoleh kesimpulannya yaitu P1 mengerjakan tugas B, P2 mengerjakan tugas A, P3 mengerjakan tugas D dan P4 mengerjakan tugas C. Dengan nilai optimalnya adalah Z = 2 + 7 + 2 + 2 = 13

b. Masalah Maksimalisai Langkah-langkah untuk maksimalisasi adalah sebagai berikut: 1. Identifikasi dan penyederhanaan masalah dalam bentuk tabel matriks penugasan 2. Ditentukan nilai terbesar dari setiap baris, kemudian nilai terbesar tersebut dikurangkan dengan setiap nilai dalam barisnya 3. Diperiksa apakah setiap kolo telah mempunyai nilai nol. Bila sudah dilanjutkan pada langkah ke-4, jika belum, dilakukan penentuan nilai terkecil dari setiap kolom yang belum mempunyai nilai nol, kemudian setiap nilai pada kolom tersebut dikurangkan dengan nilai terkecilnya 4. Dilakukan penutupan semua nilai nol dengan menggunakan garis vertikal/ horizontal seminimal mungkin. Bila jumlah garis sudah sama dengan jumlah garis atau kolom, maka tabel telah optimal.jika jumlah garis belum sama dengan jumlah garis atau kolom, maka dlanjutkan pada langkah ke-5. 5. Ditentukan nilai terkecil dari nilai-nilai yang tidak tertutup garis. Lalu semua nilai yang tidak tertutup garis dikurangkan dengan nilai terkecil tersebut, dan nilai yang tertutup oleh dua garis ditambahkan dengan nilai terkecil tersebut. 6. Kembali pada langkah ke-4. (Dodi Rahardjo, 2010:9) Eka Arifani Putri, 2014 Aplikasi pengambilan keputusan Dalam persoalan penugasan multi kriteria Universitas Pendidikan Indonesia | repository.upi.edu | perpustakaan.upi.edu20

21

Untuk dapat lebih jelas dalam memahami proses maksimalisasi, diberikan sebuah contoh sebagai berikut: Tabel 3.5 Contoh Matriks Masalah Maksimalisasi Pekerja P1 P2 P3 P4

Tugas A 2 4 6 5

B 2 4 1 3

C 3 9 7 9

D 5 7 8 8

Tentukan nilai terkecil dari setiap barisnya, lalu kurangkan setiap nilai dalam baris tersebut dengan nilai terkecilnya. Maka diperoleh: Tabel 3.6 Hasil Perhitungan Pertama Pekerja P1 P2 P3 P4

Tugas A 3 5 2 4

B 3 5 7 6

C 2 0 1 0

D 0 2 0 1

Karena pada Tabel 3.6 belum semua kolom memiliki nilai nol, maka tentukan nilai terkecil pada setiap kolomnya lalu kurangkan nilai pada kolom tersebut dengan nilai terkecilnya. Kemudian lakukan penarikan garis seminimal mungkin terhadap nilai nol. Maka diperoleh: Tabel 3.7 Hasil Perhitungan Kedua Pekerja P1 P2 P3 P4

Tugas A 1 3 0 2

B 0 2 4 3

C 2 0 1 0

D 0 2 0 1


22

Terlihat pada Tabel 3.7 jumlah garis belum sama dengan jumlah baris atau kolom, maka perlu dilakukan perbaikan. Sehingga diperoleh: Tabel 3.8 Hasil Perbaikan Pekerja P1 P2 P3 P4

Tugas A 1 2 0 1

B 0 1 4 2

C 3 0 2 0

D 0 2 0 0

Berdasarkan Tabel 3.8 jumlah garis sudah sama dengan jumlah baris atau kolom artinya penyelesaian sudah optimal. Maka diperoleh kesimpulannya yaitu P1 mengerjakan tugas B, P2 mengerjakan tugas C, P3 mengerjakan tugas A dan P4 mengerjakan tugas D. Dengan nilai optimalnya adalah Z = 2 + 9 + 6 + 8 = 25

E. Persoalan Penugasan Multi Kriteria Banyak penelitian telah dikembangkan untuk memecahkan masalah penugasan. Sebagian besar metode yang dikembangkan untuk masalah penugasan hanya mempertimbangkan situasi satu tujuan, seperti masalah meminimumkan biaya penugasan, meminimumkan waktu penyelesaian masalah. Meminimumkan biaya dalam masalah penugasan terfokus pada bagaimana memberikan tugas kepada pekerja sehingga total biaya operasi dapat diminimalkan, begitu juga dalam meminimumkan waktu penyelesaian hanya terfokus pada bagaimana memberikan tugas kepada pekerja sehingga total waktu operasi dapat diminimalkan. Dalam pembahasan penugasan multi kriteria ini akan digunakan lebih dari satu kriteria atau faktor yang digunakan sekaligus untuk menentukan satu pekerja tepat bersesuaian dengan satu tugas. Persoalan penugasan multi kriteria adalah persoalan penugasan yang melibatkan lebih dari satu kriteria, baik berupa kuantitatif maupun kualitatif. Sehingga tujuan yang hendak dicapai adalah untuk menetapkan masing- masing Eka Arifani Putri, 2014 Aplikasi pengambilan keputusan Dalam persoalan penugasan multi kriteria Universitas Pendidikan Indonesia | repository.upi.edu | perpustakaan.upi.edu22

23

pekerja yang tepat terhadap satu tugas sehingga dapat meminimumkan atau memaksimalkan penyelesaian setiap tugas dengan beberapa kriteria yang ada (Chiao-Pin Bao,dkk, 2007).

1. Mengoptimalkan dua kriteria Jika proses penyelesaian masalah penugasan ini hanya mempertimbangkan dua kriteria, katakanlah biaya operasi dan waktu yang diperlukan yaitu bagaimana menetapkan tugas agar biaya dan total waktu operasi dapat minimum secara bersamaan. Tabel matriks dengan dua kriteria ditunjukkan pada tabel dibawah ini:

Tabel 3.9 Matriks Biaya dan Waktu Operasi Tugas

Pekerja

1

3 …

2

…

j

c11

c12

c13

t11

t12

t13

c21

c22

c23

t21

t22

t23

c31

c32

c33

t31

t32

t33

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

ci1

ci2

ci3

ti1

ti2

ti3

.

.

.

1

2

3

i .

… … …

… .

c1j

n

t1j c2j t2j c3j t3j

cij tij

… … …

…

.

.


c1n t1n c2n t2n c3n t3n

cin tin .

24

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

cm1

cm2

cm3

tm1

tm2

tm3

m

cmj

…

…

tmj

cmn tmn

Karena proses penyelesaian mempertimbangkan dua kriteria , maka secara matematis bobot dari masing- masing tujuan harus ditetapkan terlebih dahulu, agar dapat mengetahui kriteria mana yang lebih penting daripada kriteria yang lain atau tingkat kepentingan dari masing-masing kriteria Maka fungsi tujuannya adalah

Minimumkan C,T =

∑

∑

∑

+

∑

(3.2)

Dimana C adalah total biaya operasi dari pekerja, T adalah total waktu operasi dari pekerja. Sedangkan α adalah besar bobot yang dimiliki setiap kriteria, dengan ∑

. cij dan tij adalah biaya dan waktu operasi

pekerja yang telah dinormalisasikan. Data biaya dan waktu yang dinormalkan yaitu menyetarakan semua data dengan cara membagi data biaya dan waktu dengan data maksimum dari masing- masing biaya dan waktu. Selanjutnya digunakan metode Hungaria untuk mengoptimalkan biaya dan waktu secara bersamaan. Untuk lebih jelasnya, diberikan sebuah contoh masalah minimalisasi dengan menggunakan kriteria biaya (ribuan) dan waktu (hari) sebagai berikut: Tabel 3.10 Contoh Matriks Dua Kriteria Tempat T1 T2

Barang B1 8 3 8

B2 9 4 8

B3 7 3 5

B4 6 2 9


25

T3 T4

3 9 3 7 3

4 8 3 6 2

2 6 2 7 2

3 7 2 9 3

Data pada Tabel 3.10 harus dinormalisasikan dahulu, sebelum dikerjakan dengan metode Hungaria. Maka diperoleh: Tabel 3.11 Data Normalisasi Dua Kriteria Tempat T1 T2 T3 T4

Barang B1 0.889 0.75 0.889 0.75 1 0.75 0.778 0.75

B2 1 1 0.889 1 0.889 0.75 0.667 0.5

B3 0.778 0.75 0.556 0.5 0.667 0.5 0.778 0.5

B4 0.667 0.5 1 0.75 0.778 0.5 1 0.75

Misalkan untuk kedua bobot diketahui α1 = biaya= 0,5 dan α2 = waktu= 0,5 dengan menggunakan fungsi (3.2) maka diperoleh:

Tabel 3.12 Jumlah Data Penormalan Biaya dan Waktu Tempat

B1

Barang B2 B3

B4

T1

0.8194

1

0.7638

0.5833

T2

0.8194

0.9444

0.5277

0.8750

T3

0.8750

0.8194

0.5833

0.6388

T4

0.7638

0.5833

0.6388

0.8750


26

Selanjutnya digunakan metode Hungaria. Tentukan nilai terkecil dari setiap barisnya, lalu kurangkan setiap nilai dalam baris tersebut dengan nilai terkecilnya. Maka diperoleh: Tabel 3.13 Hasil Perhitungan Pertama Tempat

B1

Barang B2 B3

B4

T1

0.2361

0.4167

0.1806

0

T2

0.2916

0.4166

0

0.3472

T3

0.2917

0.2361

0

0.0556

T4

0.1806

0

0.0556

0.291667

Karena pada Tabel 3.13 belum semua kolom memiliki nilai nol, maka tentukan nilai terkecil pada setiap kolomnya lalu kurangkan nilai pada kolom tersebut dengan nilai terkecilnya. Kemudian lakukan penarikan garis seminimal mungkin terhadap nilai nol. Maka diperoleh:

Tabel 3.14 Hasil Perhitungan Kedua Barang Tempat

B1

B2

B3

B4

T1

0,0555 0,4167

0,1805

0

T2

0,1111 0,4166

0

0,3472

T3

0,1111 0,2361

0

0,0556

T4

0

0

0,0556 0,2916


27

Terlihat pada Tabel 3.14 jumlah garis belum sama dengan jumlah baris atau kolom, maka perlu dilakukan perbaikan. Sehingga diperoleh: Tabel 3.15 Hasil Perbaikan Pertama Barang

Tempat T1

B1

B2

B3

B4

0

0,3612

0,1805

0

T2

0,0556 0,3611

0

0,3472

T3

0,0556 0,1806

0

0,0556

T4

0

0

0,1111 0,3471

Karena pada Tabel 3.15 jumlah garis belum sama dengan jumlah baris atau kolom, maka perlu dilakukan perbaikan lagi. Sehingga diperoleh: Tabel 3.16 Hasil Perbaikan Kedua Tempat

Barang B1

B2

B3

B4

T1

0

0,3612

0,2361

0

T2

0

0,3055

0

0,2916

T3

0

0,1250

0

0

T4

0

0

0,1667 0,3471

Berdasarkan Tabel 3.16 jumlah garis sudah sama dengan jumlah baris atau kolom artinya penyelesaian sudah optimal. Maka diperoleh kesimpulannya yaitu T1 memilih barang B4, T2 memilih barang B1, T3 memilih barang B3 dan T4 memilih barang B2. Dengan jumlah biaya sebesar 6 + 8 + 6 + 6 = 26 (ribuan) dan dengan jumlah waktu selama 2 + 3 + 2 + 2 = 9 (hari)

2. Mengoptimalkan tiga Kriteria


28

Masalah penugasan dengan tiga kriteria yaitu pengoptimalan biaya, waktu dan kualitas dimana semua tujuan harus diminimumkan. Sebelumnya harus disumsikan bobot dari biaya, waktu dan kualitas, yaitu α1 , α2 , α3 dengan α1 + α2 + α3 = 1,sehingga gabungan fungsi tujuannya adalah

Minimumkan C,T,Q =

∑

∑

∑

+

∑

+

∑

∑

(3.3) Dimana C,T,Q adalah biaya operasi dari pekerja, waktu operasi dari pekerja dan kualitas barang yang dihasilkan. Sedangkan α1 , α2 , α3 adalah bobot dari biaya, waktu dan kualitas. Tabel 3.17 Matriks Biaya, Waktu dan Kualitas Tugas

kerja q

2

3

…

j

…

n

1

c11,t11,q11

c12 ,t12 ,q12

c13 ,t13 ,q13

…

c1j,t1j,q1j

…

c1n ,t1n ,q1n

2

c21 ,t21 ,q21

c22 ,t22 ,q22

c23 ,t23 ,q23

…

c2j,t2j,q2j

…

c2n ,t2n ,q2n

3

c31 ,t31 ,q21

c32 ,t32 ,q32

c33 ,t33 ,q33

…

c3j,t3j,q3j

…

c3n ,t3n ,q3n

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

i

ci1 ,ti1 ,qi1

ci2 ,ti2 ,qm2

ci3 ,ti3 ,qi3

…

cij,tij,qij

…

cin ,tin ,qin

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

m

cm1 ,tm1 ,qm1

cm2 ,tm2 ,qm

cm3 ,tm3 ,qm

2

3

…

cmj,tmj,qm j


…

cmn ,tmn ,qm n

BAB III. Persoalan Penugasan Multi Kriteria

Recommend Documents