Masalah Penugasan (Assignment Problem) Bentuk khusus metode transportasi
Introduction Kasus-kasus yang dapat diselesaikan dengan metode penugasan adalah : Penugasan beberapa karyawan untuk menyelesaikan beberapa pekerjaan Beberapa mesin untuk menyelesaikan beberapa pekerjaan Tujuan optimasi penugasan adalah meminimumkan biaya penugasan atau memaksimumkan keuntungan penugasan
Penugasan # Transportasi Jika menggunakan metode transportasi, yang
berperan sebagai sumber adalah tugas/pekerjaan dan sebagai tujuan adalah mesin atau pekerja Suplai pada semua sumber adalah1, yaitu ai = 1 untuk semua i Permintaan pada semua tujuan adalah 1, yaitu bj = 1 untuk semua j Karena xij menunjukkan penugasan, berarti nilainya hanya ada 2 yaitu nilai 0 atau 1 Xij = 1, jika pekerjaan i ditugaskan ke pekerja/mesin j Xij = 0, jika pekerjaan i tidak ditugaskan ke pekerja/mesin j
Assignment Problem Major Characteristics: Finite number of Team-Job (or the like) to be assigned. Assignment must be made based on one-to-one basis. Payoff matrix: cost (profit) for each possible assignment. Available Solution Techniques to Assignment Problem: Linear Programming Dynamic Programming Integer IP (Branch-and-Bound) Complete Enumeration Transportation Model (special case with all Si = di = 1) Hungarian Method (A "smart" method for large size problems)
Assignment Problem Special Cases in Assignment Problem: Prohibited Assignment (assign a large "M" as
cost) It is possible to have multiple optimal solutions. Special arrangement for a fixed assignment or One-to-More assignment.
Special Solution Procedure Hungarian Method: (Tabular Form) Principle: Add (or subtract) a constant to all cells of a row (or column) in the table will not change final optimal solution. Four-Step Procedure For Max Problem: (Transforming into Min Problem) Change the sign ("+" or "-") of each cell in the table. Add the largest cell value to all cells.
(Examples)
Masalah Minimisasi Contoh : Suatu perusahaan mempunyai 4 pekerjaan yang berbeda untuk diselesaikan oleh 4 karyawan
Tabel Matrik biaya Pekerjaan Karyawan
I
II
III
IV
A
Rp 15
Rp 20
Rp 18
Rp 22
B
14
16
21
17
C
25
20
23
20
D
17
18
18
16
Langkah-langkah Metode Hungarian
1. Mengubah Matriks biaya menjadi matriks opportunity cost: Caranya: pilih elemen terkecil dari setiap baris, kurangkan pada seluruh elemen baris tersebut Reduced cost matrix Pekerjaan Karyawan
I
II
III
IV
A
Rp0 15
Rp5 20
Rp3 18
7 22 Rp
B
0 14
2 16
7 21
3 17
C
5 25
0 20
3 23
0 20
D
1 17
2 18
2 18
0 16
2.
Reduced-cost matrix terus dikurangi untuk mendapatkan totalopportunity-cost matrix. pilih elemen terkecil dari setiap kolom pada RCM yang tidak mempunyai nilai nol, kurangkan pada seluruh elemen dalam kolom tersebut.
Reduced costcost matrix Total opportunity matrix Pekerjaan Karyawan
I
II
III
IV
A
0
5
31
7
B
0
2
3
C
5
0
75 31
D
1
2
20
0
http://rosihan.web.id
0
3.
Melakukan test optimalisasi dengan menarik sejumlah minimum garis horisontal dan/atau vertikal untuk meliput seluruh elemen bernilai nol
Penugasan optimal adalah feasible jika : jumlah garis = jumlah baris atau kolom Test of optimality Pekerjaan I Karyawan
II
III
IV
A
0
5
1
7
B
0
2
5
3
C
5
0
1
0
D
1
2
0
0
http://rosihan.web.id
4.
Tambahkan jumlah yang sama pada seluruh Untuk merevisi total-opportunity matrix, pilih elemen terkecil yang elemen yanggaris mempunyai dua garis belum terliput (1) untuk mengurangi seluruhyang elemensaling yang belum terliput bersilangan Ulangi langkah 3
Revised matrix dan Test of optimality Test of optimality Pekerjaan I Karyawan
II
III
IV
A
0
45
10
7 6
B
12
4 5
2 3
C
0 6 5
0
1
0
D
2 1
2
0
0
http://rosihan.web.id
Melakukan test optimalisasi dengan menarik sejumlah minimum garis horisontal dan/atau vertikal untuk meliput seluruh elemen bernilai nol Karena jumlah garis = jumlah baris atau kolom maka matrik penugasan optimal telah tercapai Revised matrix dan Test of optimality Pekerjaan Karyawan
I
II
III
IV
A
0
45
10
7 6
B
12
4 5
2 3
C
0 6 5
0
1
0
D
2 1
2
0
0
http://rosihan.web.id
Matrix optimal Pekerjaan Karyawan
A B C D
I
II
0 1
0 6 5
Tabel Matrik biaya Pekerjaan I Karyawan
IV 2
45
10
12
4 5
2 3
1
0
0
0 1
III
4
7 6
2
0
0
II
III
IV
3
A
Rp 15
Rp 20
Rp 18
Rp 22
B
14
16
21
17
C
25
20
23
20
D
17
18
18
16
http://rosihan.web.id
Skedul penugasan optimal Skedul penugasan A - III
Rp 18
B -I
14
C - II D - IV
20 16 Rp 68
Karyawan B ditugaskan untuk pekerjaan satu karena baris B hanya mempunyai satu nilai nol
Masalah Maksimisasi Contoh :
Suatu perusahaan mempunyai 5 pekerjaan yang berbeda untuk diselesaikan oleh 5 karyawan Tabel Matrik keuntungan Pekerjaan Karyawan
I
II
III
IV
V
A
Rp 10
Rp 12
Rp 10 Rp 8 Rp 15
B
14
10
9
15
13
C
9
8
7
8
12
D
13
15
8
16
11
E
10
13
14
11
17
Langkah-langkah Metode Hungarian
1.
Mengubah Matriks biaya menjadi matriks opportunity-loss: pilih elemen terbesar dari setiap baris, kurangkan pada seluruh elemen baris tersebut
Opportunity-loss matrix Pekerjaan Karyawan
I
II
III
IV
V
B
Rp5 10 1 14
Rp3 12 5 10
C
3 9
4 8
5 7
4 8
0 12
D
3 13
1 15
8 8
0 16
5 11
E
7 10
4 13
3 14
6 11
0 17
A
Rp5 10 Rp7 8 Rp0 15 6 9 0 15 2 13
Total Opportunity-loss matrix Pekerjaan Karyawan
I
II
A
5 10 4 Rp2
3 12 2 Rp0
B
0 1 14
4 5 10
C
3 9 2 0
D E
III
IV
V
5 10 Rp7 2 5 8 Rp0 15 Rp0
0 15
2 13 4
4 8 3 1
6 9 3 5 7 2 0
4 2 8
0 12
2 13 3
0 15 1
8 8 5
0 16
7 11 5
7 10 6
4 13 3
3 14 0
6 11
0 17 2
Karena jumlah garis = jumlah baris atau kolom maka matrik penugasan optimal telah tercapai Total Opportunity-loss matrix Pekerjaan Karyawan
2
I
4
II 3 12 2 Rp0
III
A
5 10 4 Rp2
B
0 1 14
4 5 10
C
3 9 2 0
4 8 3 1
6 3 9 5 7 2 0
D
2 13 3
0 15 1
8 8 5
E
7 10 6
4 13 3
3 14 0
IV
V
5 10 Rp5 2 7 8 Rp0 15 Rp0 5 0 15
1
4 8 2
3
2 13 4 0 12
0 16
7 11 5
6 11
0 17 2
