Manajemen Sains Model Penugasan (Assignment Modelling)
Eko Prasetyo Teknik Informatika Univ. Muhammadiyah Gresik 2011
Model Penugasan
2
Biasanya diterapkan pada suatu jaringan guna mendapatkan nilai optimal dari jaringan tersebut.
Pemodelan ini merupakan pemodelan khusus dari model program linear.
Prinsip “The right man on the right pleased”
Gambaran dimana setiap subyek hanya ditugaskan pada satu area tujuan saja, atau setiap area tujuan hanya dikuasai satu subyek saja.
Parameter yang akan digunakan dalam menyelaraskan penentuan solusi dan tujuannya, apakah memaksimumkan atau meminimumkan.
Teknik Informatika UMG 2011
Metode mendapatkan solusi optimal : Hungarian
3
1.
Menyusun data dalam bentuk bujur sangkar. Maksudnya, jumlah baris harus sama dengan jumlah kolom. Jika yang dicari adalah nilai maksimal, maka matrik data dikalikan dengan (–1).
2.
Menentukan nilai terkecil dari setiap baris matrik, kemudian unsur-unsur dari setiap baris dikurangi dengan nilai terkecil menurut barisnya.
3.
Menentukan nilai terkecil dari setiap kolom matrik, kemudian unsur-unsur dari setiap kolom dikurangi dengan nilai terkecil menurut kolomnya.
4.
Membuat garis vertikal atau horizontal. Garis yang dibuat harus melintasi unsur nol dan diusahakan seminimal mungkin menggunakan garis.
5.
Menghitung jumlah garis yang melintasi kolom atau baris, jika jumlah garis sama dengan jumlah baris atau kolom maka menuju ke langkah-8.
6.
Menentukan nilai terkecil dari unsur-unsur yang tidak dilintasi garis, kemudian unsurunsur tersebut dikurangkan dengan nilai terkecil tersebut. Akan tetapi, unsur-unsur yang dilintasi dua garis ditambah oleh nilai terkecil tersebut.
7.
Kembali ke langkah-4.
8.
Solusi optimal ditemukan dengan menentukan pasangan penugasan optimal (MPPO) dari model penugasan ditunjukkan oleh unsur nol yang terletak pada baris atau kolom yang ditunjuk.
Teknik Informatika UMG 2011
Metode mendapatkan solusi optimal : Hungarian Menurut langkah 1 di atas, matrik bujur sangkar adalah matrik yang jumlah kolom dan barisnya sama. Cara untuk menjadikan baris dan kolom agar sama adalah dengan menambah nilai 0. Baris > kolom Asal
4
Menjadi
1
26
11
1
1
26
11
1
0
15
8
19
20
15
8
19
20
0
6
81
11
6
6
81
11
6
0
7
1
68
77
7
1
68
77
0
81
79
55
91
81
79
55
91
0
Teknik Informatika UMG 2011
Metode mendapatkan solusi optimal : Hungarian Baris < kolom Asal
Menjadi
1
26
11
1
81 1
26
11
1
81
15
8
19
20
79 15
8
19
20
79
6
81
11
6
55 6
81
11
6
55
7
1
68
77
91
7
1
68
77
91
0
0
0
0
0
Khusus untuk langkah 2 dan langkah 3 bisa dilakukan pertukaran urutan, maksudnya melakukan proses reduksi kolom kemudian reduksi baris atau sebaliknya. Begitu juga dalam membuat garis yang melintasi baris atau kolom yang memiliki nol, karena prinsipnya adalah meminimalisir penarikan garis terhadap nilai nol. 5
Teknik Informatika UMG 2011
Contoh 1 Suatu perusahaan memiliki
empat operator dan empat mesin. Manager perusahaan ingin mengetahui kombinasi keadaan kerja operator dan mesin yang dimilikinya. Manager menganggap seluruh operator layak mengoperasikan seluruh mesin. Maka manager harus tahu: Berapa waktu terpendek yang bisa
dikerjakan oleh keempat operator tersebut? (meminimumkan) Berapa waktu terlama yang bisa dikerjakan oleh keempat operator tersebut? (memaksimumkan) 6
Teknik Informatika UMG 2011
Penyelesaian (1) - Meminimalkan Menentukan nilai
terkecil pada baris Kurangkan baris dengan nilai terkecilnya Menentukan nilai
terkecil pada kolom Kurangkan kolom dengan nilai terkecilnya 7
Teknik Informatika UMG 2011
Penyelesaian (2) Menarik garis pada baris
atau kolom dengan jumlah seminimal mungkin Tentukan nilai terkecil (k) yang berada di luar garis Unsur di luar garis dikurang
1 Unsur dilalui dua garis ditambah 1 Menarik garis pada baris atau kolom
8
Teknik Informatika UMG 2011
Penyelesaian (3) Menentukan pasangan
penugasan optimal : A – 3 5 menit B – 1 11 menit C – 4 9 menit D – 2 7 menit
Mencapai solusi optimal
dengan waktu terpendek = 32 menit
9
Teknik Informatika UMG 2011
Penyelesaian (4) Memaksimalkan Matrik dikalikan
dengan -1 Menentukan nilai terkecil pada baris
10
Teknik Informatika UMG 2011
Penyelesaian (5) Mengurangkan baris
dengan nilai terkecilnya Menentukan nilai terkecil pada kolom Mengurangkan kolom
dengan nilai terkecilnya Menarik garis pada kolom atau baris
11
Teknik Informatika UMG 2011
Penyelesaian (6) Menentukan nilai
terkecil di luar garis Unsur di luar garis
dikurang 5 Unsur dilalui dua garis ditambah 5 Menyesuaikan garis dengan nol
12
Teknik Informatika UMG 2011
Penyelesaian (7) Menentukan pasangan
penugasan optimal Total waktu terlama tidak
ditemukan karena ada satu operator yang tidak fungsional dan ada satu mesin yang tidak digunakan yang disebabkan operator tidak mungkin mengerjakan dua mesin sekaligus. 13
Teknik Informatika UMG 2011
Contoh 2 Sebuah perusahaan
memiliki lima orang sales dan 4 wilayah pemasaran. Seorang manager pemasaran dari perusahaan tersebut ingin mengetahui volume hasil penjualan yang dilakukan oleh karyawannya sehingga bisa diketahui karyawan mana saja yang memiliki kerja optimal. (memaksimumkan)
14
Teknik Informatika UMG 2011
Penyelesaian (1) Menjadikan matrik
menjadi matrik bujur sangkar Mengalikan setiap unsur dengan (-1) Mencari nilai terkecil
dari setiap kolom
15
Teknik Informatika UMG 2011
Penyelesaian (2) Mengurangkan unsur-unsur
kolom dengan nilai terkecilnya Menarik garis yang melintas nilai
nol Menentukan nilai terkecil dari
unsur di luar garis Mengurangkan semua unsur di
luar garis dengan nilai terkecil Menambahkan semua unsur
yang dilalui dua garis dengan nilai terkecil Menyesuaikan garis dengan nol
16
Teknik Informatika UMG 2011
Penyelesaian (3) Solusi optimal telah
ditemukan A – 1 315 B–50 C – 3 516 D – 4 310 E – 4 421
Total =1562 unit
17
Teknik Informatika UMG 2011
Tugas Baca Modul 6 Model Penugasan Kerjakan soal Modul 5 :
Kelompok 1 : 5.3 Kelompok 2 : 5.4 Kelompok 3 : 5.5 Kelompok 4 : 5.6 Kelompok 5 : 5.7
Pengerjaan : Satu kelompok berisi maksimal 9 orang Ditulis tangan pada kertas folio bergaris oleh masing-
masing anggota Dikumpulkan pada pertemuan berikutnya 18
Teknik Informatika UMG 2011