Bahan kuliah Riset Operasional
ASSIGNMENT MODELING Oleh: Darmansyah Tjitradi, MT. PROGRAM MAGISTER TEKNIK SIPIL UNLAM 2005 1
Background Assignment Modeling Metode ini dikembangkan oleh seorang berkebangsaan Hungaria bernama D. Konig pada tahun 1916, metode ini disebut juga Hungarian Method. Assignment Modeling merupakan salah satu pengembangan Linear Programming, namun mengalami modifikasi yang penyelesaiannya serupa dengan penyelesaian Metode Vogel’s Approximation (VAM) di permodelan Transportasi. Metode ini disebut juga dengan Metode Penugasan. 2
Background Assignment Modeling Metode ini secara umum berhubungan dengan personalia dan sumber daya manusia. Penentuan tiap personil untuk mengerjakan suatu tugas mempunyai beban biaya tertentu. Prinsip: Untuk menerapkan metode ini jumlah sumber yang ditugaskan harus sama persis dengan tugas yang harus diselesaikan, dan satu sumber untuk satu tugas. Berarti terdapat n sumber yang mempunyai n tugas. Ada n! (n faktorial) penugasan yang mungkin dalam suatu permasalahan. 3
Model penugasan merupakan kasus khusus dari model transportasi, di mana sejumlah m sumber ditugaskan kepada sejumlah n tujuan (satu sumber untuk satu tujuan) sedemikian sehingga didapat ongkos total yang minimum. Biasanya yang dimaksud dengan sumber ialah pekerjaan (atau pekerja) (Supply). Sedangkan yang dimaksud dengan tujuan ialah mesin-mesin (Demand). Jadi, dalam hal ini, ada m pekerjaan yang ditugaskan pada n mesin, di mana apabila pekerjaan i (1,2,3,…, m) ditugaskan kepada mesin j (1,2,3,…, n) akan muncul ongkos penugasan Cij. 4
Tabel Umum Model Penugasan:
Supply
Demand C11
C12
…
C1n
C21
C22
…
C2n
. . .
. . .
Cm1
Cm2
. . . …
Cmn
0, jika pekerjaan ke-i tidak ditugaskan pada mesin ke-j
Xij = 1, jika pekerjaan ke-i ditugaskan pada mesin ke-j 5
Bentuk Linear Programming: Maksimum/Minimumkan: m n
Z = ∑ ∑ Cij ⋅ Xij i = 1 j =1
Kendala: m
∑ Xij = 1, i = 1,2,3,L, m
i =1 n
∑ X ij = 1,
j =1
j = 1,2,3,L, n
Dan Xij = 0 atau 1 Dimana Cij adalah tetapan yang telah diketahui 6
Model Penugasan masalah Minimasi Misalnya: Suatu perusahaan ingin menyelesaikan pekerjaan dimana jumlah karyawan dan pekerjaan yang sama, seperti 4 pekerjaan (A, B, C, D) dengan 4 karyawan (1,2,3,4), lalu dengan lamanya pekerjaan oleh masing-masing karyawan: Karyawan Pekerjaan
1
2
3
4
A
6
7
10
9
B
2
8
7
8
C
8
9
5
12
D
7
11
12
3 7
Penjelasan Tabel: Baris A: Pekerjaan A dikerjakan oleh Karyawan 1 selama 6 jam Pekerjaan A dikerjakan oleh Karyawan 2 selama 7 jam Pekerjaan A dikerjakan oleh Karyawan 3 selama 10 jam Pekerjaan A dikerjakan oleh Karyawan 4 selama 9 jam
Baris B: Pekerjaan B dikerjakan oleh Karyawan 1 selama 2 jam Pekerjaan B dikerjakan oleh Karyawan 2 selama 8 jam Pekerjaan B dikerjakan oleh Karyawan 3 selama 7 jam Pekerjaan B dikerjakan oleh Karyawan 4 selama 8 jam
8
Penjelasan Tabel: Baris C: Pekerjaan C dikerjakan oleh Karyawan 1 selama 8 jam Pekerjaan C dikerjakan oleh Karyawan 2 selama 9 jam Pekerjaan C dikerjakan oleh Karyawan 3 selama 5 jam Pekerjaan C dikerjakan oleh Karyawan 4 selama 12 jam
Baris D: Pekerjaan D dikerjakan oleh Karyawan 1 selama 7 jam Pekerjaan D dikerjakan oleh Karyawan 2 selama 11 jam Pekerjaan D dikerjakan oleh Karyawan 3 selama 12 jam Pekerjaan D dikerjakan oleh Karyawan 4 selama 3 jam Pertanyaannya adalah bagaimana alokasi pekerjaan dan pekerja yang efektif agar tepat sasaran dengan waktu yang paling singkat? 9
Langkah Pertama: Ubahlah Tabel menjadi Matriks Opportunity Cost dengan mereduksi setiap baris dengan angka terkecil. Contoh : Baris A, angka yang paling kecil adalah 6, maka kotak A1=6-6=0, A2=7-6=1, A3=10-6=4, A4=9-6=3
Matriks Opportunity Cost (Aturan Horisontal) Karyawan Pekerjaan
1
2
3
4
A
0
1
4
3
B
0
6
5
6
C
3
4
0
7
D
4
8
9
0 10
Langkah Kedua: Tentukan kotak yang mempunyai nilai 0 (nol). Apabila terdapat satu nilai nol pada baris tertentu dan satu nilai nol pada kolom tertentu, maka pekerja akan ditugaskan pada pekerjaan tsb. Jika ada 2 nilai nol pilih karyawan yang produksinya paling cepat. Karyawan Pekerjaan
1
2
3
4
A
0
1
4
3
B
0
6
5
6
C
3
4
0
7
D
4
8
9
0 11
Langkah Ketiga: Pekerjaan D dikerjakan oleh Karyawan 4 Pekerjaan C dikerjakan oleh Karyawan 3 Pekerjaan B dikerjakan oleh Karyawan 1 (karena pekerjaan B paling kecil waktunya dibandingkan pekerjaan A) Karyawan Pekerjaan
1
2
3
4
A
0
1
4
3
B
0
6
5
6
C
3
4
0
7
D
4
8
9
0 12
Langkah Keempat: Ulangi lagi mereduksi baris yang belum tergaris, yaitu Baris A dengan nilai terkecil pada baris. Karyawan Pekerjaan
1
2
3
4
A
0
0
4
3
B
0
6
5
6
C
3
4
0
7
D
4
8
9
0
13
Langkah Kelima: Alokasikan pekerjaan pada elemen-elemen nol tsb. Tabel Akhir: Karyawan Pekerjaan
1
2
3
4
A
0
0
1
0
B
0
5
2
3
C
6
6
0
7
D
7
10
9
0
Alokasi Akhir: Pekerjaan A dikerjakan oleh Karyawan 2 Pekerjaan B dikerjakan oleh Karyawan 1 Pekerjaan C dikerjakan oleh Karyawan 3 Pekerjaan D dikerjakan oleh Karyawan 4 14
Langkah Keenam: Hitung banyaknya waktu yang terpakai dengan menjumlahkan semua komponen waktu yang terpakai. Pekerjaan A dikerjakan Karyawan 2 selama 7 jam Pekerjaan B dikerjakan Karyawan 1 selama 2 jam Pekerjaan C dikerjakan Karyawan 3 selama 5 jam Pekerjaan D dikerjakan Karyawan 4 selama 3 jam Total waktu = 17 jam Berarti waktu yang dibutuhkan untuk mengerjakan keempat tugas tersebut adalah 17 jam. Apabila keempat karyawan tersebut dibayar dengan upah Rp.50.000,- per jam, maka total biaya untuk mengerjakan tugas tersebut adalah Rp.50.000,- x 17 = Rp.850.000,-. 15
Model Penugasan masalah Minimasi Misalnya: Suatu perusahaan ingin menyelesaikan pekerjaan dimana jumlah karyawan dan pekerjaan yang sama, seperti 4 pekerjaan (A, B, C, D) dengan 4 karyawan (1,2,3,4), lalu dengan lamanya pekerjaan oleh masing-masing karyawan: Karyawan Pekerjaan
1
2
3
4
A
6
7
10
9
B
2
8
7
8
C
8
9
5
12
D
7
11
12
3 16
Langkah Pertama: Ubahlah Tabel menjadi Matriks Opportunity Cost dengan mereduksi setiap kolom dengan angka terkecil.
Contoh : Kolom A, angka yang paling kecil adalah 2, maka kotak A1=6-2=4, B1=2-2=0, C1=8-2=6, D1=7-2=5
Matriks Opportunity Cost (Aturan Vertikal) Karyawan Pekerjaan
1
2
3
4
A
4
0
5
6
B
0
1
2
5
C
6
2
0
9
D
5
4
7
0 17
Langkah Kedua: Tentukan kotak yang mempunyai nilai 0 (nol). Apabila terdapat satu nilai nol pada baris tertentu dan satu nilai nol pada kolom tertentu, maka pekerja akan ditugaskan pada pekerjaan tsb. Jika ada 2 nilai nol pilih karyawan yang produksinya paling cepat. Karyawan Pekerjaan
1
2
3
4
A
4
0
5
6
B
0
1
2
5
C
6
2
0
9
D
5
4
7
0
Eliminasi kolom merupakan langsung alokasi penugasan akhir.
18
Langkah Ketiga: Alokasikan pekerjaan pada elemen-elemen nol tsb. Tabel Akhir: Karyawan Pekerjaan
1
2
3
4
A
0
0
1
0
B
0
5
2
3
C
6
6
0
7
D
7
10
9
0
Alokasi Akhir: Pekerjaan A dikerjakan oleh Karyawan 2 Pekerjaan B dikerjakan oleh Karyawan 1 Pekerjaan C dikerjakan oleh Karyawan 3 Pekerjaan D dikerjakan oleh Karyawan 4 19
Langkah Keenam: Hitung banyaknya waktu yang terpakai dengan menjumlahkan semua komponen waktu yang terpakai. Pekerjaan A dikerjakan Karyawan 2 selama 7 jam Pekerjaan B dikerjakan Karyawan 1 selama 2 jam Pekerjaan C dikerjakan Karyawan 3 selama 5 jam Pekerjaan D dikerjakan Karyawan 4 selama 3 jam Total waktu = 17 jam Berarti waktu yang dibutuhkan untuk mengerjakan keempat tugas tersebut adalah 17 jam. Apabila keempat karyawan tersebut dibayar dengan upah Rp.50.000,- per jam, maka total biaya untuk mengerjakan tugas tersebut adalah Rp.50.000,- x 17 = Rp.850.000,-. 20
Model Penugasan masalah Maksimasi Misalnya: Seorang yang berpengalaman membuat suatu produk tertentu akan dapat menghasilkan produk lebih banyak dibandingkan karyawan lainnya. Karena itu, penugasan karyawan untuk memproduksi suatu produk tertentu perlu ditentukan dari banyaknya produk yang dihasilkan (maksimumkan jumlah produk). Karyawan Produk
1
2
3
4
A
6
7
10
9
B
2
8
7
8
C
8
9
5
12
D
7
11
12
3 21
Penjelasan Tabel: Baris A: Produk A diproduksi oleh Karyawan 1 sebanyak 6 buah Produk A diproduksi oleh Karyawan 2 sebanyak 7 buah Produk A diproduksi oleh Karyawan 3 sebanyak 10 buah Produk A diproduksi oleh Karyawan 4 sebanyak 9 buah
Baris B: Produk B diproduksi oleh Karyawan 1 sebanyak 2 buah Produk B diproduksi oleh Karyawan 2 sebanyak 8 buah Produk B diproduksi oleh Karyawan 3 sebanyak 7 buah Produk B diproduksi oleh Karyawan 4 sebanyak 8 buah
22
Penjelasan Tabel: Baris C: Produk C diproduksi oleh Karyawan 1 sebanyak 8 buah Produk C diproduksi oleh Karyawan 2 sebanyak 9 buah Produk C diproduksi oleh Karyawan 3 sebanyak 5 buah Produk C diproduksi oleh Karyawan 4 sebanyak 12 buah
Baris D: Produk D diproduksi oleh Karyawan 1 sebanyak 7 buah Produk D diproduksi oleh Karyawan 2 sebanyak 11 buah Produk D diproduksi oleh Karyawan 3 sebanyak 12 buah Produk D diproduksi oleh Karyawan 4 sebanyak 3 buah
23
Langkah Pertama: Ubahlah Tabel menjadi Matriks Opportunity Cost dengan mereduksi setiap baris dengan angka terbesar. Contoh : Baris A, angka yang paling besar adalah 10, maka kotak A1=|6-10|=4, A2=|7-10|=3, A3=|10-10|=0, A4=|9-10|=1
Matriks Opportunity Cost (Aturan Horisontal) Karyawan Produk
1
2
3
4
A
4
3
0
1
B
6
0
1
0
C
4
3
7
0
D
5
1
0
9 24
Langkah Kedua: Tentukan kotak yang mempunyai nilai 0 (nol). Apabila terdapat satu nilai nol pada baris tertentu dan satu nilai nol pada kolom tertentu, maka pekerja akan ditugaskan pada pekerjaan tsb. Jika ada 2 nilai nol pilih karyawan yang produksinya paling cepat. Karyawan Produk
1
2
3
4
A
4
3
0
1
B
6
0
1
0
C
4
3
7
0
D
5
1
0
9 25
Langkah Ketiga: Produk C diproduksi oleh Karyawan 4 Produk D diproduksi oleh Karyawan 3 Produk B diproduksi oleh Karyawan 2
Karyawan Produk
1
2
3
4
A
4
3
0
1
B
6
0
1
0
C
4
3
7
0
D
5
1
0
9
26
Langkah Keempat: Ulangi lagi mereduksi baris yang belum tergaris, yaitu Baris A dengan nilai terkecil pada baris. Karyawan Produk
1
2
3
4
A
0
3
0
1
B
6
0
1
0
C
4
3
7
0
D
5
1
0
9
27
Langkah Kelima: Alokasikan pekerjaan pada elemen-elemen nol tsb. Tabel Akhir: Karyawan Produk
1
2
3
4
A
0
2
0
0
B
2
0
1
0
C
0
3
7
0
D
3
0
0
8
Alokasi Akhir: Produk A diproduksi oleh Karyawan 1 Produk B diproduksi oleh Karyawan 2 Produk C diproduksi oleh Karyawan 4 Produk D diproduksi oleh Karyawan 3 28
Langkah Keenam: Hitung banyaknya waktu yang terpakai dengan menjumlahkan semua komponen waktu yang terpakai. Produk A diproduksi Karyawan 1 sebanyak 6 buah Produk B diproduksi Karyawan 2 sebanyak 8 buah Produk C diproduksi Karyawan 4 sebanyak 12 buah Produk D diproduksi Karyawan 3 sebanyak 12 buah Total produksi = 38 buah
29
Model Penugasan masalah Maksimasi Misalnya: Seorang yang berpengalaman membuat suatu produk tertentu akan dapat menghasilkan produk lebih banyak dibandingkan karyawan lainnya. Karena itu, penugasan karyawan untuk memproduksi suatu produk tertentu perlu ditentukan dari banyaknya produk yang dihasilkan (maksimumkan jumlah produk). Karyawan Produk
1
2
3
4
A
6
7
10
9
B
2
8
7
8
C
8
9
5
12
D
7
11
12
3 30
Langkah Pertama: Ubahlah Tabel menjadi Matriks Opportunity Cost dengan mereduksi setiap kolom dengan angka terbesar. Contoh :
Kolom A, angka yang paling besar adalah 2, maka kotak A1=|6-8|=2, B1=|2-8|=6, C1=|8-8|=0, D1=|7-8|=1
Matriks Opportunity Cost (Aturan Vertikal) Karyawan Produk
1
2
3
4
A
2
4
2
3
B
6
3
5
4
C
0
2
7
0
D
1
0
0
9 31
Langkah Kedua: Tentukan kotak yang mempunyai nilai 0 (nol). Apabila terdapat satu nilai nol pada baris tertentu dan satu nilai nol pada kolom tertentu, maka pekerja akan ditugaskan pada pekerjaan tsb. Jika ada 2 nilai nol pilih karyawan yang produksinya paling cepat. Karyawan Produk
1
2
3
4
A
2
4
2
3
B
6
3
5
4
C
0
2
7
0
D
1
0
0
9 32
Langkah Ketiga: Produk C diproduksi oleh Karyawan 4 Produk D diproduksi oleh Karyawan 3 Karyawan Produk
1
2
3
4
A
2
4
2
3
B
6
3
5
4
C
0
2
7
0
D
1
0
0
9
33
Langkah Keempat: Ulangi lagi mereduksi kolom yang belum tergaris, yaitu Kolom 1 dan 2 dengan nilai terkecil pada kolom. Karyawan Produk
1
2
3
4
A
0
1
2
3
B
4
0
5
4
C
0
2
7
0
D
1
0
0
9
34
Langkah Kelima: Alokasikan pekerjaan pada elemen-elemen nol tsb. Tabel Akhir: Karyawan Produk
1
2
3
4
A
0
2
0
0
B
2
0
1
0
C
0
3
7
0
D
3
0
0
8
Alokasi Akhir: Produk A diproduksi oleh Karyawan 1 Produk B diproduksi oleh Karyawan 2 Produk C diproduksi oleh Karyawan 4 Produk D diproduksi oleh Karyawan 3 35
Langkah Keenam: Hitung banyaknya waktu yang terpakai dengan menjumlahkan semua komponen waktu yang terpakai. Produk A diproduksi Karyawan 1 sebanyak 6 buah Produk B diproduksi Karyawan 2 sebanyak 8 buah Produk C diproduksi Karyawan 4 sebanyak 12 buah Produk D diproduksi Karyawan 3 sebanyak 12 buah Total produksi = 38 buah
36
KESIMPULAN Eleminasi pada penyelesaian Model Penugasan dapat menggunakan 2 cara, yaitu: 1. ATURAN HORISONTAL, aturan ini mengeliminasi setiap BARIS dengan ANGKA TERKECIL (kasus Minimasi) dan ANGKA TERBESAR (kasus Maksimasi). 2. ATURAN VERTIKAL, aturan ini mengeliminasi setiap KOLOM dengan ANGKA TERKECIL (kasus Minimasi) dan ANGKA TERBESAR (kasus Maksimasi).
37
