ASSIGNMENT MODEL MATAKULIAH RISET OPERASIONAL Pertemuan Ke-12 Riani Lubis JurusanTeknik Informatika Universitas Komputer Indonesia
1
Masalah Penugasan g Salah satu metode yang digunakan untuk Penugasan adalah
2
Metode M t d Hungarian. H i Pada metode Hungarian, jumlah sumber-sumber yang ditugaskan h harus sama persis i dengan d j l h tugas yang akan jumlah k diselesaikan. di l ik Setiap sumber harus ditugaskan hanya untuk satu tugas. Jadi masalah penugasan akan mencakup sejumlah m sumber yang mempunyai n tugas/tujuan (satu sumber untuk satu tujuan). Diasumsikan m = n, sehingga ada n! (n faktorial) kemungkinan. Masalah ini dapat p dijelaskan j dengan g mudah dalam bentuk matriks segi empat, dimana baris-barisnya menunjukkan sumber-sumber y menunjukkan tugas-tugas/tujuan-tujuan. g g dan kolom-kolomnya Sumber : pekerja Tujuan/Tugas : pekerjaan, mesin mesin-mesin mesin
Persoalan e soa a pe penugasan ugasa melibatkan e at a pe penugasan ugasa karyawan a ya a kee te tempat pat
tugas, penjualan ke daerah, penawaran kontrak, atau fungsifungsi di pabrik. pabrik Dalam menggunakan metode penugasan, pihak manajemen mencarii rute t penugasan yang akan k mengotpimumkan t i k tujuan t j tertentu. Jadi masalah penugasan menyangkut penempatan para pekerja pada bidang yang tersedia agar biaya yang ditanggung dapat diminimumkan. Pada model p penugasan, g , jjumlah ppasokan ppada setiapp sumber dan jumlah permintaan pada setiap tujuan adalah satu. Artinya setiap pekerja hanya menangani satu pekerjaan dan sebaliknya setiap pekerjaan hanya ditangani satu pekerja. 3
Tabel Persoalan Penugasan
4
Dimana, Xij : unit alokasi dari sumber i ke tujuan j (hanya bernilai 1 atau 0) Cij : pa parameter a ete aalokasi o as dari a su sumber be i kee tujua tujuan j Dalam hal ini berlaku : 1. Xi1 + Xi2 + … + Xin = 1 untuk i = 1,2,…,m. Artinya bahwa pada d tiap ti i hanya h ada d satu t Xij yang bernilai b il i 1 sedangkan d k yang lainnya bernilai 0. 2 X1j + X2j + … + Xmj = 1 untuk 2. k i = 1,2,…,n. 12 A i bahwa Artinya bh pada tiap j hanya ada satu Xij yang bernilai 1 sedangkan yang lainnya bernilai 0. 0 3. Nilai alokasi dari sumber ke tujuan sangat bergantung kepada nilai il i Cij dan d Xij, Xij namun karena k Xij hanya h b il i 1 atau bernilai t 0 maka nilai alokasi tersebut sangat dipengaruhi oleh Cij. 5
Perumusan Model Penugasan g Maksimum/ Minimum :
Pembatas :
6
Masalah Minimasi Langkah-langkahnya : 1 Melakukan 1. M l k k pengurangan baris b i dengan d cara : a. Memilih biaya terkecil setiap baris b. Kurangkan semua biaya dengan biaya terkecil setiap baris gg menghasilkan g reduced cost matrix (matrik biaya yangg sehingga telah dikurangi) 2. Melakukan pengurangan kolom Berdasarkan hasil tabel langkah 1, pilih biaya terkecil setiap kolom untuk mengurangi seluruh biaya bia a dalam kolom-kolom kolom kolom tersebut, sehingga menghasilkan matrix total opportunity cost. Jik langkah Jika l k h 1 telah t l h menghasilkan h ilk paling li sedikit dikit satu t nilai il i noll pada setiap kolom, maka langkah 2 dapat dihilangkan. 7
3. Membentuk penugasan optimum
Prosedur praktis untuk melakukan tes optimalisasi adalah dengan j minimum ggaris horisontal dan/atau vertikal menarik sejumlah untuk meliputi seluruh elemen bernilai nol dalam total pp y cost matrix. JJika jjumlah ggaris sama dengan g jjumlah opportunity baris/kolom maka penugasan telah optimal. Jika tidak maka harus direvisi 4. Melakukan revisi tabel a. Untuk U k merevisi totall opportunity cost, pilih l h angka k terkecil k l yang tidak terliput (dilewati) garis. b. Kurangkan angka yang tidak dilewati garis dengan angka terkecil c. Tambahkan angka g yyangg terdapat p ppada ppersilangan g ggaris dengan g angka terkecil d Kembali ke langkah 3 d. 8
Contoh : Sebuah perusahaan mempunyai 4 jenis pekerjaan untuk diselesaikan oleh 4 karyawan. karyawan Biaya penugasan tiap karyawan untuk tiap jenis pekerjaan adalah berbeda. Setiap karyawan mempunyai tingkat keterampilan, pengalaman kerja, kerja dan latar belakang pendidikan yang berbeda. berbeda Sehingga biaya penyelesaian pekerjaan yang sama oleh para karyawan yang berlainan juga berbeda (ditunjukkan dalam tabel biaya di bawah). bawah)
9
10
11
12
Berikut e ut ta tabel e pe penugasannya ugasa ya :
13
Jumlah Sumber Jumlah Tujuan Bila jumlah tujuan/pekerjaan lebih besar dari jumlah
sumber/karyawan, b k maka k harus h d ditambahkan b hk tujuan/karyawan k semu (dummy worker). Biaya semu sama dengan nol karena tidak akan terjadi biaya bila suatu pekerjaan ditugaskan ke karyawan semu. Bila jumlah sumber/karyawan lebih banyak daripada tujuan/ ppekerjaan, j , maka ditambahkan ppekerjaan j semu ((dummyy jjob). ) Prosedur penyelesaian sama dengan langkah-langkah sebelumnya.
14
Masalah Maksimasi Dalam l masalah l h maksimasi, k elemen-elemen l l matriks k menunjukkan kk tingkat k
keuntungan. Efektivitas pelaksanaan tugas oleh karyawan diukur dengan jumlah kontribusi keuntungan. Langkah-langkahnya : 1. Seluruh elemen dalam tiap p baris dikurangi g dengan g nilai maksimum dalam baris yang sama., sehingga menghasilkan Matrix Opportunity Loss. 2. Meminimumkan opportunity pp y loss dengan g cara mengurangi g g seluruh elemen dalam setiap kolom (belum ada nol) dengan elemen terkecil dari kolom tersebut, sehingga gg diperoleh p MatriksTotal Opportunity pp y Loss. 3. Menarik sejumlah garis horisontal dan/atau vertikal untuk meliputi seluruh elemen bernilai nol dalam total opportunity pp y loss matrix. JJika jumlah garis sama dengan jumlah baris/kolom maka penugasan telah p Jika tidak maka harus direvisi. optimal. 15 4. Merevisi matriks
Contoh : Tabel Keuntungan :
16
17
18
19
