RO14-15_Materi Assignment

RO - Masalah Penugasan (Assignment Problem)

Pendahuluan Masalah penugasan (assignment problems), seperti juga masalah transportasi merupakan suatu kasus khusus yang ditemui dalam pemrograman linier (linier programming). Dalam masalah penugasan ini kita akan mendelegasikan sejumlah tugas (assignment) kepada sejumlah penerima tugas (assignee) dalam basis satu-satu. Jadi pada masalah penugasan ini diasumsikan bahwa jumlah assignment sama dengan jumlah assignee. Jadi data pokok pertama yang harus dimiliki dalam menyelesaikan suatu masalah penugasan adalah jumlah assignee dan jumlah assignment. Selain data jumlah assignee dan jumlah assignment yang terlibat, data lain yang biasa diperlukan adalah besar kerugian yang ditimbulkan atau besar keuntungan yang didapatkan oleh setiap assignee dalam menyelesaikan setiap assignment. Sedangkan tujuan yang ingin dicapai dalam menyelesaikan masalah ini adalah berusaha untuk menjadwalkan setiap assignee pada suatu assignment sedemikian rupa sehingga kerugian yang ditimbulkan minimal atau keuntungan yang didapatkan maksimal. Yang dimaksud dengan kerugian dalam masalah ini adalah biaya dan waktu, sedangkan yang termasuk dalam keuntungan diantaranya adalah pendapatan, laba dan nilai kemenangan. Dari sini terlihat bahwa secara garis besar ada dua jenis masalah assignment, yaitu : 1. Masalah minimasi 2. Masalah maksimisasi Berikut ini adalah beberapa contoh kegiatan yang termasuk dalam masalah assignment.

PENEMPATAN KARYAWAN PADA SUATU POSISI JABATAN DI PERUSAHAAN. Suatu perusahaan mempunyai empat posisi jabatan yang kosong. Sang Direktur telah mempunyai empat kandidat yang akan ditempatkan pada keempat posisi jabatan tersebut, tetapi sang Direktur belum bisa memutuskan kandidat mana yang akan ditempatkan pada jabatan yang mana. Dengan menggunakan data kelebihan/kekurangan dari setiap kandidat, sang Direktur dapat menggunakan metode penugasan untuk membantunya membuat keputusan.

PEMBAGIAN WILAYAH TUGAS SALESMAN Seorang Manajer pemasaran akan menempatkan beberapa salesmannya di beberapa wilayah pemasaran produknya. Berdasarkan data prakiraan keuntungan yang akan diberikan oleh setiap salesman di setiap wilayah pemasaran, sang manajer dapat menjadwalkan penugasan salesman tersebut dengan bantuan metode penugasan.

1

RO - Masalah Penugasan (Assignment Problem) PEMBAGIAN TUGAS DALAM SUATU TIM RENANG ESTAFET Seorang pelatih renang mengasuh empat perenang yang akan diturunkan di nomor estafet gaya ganti. Dikarenakan keempat perenang yanga ada di bawah asuhannya menguasai dengan baik setiap gaya, maka pelayih dapat menggunakan bantuan metode penugasan untuk membantunya membuat keputusan penempatan perenang, berdasarkan pada data waktu terbaik masing-masing perenang di setiap gaya. Untuk menyelesaikan masalah penugasan, biasa digunakan metode Hungarian. Metode ini merupakan modifikasi dari metode transportasi yang telah dibahas sebelumnya. Untuk dapat diselesaikan dengan menggunakan metode Hungarian ini, maka data dari masalah tersebut harus dipresentasikan dalam bentuk tabel penugasan seperti yang terlihat pada Tabel 1.

Tabel 1 Tabulasi Masalah Penugasan Assignment 1

2

…..

n

1

A11

A12

…..

A1n

2

A21

A22

…..

A2n

Assignee

…

…

…

…

… n

An1

An2

…..

Ann

Pada Tabel 1, A11, A12 hingga Ann mempresentasikan data keuntungan yang diperoleh atau kerugian yang ditimbulkan oleh setiap assignee dalam menyelesaikan suatu assignment. Misalnya, A11 adalah data yang mempresentasikan keuntungan yang diperoleh atau kerugian yang ditimbulkan oleh assignee 1 dalam menyelesaikan keuntungan yang diperoleh atau kerugian yang ditimbulkan oleh assignee 1 dalam menyelesaikan assignment 1. Pada bagian terdahulu telah disebutkan bahwa pada masalah penugasan disyaratkan suatu penugasan satu-satu, sehingga jumlah assignee dan assignmentnya harus sama. Bila pada suatu masalah ditemui adanya jumlah assignee dan assignment yang berbeda, maka perlu ditambahkan suatu assignee/assignment dummy untuk menyamakan jumlahnya. Penambahan baris/kolom dummy ini merupakan langkah awal dalam pembuatan tabel penugasan. Setelah data terpresentasi dalam bentuk tabel penugasan, maka kita dapat langsung menyelesaikannya dengan menggunakan metode Hungarian. Dalam penyelesaiannya, masalah penugasan ini terbagai dua yaitu masalah maksimisi dan masalah minimisasi. Pada masalah

2

RO - Masalah Penugasan (Assignment Problem) maksimasi, data yang tersaji adalah data keuntungan, dan pada masalah minimisasi data yang tersaji adalah data kerugian.

MASALAH MINIMISASI Langkah-langkah penyelesaian dengan metode Hungarian untuk masalah minimisasi adalah sebagai berikut : 1. Ditentukan nilai terkecil dari setiap baris, lalu mengurangkan semua nilai dalam baris tersebut dengan nilai terkecilnya. 2. Diperiksa apakah setiap kolom telah mempunyai nilai nol. Bila sudah dilanjutkan kelangkah 3; bila belum, dilakukan penentuan nilai terkecil dari setiap kolom yang belum mempunyai nilai nol, kemudian setiap nilai pada kolom tersebut dikurangkan dengan nilai terkecilnya. 3. Ditentukan apakah terdapat n elemen nol dimanan tidak ada 2 nilai nol yang berada pada baris/kolom yang sama, dimana n adalah jumlah kolom/baris. Jika ada, maka tabel telah optimal; jika tidak dilanjutkan ke langkah 4. 4. Dilakukan penutupan semua nilai nol dengan menggunakan garis vertikal/horizontal seminimal mungkin. 5. Ditentukan nilai terkecil dari nila-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 ke langkah 3.

Untuk lebih jelasnya perhatikan contoh penyelesaian masalah berikut ini. Contoh : Seorang pelatih renang ingin membentuk tim renang yang tangguh untuk terjun di nomor 400m estafet gaya ganti pada suatu pertandingan tingkat nasional. Ada empat perenang dibawah asuhannya, yang merupakan perenang terbaiknya, yang menguasai dengan baik keempat gaya yang dipertandingkan. Pelatih ingin melakukan penugasan satu perenang pada satu gaya berdasarkan data waktu terbaik mereka untuk tiap gaya nomor 100 meter yang tersaji pada Tabel 2 dengan bantuan metoda Hungarian.

3

RO - Masalah Penugasan (Assignment Problem) Tabel 2 Data Perolehan Waktu (dalam detik) Perenang Budi

Giri

Koko

Fajar

Kupu-kupu

52.4

48.3

55.6

49.5

Dada

55.4

58.2

59.1

57.3

Punggung

62.7

62.5

60.9

63.2

Bebas

47.7

49.1

53.5

52.1

Gaya

Penyelesaian : Pada suatu pertandingan renang selalu waktu tercepat yang mungkin dapat dilakukan, sehingga masalah ini masuk ke dalam masalah minimisasi. Berdasarkan data yang tersaji pada Tabel 2, maka langkah pertama yang dilakukan adalah menentukan nilai terkecil dari setiap baris. Hasil penentuan terkecil tersebut adalah sebagai berikut : - baris I

: 48.3

- baris II

: 55.4

- baris III

: 60.9

- baris IV

: 47.7

sehingga setiap nilai pada baris I dikurangkan dengan 48.3, setiap nilai pada baris II dikurangkan dengan 55.4, setiap nilai pada baris III dikurangkan dengan 60.9 dan setiap nilai pada bris IV dikurangkan dengan 47.7. Hasil perhitungan langkah pertama ini dapat dilihat pada Tabel 3. Tabel 3 Hasil Perbaikan Pertama Perenang Budi

Giri

Koko

Fajar

Kupu-kupu

4.1

0

7.3

1.2

Dada

0

2.8

3.7

1.9

Punggung

1.8

1.6

0

2.3

Bebas

0

1.4

5.8

4.4

Gaya

4

RO - Masalah Penugasan (Assignment Problem) Selanjutnya, dilakukan pemeriksaan apakah setiap kolom telah mempunyai nilai nol. Ternyata pada kolom IV belum terdapat nilai nol, sehingga perlu dilakukan penentuan nilai terkecil dari kolom ini, yaitu 1.2. Kemudian setiap nilai pada kolom IV dikurangkan dengan 1.2, sehingga diperoleh nilai seperti yang tersaji pada Tabel 4. Tabel 4 Hasil Perbaikan Kedua Perenang Budi

Giri

Koko

Fajar

Kupu-kupu

4.1

0

7.3

0

Dada

0

2.8

3.7

0.7

Punggung

1.8

1.6

0

1.1

Bebas

0

1.4

5.8

3.2

Gaya

Langkah berikutnya adalah memeriksa apakah terdapat suatu penugasan yang layak. Bila diperlihatkan akan ditemui sejumlah 5 nilai nol pada Tabel 4. Tetapi dari kelima nilai nol tersebut, tidak ada empat nilai nol yang keempat-empatnya terdapat pada baris dan kolom yang berbeda. Misalnya kita ambil nilai nol pada kotak (1.2), (2.1), (3.3) dan (4.1); kita masih menemukan ada dua nilai nol yang berada pada kolom yang sama yaitu nilai nol pada kotak (2.1) dan (4.1). Hal yang sama juga akan terjadi pada kemugkinan-kemungkinan yang lainnya. Ini menandakan bahwa tabel belum optimal, sehingga perlu dilakukan langkah-langkah selanjutnya guna mendapatkan tabel yang optimal. Langkah selanjutnya adalah menutup seluruh nilai nol dengan garis vertikal dan horizontal seminimal mungkin, seperti yang terlihat pada Tabel 5. Tabel 5 Hasil Perbaikan Ketiga Perenang Budi

Giri

Koko

Fajar

Kupu-kupu

4.1

0

7.3

0

Dada

0

2.8

3.7

0.7

Punggung

1.8

1.6

0

1.1

Bebas

0

1.4

5.8

3.2

Gaya

5

Modul 14. Riset Operasional. Masalah Penugasan Pada Tabel 5 terlihat bahwa jumlah garis yang menutup nilai nol ada tiga, dan ini merupakan jumlah yang minimal, karena tidak mungkin menutup semua nilai nol dengan hanya dua garis vertikal/horizontal. Setelah seluruh nilai nol tertutup oleh garis vertikal/horizontal, maka dilakukan penentuan nilai terkecil dari nilai-nilai yang tidak tertutup garis. Bila diperhatikan Tabel 5, maka nilai terkecil yang dimaksud adalah 0.7. Selanjutnya kita kurangkan setiap nilai yang tidak tertutup garis dengan 0.7, dan kita tambahkan setiap nilai yang terttutup oleh dua garis dengan 0.7. Langkah ini memungkinkan nilai seperti yang tersaji pada Tabel 6.

Tabel 6 Tabel Akhir (Optimal) Perenang Budi

Giri

Koko

Fajar

Kupu-kupu

4.8

0

7.3

0

Dada

0

2.1

3.0

0

Punggung

2.5

1.6

0

1.1

Bebas

0

2.1

6.5

3.9

Gaya

Berikutnya kembali dilakukan pemriksaan apakah telah terdapat suatu penugasan yang layak yang memberikan solusi optimal. Pada Tabel 6 terlihat bahwa terdapat sejumlah empat nilai nol yang keempat-empatnya berada pada baris dan kolom yang berbeda, sehingga dapat dikatakan bahwa tabel telah optimal. Dengan telah diperolehnya tabel yang optimal, maka kita tinggal melakukan penugasan assignment ke assignee. Penugasan ini diberikan kepada pasangan assignee-assignment pada kotak yang bernilai nol pada tabel optimal. Penentuan penugasan sebaiknya dimulai dari baris yang hanya mengandung satu nilai nol. Pada Tabel 6, baris yang dimaksud adalah baris ke-3 dan ke-4. Hal ini berarti gaya punggung ditugaskan kepada Koko, dan gaya bebas kepada Budi. Kemudian untuk baris ke-2, karena Budi telah mendapatkan tugas di gaya bebas, maka gaya dada diberikan kepada Fajar, sedangkan gaya kupu-kupu, pada baris ke-1, diberikan kepada Giri. Berdasarkan pada penugasan tersebut, maka perolehan waktu yang diperkirakan pada nomor 400 estafet gaya ganti adalah 48.3 + 57.3 + 60.9 + 47.7 = 214.2 detik.

6

Modul 14. Riset Operasional. Masalah Penugasan MASALAH MAKSIMISASI Langkah-langkah penyelesaian dengan metoda Hungarian untuk masalah maksimisasi adalah sebagai berikut : 1. Ditentukan nilai terbesar dari setiap baris, lalu mengurangkan semua nilai pada setiap baris dari nilai terbesarnya. 2. Diperiksa apakah setiap kolom telah mempunyai nilai nol. Bila sudah dilanjutkan ke langkah 3; bila belum, dilakukan penentuan nilai terkecil dari setiap kolom yang belum mempunyai nilai nol, kemudian setiap nilai pada kolom tersebut dikurangkan dari nilai terkecilnya. 3. Ditentukan apakah terdapat n elemen nol dimana tidak ada 2 nilai nol yang berada pada baris/kolom yang sama, dimana n adalah jumlah kolom/baris. Jika ada, maka tabel telah optimal; jika tidak dilanjutkan ke langkah 4. 4. Dilakukan penutupan semua nilai nol dengan menggunakan garis vertikal/horizontal seminimal mungkin. 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 ke langkah 3.

Untuk lebih jelasnya, perhatikan contoh penyelesaian masalah berikut ini. Contoh : Seorang manajer pemasaran ingin menempatkan empat orang salesmannya di empat daerah pemasaran produknya. Penempatan salesman tersebut didasarkan pada perolehan nilai keuntungan yang diperkirakan akan diperoleh oleh setiap salesman di setiap daerah pemasaran berdasarkan prestasi kerja mereka saat ini dan pengenalan terhadap masing-masing daerah pemasaran tersebut. Bila data perolehan keuntungan dari setiap salesman di setiap daerah pemasaran seperti yang tersaji pada Tabel 7, tentukan penugasan salesman yang harus dibuat oleh sang manajer agar keuntungan yang diperoleh maksimal.

7

Modul 14. Riset Operasional. Masalah Penugasan Tabel 7. Data Perolehan Keuntungan D. pem. 1

D. pem. 2

D. pem. 3

D. pem. 4

Sal. 1 1000

900

1100

900

Sal. 2 1100

1000

950

950

Sal. 3 1050

950

900

1050

Sal. 4 1150

1000

950

1000

Penyelesaian : Tujuan yang ingin dicapai dalam penugasan salesman diatas adalah diperolehnya keuntungan yang maksimal, sehingga masalah tergolong dalam masalah maksimisasi. Langkah pertama untuk menyelesaikan masalah ini dengan menggunakan metoda Hungarian adalah menentukan nilai terbesar dari setiap baris, dengan hasil sebagai berikut : - baris I

: 1100

- baris II

: 1100

- baris III

: 1050

- baris IV

: 1150

hal ini berarti nilai-nilai keuntungan pada baris I dikurangkan dari 1100, baris II dikurangkan dari 1100, baris III dikurangkan dari 1050 dan baris IV dikurangkan dari 1150. Hasil perhitungan langkah pertama ini dapat dilihat pada Tabel. 6.8.

Tabel 8 Hasil Perbaikan Pertama D. pem. 1

D. pem. 2

D. pem. 3

D. pem. 4

Salesman 1

100

200

0

200

Salesman 2

0

100

150

150

Salesman 3

0

100

150

0

Salesman 4

0

150

200

150

Selanjutnya diperiksa apakah setiap kolom telah mempunyai nilai nol. Ternyata pada Tabel 8 terlihat bahwa kolom II belum mempunyai nilai nol, sehingga perlu ditentukan nilai terkecil dari kolom tersebut, yaitu 100. setiap nilai pada kolom II dikurangkan dari 100, sehingga diperoleh hasil seperti pada Tabel 9.

8

Modul 14. Riset Operasional. Masalah Penugasan Tabel 9 Tabel Akhir (Optimal) D. pem. 1

D. pem. 2

D. pem. 3

D. pem. 4

Salesman 1

100

100

0

200

Salesman 2

0

100

150

150

Salesman 3

0

0

150

0

Salesman 4

0

50

200

150

Sekarang dilihat apakah ada empat nilai nol pada Tabel 9 dimana keempat-empatnya berada pada baris dan kolom yang berbeda. Ternyata ada, sehingga Tabel 9 dapat dinyatakan sebagai tabel optimal. Sebagai langkah terakhir adalah penentuan penugasan salesman ke aderah pemasaran berdasarkan pada nilai-nilai nol tadi. Dimulai dengan baris dengan jumlah nilai nol satu, yaitu baris I dan IV, yang berarti salesman 1 ditempatkan di daerah pemasaran 3, salesman 4 ditempatkan di daerah pemasaran 1. untuk baris II terdapat dua nilai nol, tetapi karena daerah pemasaran 1 telah diberikan kepada salesman 4, maka salesman 2 ditempatkan di daerah pemasaran 2; dan yang terakhir, salesman 3 ditempatkan di daerah pemasaran 4. Berdasarkan penugasan yang dibuat diatas, maka nilai keuntungan yang akan diperoleh adalah sebesar 1100 + 1000 + 1050 + 1150 = 4300.

PENAMBAHAN DUMMY DAN PENGGUNAAN BIG M Kolom/baris dummy ditambahkan bila jumlah assignee tidak sama dengan assignment, atau terkadang disebut sebagai masalah tak seimbang. Pada kolom/baris dummy ini diberikan nilai keuntungan/kerugian sebesar nol. Sedangkan untuk suatu hubungan assignee dan assignment yang tidak mungkin (boleh) terjadi, untuk hubungan keduanya diberikan nilai keuntungan sebesar –M atau nilai kerugian sebesar M. Nilai M ini mewakili bilangan yang sangat besar

bila

dibandingkan

dengan

bilangan-bilangan

lain

yang

menunjukkan

nilai

keuntungan/kerugian lainnya. –M berarti suatu keuntungan yang sangat kecil dan M berarti kerugian yang sangat besar.

9