PRESENTASI TUGAS AKHIR KI OPTIMASI PERMASALAHAN PENUGASAN DOKTER MENGGUNAKAN REPRESENTASI GRAF BIPATIT BERBOBOT

PRESENTASI TUGAS AKHIR – KI091391

OPTIMASI PERMASALAHAN PENUGASAN DOKTER MENGGUNAKAN REPRESENTASI GRAF BIPATIT BERBOBOT

Penyusun Tugas Akhir : Laili Rochmah (NRP : 5109 100 707)

Dosen Pembimbing : Ahmad Saikhu, S.Si., M.T. Rully Soelaiman S.Kom., M.Kom. 16 Juli 2013

Tugas Akhir – KI091391

1

.:AGENDA:. Kesimpulan

7. Ujicoba

Data Masukan

1.

6.

2.

5.

Penugasan Dokter pada Rumah Sakit

3.

4.

Proses untuk menentukan dokter yang ditugaskan dengan model Integer programming 16 Juli 2013

• Latar belakang • Permasalahan • Batasan Masalah • Tujuan

Proses untuk menentukan dokter yang memenuhi kondisi dengan model Graf Bipartite


2

.: LATAR BELAKANG :. 1. Pelayanan kesehatan merupakan salah satu bentuk pelayanan yang

paling banyak dibutuhkan masyarakat. Berbagai rumah sakit berupaya memberikan pelayanan yang terbaik bagi pasien. 2. Perbaikan terhadap mutu rumah sakit layanan medis sangat dibutuhkan. Salah satunya layanan panggilan dokter bagi masyarakat yang membutuhkan secara real time. 3. Sehingga rumah sakit membutuhkan struktur pengambilan keputusan untuk penugasan dokter agar dapat menanggulangi situasi gawat darurat korban secepat mungkin. 4. Model Graf Bipartite (GB) dan Integer Programming (IP) diharapkan mampu mengoptimalkan hasil penugasan dokter yang tepat serta mampu mengatasi semua masalah pengambilan keputusan yang berkaitan dengan penugasan dokter. 16 Juli 2013


3

.: PERMASALAHAN:. Permasalahan yang diangkat dalam tugas akhir ini adalah: 1. Bagaimana model GB dan IP dalam struktur pengambilan keputusan dapat menghasilkan solusi yang optimal untuk penugasan dokter? 2. Bagaimana mengimplementasikan model GB dan IP dalam struktur pengambilan keputusan untuk penugasan dokter? 3. Bagaimana pengaruh jumlah kemungkinan dokter yang memenuhi kondisi terhadap performa dari model GB dan IP? 4. Bagaimana uji coba terhadap implementasi dari contoh percobaan yang dilakukan?

16 Juli 2013


4

.: BATASAN MASALAH:. 1. Model dalam struktur pengambilan keputusan yang 2. 3. 4. 5. 6. 7.

diimplementasikan hanya untuk model GB dan IP. Permasalahan penugasan dokter terjadi dalam satu waktu. Penugasan untuk tiap dokter ditugaskan untuk satu kondisi. Penugasan untuk tiap kondisi ditugaskan untuk satu dokter. Data kondisi dalam bentuk postfix. Data pertama terdiri dari 7 dokter dan 5 kondisi karena data tersebut dapat mewakili permasalahan penugasan dokter. Data diambil dari paper karya Yuqing Sun [1]. Data kedua terdiri dari 40 dokter dan 18 kondisi yang didalamnya dilakukan perubahan tertentu dengan harapan dapat memperoleh hasil yang diinginkan. Data diambil dari paper karya Mehran Hojati [11].

16 Juli 2013


5

.: TUJUAN:. 1. Melakukan verifikasi solusi optimal dalam penugasan dokter berdasarkan implementasi model yang diajukan. 2. Mengimplementasikan model Graf Bipartite (GB) dan Integer Programming (IP) pada permasalahan penugasan dokter. 3. Melakukan uji coba terhadap implementasi dari contoh percobaan yang dilakukan.

16 Juli 2013


6

.: PENUGASAN DOKTER PADA RUMAH SAKIT:. 1. Penugasan untuk dokter dimana dokter akan diberi tugas untuk 2. 3. 4. 5. 6.

pergi ke suatu tempat untuk melakukan perawatan medis. Kualifikasi dokter yang ditugaskan disebut kondisi. Kondisi berisi keahlian dokter yang dibutuhkan. Satu dokter bisa memiliki banyak keahlian. Contoh: Dokter A memiliki keahlian dokter kulit dan kandungan. Satu kondisi bisa berisi banyak keahlian dan dihubungkan dengan ‘dan’ ‘atau’. Contoh: suatu daerah membutuhkan dokter jantung dan bedah Terdapat jarak yang menghubungkan dokter dan lokasi kondisi. Keputusan-keputusan yang terkait dengan masalah penugasan dokter antara lain dokter siapa yang memenuhi kondisi dan dokter siapa yang ditugaskan.

16 Juli 2013


7

.:ILUSTRASI PENUGASAN DOKTER(1) :. Model penugasan dokter yang digunakan pada tugas akhir ini meliputi: • 7 dokter (D1 sampai D7) • 5 kondisi (C1 sampai C5)

16 Juli 2013


8

.:ILUSTRASI PENUGASAN DOKTER(2) :. Gambar konfigurasi penugasan dokter yang belum dilakukan optimasi

16 Juli 2013


9

.: PROSES UNTUK MENENTUKAN DOKTER YANG MEMENUHI KONDISI DENGAN MODEL GB:. • Model GB yang digunakan adalah: 1. 𝑉1 himpunan node yang mewakili keahlian. 2. 𝑉2

himpunan node yang mewakili dokter

3. 𝐸

himpunan edge yang menghubungkan node di 𝑉1 dengan node di 𝑉2 atau menghubungkan sebuah keahlian dengan seorang dokter yang cocok.

16 Juli 2013


10

.: PROSES UNTUK MENENTUKAN DOKTER YANG DITUGASKAN DENGAN MODEL IP :.

• Variabel keputusan Variabel keputusan pada model optimasi ini meliputi dua tipe: 1. Variabel kontinyu (hasil tidak harus integer) 2. Variabel binari (nilai 1 atau 0)

16 Juli 2013


11

.: PROSES UNTUK MENENTUKAN DOKTER YANG DITUGASKAN DENGAN MODEL IP :. • Variabel Kontinyu

Dij

Jarak dokter i ke lokasi kondisi j Menunjukkan jarak dari masing-masing dokter i dalam ke kondisi j

• Variabel Binari

X ij

16 Juli 2013

Bernilai 1 jika dokter i ditugaskan ke kondisi j, 0 jika selainnya


12


• Tujuan : Meminimalkan

 D .X ij

ij

i, j

• Batasan penugasan 1.

X

2.

X

ij

1

ij

1

i

j

16 Juli 2013


13



 D .X ij

ij

i, j

Jarak dokter Jarak ini menunjukkan bahwa jarak dokter dengan lokasi kondisi

Dij

= Jarak dokter i ke lokasi kondisi j

= Dokter i ditugaskan ke kondisi j i = Dokter J = Kondisi

X ij


X

2.

X

ij

1

ij

1

i

j

16 Juli 2013


14



 D .X ij

ij

i, j


X

2.

X

ij

1

tiap-tiap dokter i ditugaskan dengan tepat satu kondisi j

ij

1

tiap-tiap kondisi j ditugaskan dengan tepat satu dokter i

i

j

16 Juli 2013


15

.: DATA MASUKAN:. 1. 2. 3. 4.

Data Data Data Data

16 Juli 2013

keahlian dokter dan keahliannya kondisi jarak dokter ke lokasi kondisi


16

UJI COBA 1. Model GB diimplementasikan pada sistem operasi windows

dengan aplikasi Dev C++ 2. Model IP diimplementasikan pada sistem operasi windows dengan aplikasi MATLAB dibantu solver TOMLAB 3. Uji coba dilakukan untuk menyelesaikan permasalahan yang berbeda o Permasalahan 1 o Permasalahan 2

16 Juli 2013


17

.:KESIMPULAN(1):. 1. Model GB dapat memberikan hasil yang akurat berupa dokter

yang memenuhi kondisi. Hal ini dapat membantu pihak rumah sakit dalam mengambil keputusan perihal pemilihan dokter yang memenuhi kondisi secara tepat. 2. Model IP dapat menghasilkan suatu hasil optimal berupa total jarak dokter dengan lokasi kondisi. Hal ini dapat membantu rumah sakit dalam mengambil keputusan yang optimal perihal pemilihan kombinasi dokter yang ditugaskan. 3. Dalam kaitannya dengan struktur pengambilan keputusan hasil dari model IP sangatlah bergantung pada faktor dokter yang memenuhi kondisi. Di mana faktor dokter yang memenuhi kondisi ditentukan dengan model GB. 16 Juli 2013


18

.:KESIMPULAN(2):. 4. Jumlah kemungkinan dokter yang memenuhi kondisi tidak

berpengaruh secara signifikan terhadap performa dari model GB dan IP.

16 Juli 2013


19

.:DAFTAR PUSTAKA (1):. 1) Yuqing Sun, Dickson K.W. Chiu, Bin Gong, Xiangxu Meng, and Peng

2) 3) 4) 5)

Zhang, "Scheduling mobile collaborating workforce for multiple urgent events," Journal of Network and Computer Applications, pp. 156–163, 2012. Frederick S Hillier and Gerald J Lieberman, Introduction to Operations Research,Seventh Edition. New York: Thomas Casson, 2001. Hamdy A Tamha, Operations Research an Introduction Eight Edition. London: Pearson Education, Inc, 2007. K., Goran, A.O.,Edvall, M.M. Holmstrom, User's Guide For Tomlab 5.9, Tomlab Optimization., 2007. Kenneth H. Rosen, Discrete Mathematics and Its Applications,Sixth Edition. New York: McGraw-Hill, 2007.

16 Juli 2013


20

.:DAFTAR PUSTAKA (2):. 6) Thomas H. Cormen, Introduction to Algorithms, Second Edition.

London: The MIT Press, 2001. 7) Richard Johnsonbaugh, Discrete Mathematics. New Jersey: Prentice Hall Inc, 1997. 8) Yuqing Sun and Dickson K.W., "Context-Aware Scheduling of Workforce for Multiple Urgent Events," 2010. 9) Robert Sedgewick and Kevin Wayne, Algorithms,Four Edition. Boston: Pearson Education, Inc, 2011. 10) Van Bang Le, "Bipartite-perfect graphs," Discrete Applied Mathematics , pp. 581 – 599, 2003. 11) Mehran Hojati, "An Integer Linear Programming-Based Heuristic For Weekly Scheduling of Fast Food Restaurant Employees," Business, 2009. 16 Juli 2013


21

.:DAFTAR PUSTAKA (3):. 12) Eddy Herjanto, Managemen Operasi Edisi Ketiga. Jakarta: PT.

Gramedia Widiasarana Indonesia, 2007. 13) Anders O. Goran and Marcus M. Edvall, TOmlab Instalation Guide., 2009. 14) Rainer E.Burkard, "Selected topics on assignment problems," Discrete Applied Mathematics , pp. 257 – 302, 2002. 15) P. K. De and Bharti Yadav, "An Algorithm to Solve Multi-Objective Assignment Problem Using Interactive Fuzzy Goal Programming Approach," Math. Sciences, pp. 1651 - 1662, 2011. 16) S.R. Agnihothri and P.F. Taylor, "Stafﬁng a centralized appointment scheduling," Interfaces, pp. 1-11, 1991.

16 Juli 2013


22

TERIMA KASIH

16 Juli 2013


23

.:Permasalahan 1:. Pada permasalahan ini, akan dilakukan optimasi penugasan dokter yang menunjukkan semua keputusan tentang dokter yang memenuhi kondisi dan dokter yang ditugaskan. Data percobaan yang dilakukan meliputi: •

8 macam keahlian

•

7 dokter (D1 sampai D7)

•

5 kondisi (C1 sampai C5)

•

jarak 7 dokter ke 5 lokasi kondisi

16 Juli 2013


24

.:Permasalahan 1:. • Proses untuk menentukan dokter yang memenuhi kondisi dengan model GB 1. 2.

inisialisasi data keahlian dan dokter direpresentasikan sebagai graf

bipartite 3.

dokter dikelompokkan berdasarkan keahliannya menggunakan algortima

Ford Fulkerson 4.

5.

dokter yang memenuhi kondisi ditentukan menggunakan operasi himpunan union dan intersection jarak baru ditentukan

16 Juli 2013


25



   

Data Data Data Data

bipartite 3.

4.

5.


8 keahlian 7 dokter dan keahliannya 5 kondisi jarak Tabel data keahlian

No 1

Keahlian Bedah

2

Jantung

3

Kandungan

Ford Fulkerson

4

Kulit

dokter yang memenuhi kondisi ditentukan menggunakan operasi himpunan union dan intersection

5

Koordinator

6

Asisten

7

DokterUtama

jarak baru ditentukan

8

PembantuDokter

16 Juli 2013


26



bipartite 3.


Ford Fulkerson 4.

5.


16 Juli 2013

   

Data Data Data Data

8 keahlian 7 dokter dan keahliannya 5 kondisi jarak

Tabel data dokter dan keahliannya

Dktr D1

Keahlian Jantung, bedah, pembantu dokter

D2

D3

Kulit, kandungan, asisten dokter utama Kandungan, bedah, dokter utama

D4

Jantung, pembantu dokter

D5

Jantung, kulit, dokter utama

D6

Jantung, kandungan, koord. dokter utama Kandungan, bedah, pembantu dokter

D7 Tugas Akhir – KI091391

27



bipartite 3.


Ford Fulkerson 4.

5.


16 Juli 2013

   

Data Data Data Data


Tabel data kondisi

KonKeahlian yang dibutuhkan disi C1 Jantung dan Kulit C2 Kandungan atau (Bedah dan DokterUtama ) C3 (Bedah dan DokterUtama ) atau (Kandungan dan Asisten) C4 Jantung dan DokterUtama C5 Kandungan


28



bipartite 3.

   

Data Data Data Data

Tabel data jarak

Dokter


Ford Fulkerson 4.

5.


16 Juli 2013



D1 D2 D3 D4 D5 D6 D7

C1 10 12 24 2 3 12 12

Kondisi C2 C3 C4 12 14 5 40 6 9 2 14 10 12 15 9 14 4 20 24 4 10 15 6 16

C5 40 19 15 9 10 36 8 29


3.

4.

5.


Keahlian

Dktr

Bedah

D1

Jantung

D2

Kandungan

bipartite

Kulit


Koordinator

Ford Fulkerson

Asisten


DokterUtama PembantuDokter

D3 D4 D5 D6 D7


16 Juli 2013


30

.:Permasalahan 1:. • Proses untuk menentukan dokter

Keahlian

yang memenuhi kondisi dengan model GB 1. 2.


bipartite 3.

5.

D1

Jantung

D2 Kandungan

D3 Kulit


Ford Fulkerson 4.

Bedah

Dokter

Koordinator

D4

Asisten


D5 Dktr Utama

D6 Pmbntu Dktr

D7

16 Juli 2013


31


Keahlian



bipartite 3.


Ford Fulkerson 4.

5.


Bedah

Dokter D1

DktrJantung Keahlian D2 D1 Jantung, bedah, pembantu dokter D2 D3 D4 D5 D6

Kandungan

Kulit

Koordinator

Kulit, kandungan, asisten dokter utama D3 Kandungan, bedah, dokter utama Jantung, pembantu dokter

D4

Jantung, kulit, dokter utama

Jantung, kandungan, koord. dokter D5 utama Dktr D7 Utama Kandungan, bedah, pembantu dokter


Asisten

D6 Pmbntu Dktr

D7

16 Juli 2013


32


Keahlian



bipartite 3.

5.

D1

Jantung

D2 Kandungan

D3 Kulit


Ford Fulkerson 4.

Bedah

Dokter

Koordinator

D4

Asisten


D5 Dktr Utama

D6 Pmbntu Dktr

D7

16 Juli 2013


33


Keahlian



bipartite 3.

5.

D1

Jantung

D2 Kandungan

D3 Kulit


Ford Fulkerson 4.

Bedah

Dokter

Koordinator

D4

Asisten


D5 Dktr Utama

D6 Pmbntu Dktr

D7

16 Juli 2013


34


Keahlian



bipartite 3.

5.

D1

Jantung

D2 Kandungan

D3 Kulit


Ford Fulkerson 4.

Bedah

Dokter

Koordinator

D4

Asisten


D5 Dktr Utama

D6 Pmbntu Dktr

D7

16 Juli 2013


35


Keahlian



Bedah

D2 Kandungan

D3 Kulit


Ford Fulkerson 4.

5.

16 Juli 2013

Koordinator

D4

Asisten


D1

Jantung

bipartite 3.

Dokter

D5 Dktr Utama

D6 Pmbntu Dktr

D7


36



bipartite 3.

5.

Keahlian Bedah

Dokter D1,D3,D7

Jantung

D1,D4,D5,D6

Kandungan

D2,D3,D6,D7

Kulit


Koordinator


Pembantu Dokter

Ford Fulkerson 4.

Tabel hasil pengelompokkan dokter Berdasarkan keahlian

Asisten Dokter utama

D2,D5 D6 D2 D2,D3,D5,D6

D1,D4,D7


16 Juli 2013


37


3.

Tabel data kondisi

Kondisi Keahlian yang dibutuhkan C1 Jantung dan Kulit C2

bipartite

C4

Kandungan atau (Bedah dan DokterUtama ) (Bedah dan DokterUtama ) atau (Kandungan dan Asisten) Jantung dan DokterUtama


C5

Kandungan


C3

Ford Fulkerson 4.

5.


16 Juli 2013


38



bipartite 3.


Ford Fulkerson 4.

5.


16 Juli 2013

Tabel data kondisi

Kondisi Keahlian yang dibutuhkan C1 Jantung dan Kulit C2

Kandungan atau (Bedah dan DokterUtama ) Tabel hasil pengelompokkan dokter C3 (Bedah dan DokterUtama ) Berdasarkan keahlian atau (Kandungan dan Asisten) Dokter C4Keahlian Jantung dan DokterUtama Bedah C5

Jantung

Kandungan

Kandungan Kulit Koordinator Asisten Dokter utama Pembantu Dokter


D1,D3,D7

D1,D4,D5,D6 D2,D3,D6,D7 D2,D5 D6 D2 D2,D3,D5,D6 D1,D4,D7 39



bipartite 3.

5.

Kondisi Keahlian yang dibutuhkan C1 Jantung dan Kulit C2 C3 C4

Kandungan atau (Bedah dan DokterUtama ) (Bedah dan DokterUtama ) atau (Kandungan dan Asisten) Jantung dan DokterUtama

C5 Kandungan dokter dikelompokkan berdasarkan keahliannya menggunakan algortima Kondisi C1

Ford Fulkerson 4.

Tabel data kondisi


= Jantung dan Kulit = {D1,D4,D5,D6} ∩ {D2,D5} = {D5}


16 Juli 2013


40



Tabel dokter yang memenuhi kondisi

Kondisi C1 C2 C3 C4 C5

Dokter yang memenuhi

D5 D2,D3,D6,D7 D2,D3 D5,D6 D2,D3,D6,D7

bipartite 3.


Ford Fulkerson 4.

5.


16 Juli 2013


41


3.


Tabel dokter yang memenuhi kondisi

Kondisi C1 C2 C3 C4 C5

5.

D5 D2,D3,D6,D7 D2,D3 D5,D6 D2,D3,D6,D7

bipartite

Tabel data jarak


Dokter

Ford Fulkerson 4.

Dokter yang memenuhi


16 Juli 2013


D1 D2 D3 D4 D5 D6 D7

Kondisi C1 10 12 24 2 3 12 12

C2 12 40 2 12 14 24 15

C3 14 6 14 15 4 4 6

C4 5 9 10 9 20 10 16

C5 40 19 15 9 10 36 8 42


3.

• Jarak dokter yang tidak memenuhi kondisi di-set maksimal, yaitu 100


bipartite

Tabel data jarak


Dokter

Ford Fulkerson 4.

5.


16 Juli 2013


D1 D2 D3 D4 D5 D6 D7

Kondisi C1 10 12 24 2 3 12 12

C2 12 40 2 12 14 24 15

C3 14 6 14 15 4 4 6

C4 5 9 10 9 20 10 16

C5 40 19 15 9 10 36 8 43


3.

• Jarak dokter yang tidak memenuhi kondisi di-set maksimal, yaitu 100


bipartite

Tabel data jarak


Dokter

Ford Fulkerson 4.

5.


16 Juli 2013


D1 D2 D3 D4 D5 D6 D7

Kondisi C1 100 100 100 100 3 100 100

C2 100 40 2 100 100 24 15

C3 100 6 14 100 100 100 100

C4 C5 100 100 100 19 100 15 100 100 20 100 10 36 100 8 44


yang ditugaskan dengan model IP 1. 2.

3. 4. 5.

inisialisasi data fungsi tujuan, seluruh batasan, dan variabel keputusan digunakan pada model inisialisasi nilai b_L dan b_U inisialisasi nilai x_L dan x_U inisialisasi IntVars

16 Juli 2013

Tabel data jarak

Dokter D1 D2 D3 D4 D5 D6 D7


Kondisi C1 100 100 100 100 3 100 100

C2 100 40 2 100 100 24 15

C3 100 6 14 100 100 100 100

C4 C5 100 100 100 19 100 15 100 100 20 100 10 36 100 8

45


Tabel data jarak


3. 4. 5.


16 Juli 2013


•

Kondisi C1 100 100 100 100 3 100 100

C2 100 40 2 100 100 24 15

C3 100 6 14 100 100 100 100

C4 C5 100 100 100 19 100 15 100 100 20 100 10 36 100 8

Fungsi tujuan: Z=

100xD1C1+100xD1C2+100xD1C3+100xD1C4+100xD1C5 +100xD2C1+40xD2C2+6xD2C3+100xD2C4+19xD2C5 +100xD3C1+2xD3C2+14xD3C3+100xD3C4+15xD3C5 +100xD4C1+100xD4C2+100xD4C3+100xD4C4+100xD4C5 +3xD5C1+100xD5C2+100xD5C3+20xD5C4+100xD5C5 +100xD6C1+24xD6C2+100xD6C3+10xD6C4+36xD6C5 +100xD7C1+15xD7C2+100xD7C3+100xD7C4+8xD7C5


46



3. 4. 5.


16 Juli 2013

•

Batasan 1:

- tiap-tiap dokter ditugaskan dengan tepat satu kondisi Dokter D1: xD1C1+xD1C2+xD1C3+xD1C4+xD1C5 =1 Dokter D2: xD2C1+xD2C2+xD2C3+xD2C4+xD2C5 =1 Dokter D3: xD3C1+xD3C2+xD3C3+xD3C4+xD3C5 =1 Dokter D4: xD4C1+xD4C2+D4C3+xD4C4+xD4C5 =1 Dokter D5: xD5C1+xD5C2+xD5C3+xD5C4+xD5C5 =1 Dokter D6  xD6C1+xD6C2+xD6C3+xD6C4+xD6C5 =1 Dokter D7  xD7C1+xD7C2+xD7C3+xD7C4+xD7C5 =1


47



3. 4. 5.


16 Juli 2013

•

Batasan 2:

- tiap-tiap kondisi ditugaskan dengan tepat satu dokter Kondisi C1:

xD1C1+xD2C1+xD3C1+xD4C1+xD5C1+xD6C1+xD7C1=1 Kondisi C2:




xD1C5+xD2C5+xD3C5+xD4C5+xD5C5+xD6C5+xD7C5=1


48



3. 4. 5.


16 Juli 2013

b_L = 1 b_U = 1 x_L = 0 x_U =1 IntVars = 1


49



3. 4. 5.


• Tujuan meminimalkan total jarak Tabel data jarak


Kondisi C1 100 100 100 100 3 100 100

C2 100 40 2 100 100 24 15

C3 100 6 14 100 100 100 100

C4 C5 100 100 100 19 100 15 100 100 20 100 10 36 100 8

Hasil optimal permasalahan 1, dengan total jarak = 29 16 Juli 2013


50

.:Permasalahan 1:. Tabel Dokter yang ditugaskan

Kondisi Dokter C1 D5 C2 D3 C3 D2 C4 D6 C5 D7 Total jarak

Jarak 3 2 6 10 8 29

Gambar Penugasan dokter untuk permasalahan 1

analisa

simpulan

16 Juli 2013

beda Tugas Akhir – KI091391

51

.:Beda konfigurasi:.

Setelah dilakukan optimasi

16 Juli 2013


52

.:Permasalahan 2:. Pada permasalahan ini, akan dilakukan untuk mengamati jumlah kemungkinan dokter yang memenuhi kondisi berpengaruh terhadap performa model. Percobaan dilakukan sebanyak 7 kali dengan data yang berbeda-beda.

16 Juli 2013


53

.:Permasalahan 2:. •

Langkah-langkah yang dilakukan seperti permasalahan 1.

•

Data yang digunakan setiap percobaan: •

5 macam keahlian

•

40 dokter

•

18 kondisi

•

jarak 40 dokter ke 18 lokasi kondisi

16 Juli 2013


54


Hasil optimal permasalahan 2 Tabel hasil optimal permasalahan 2

Percobaan

Jarak

1

715

2

530

3

116

4

119

5

219

6

142

7

129

16 Juli 2013


55


Estimasi running time Grafik running time permasalahan 2 Jumlah kemungkinan dokter yang memenuhi kondisi

Total rata-rata running time pada uji coba 2 0.120

Percobaan 1 = Percobaan 2 = Percobaan 3 = Percobaan 4 = Percobaan 5 = Percobaan 6 = Percobaan 7 =

0.100

Waktu (detik)

0.080 0.060 0.040

170 309 430 420 387 391 381

0.020 0.000 Waktu proses 1 Waktu proses 2 Waktu total

analisa

1 0.017 0.088 0.105

2 0.020 0.089 0.109

3 0.020 0.083 0.103

4 0.020 0.085 0.105

5 0.015 0.087 0.102

6 0.016 0.086 0.102

7 0.016 0.092 0.108

simpulan

16 Juli 2013


56

.:Analisa Permasalahan(1):. 1. Pada permasalahan 1, menunjukkan bahwa model GB dapat

digunakan dalam proses menentukan dokter yang memenuhi kondisi karena memberikan hasil yang akurat. 2. Selain itu, model IP dapat digunakan dalam proses menentukan dokter yang ditugaskan karena menghasilkan suatu hasil optimal berupa total jarak. 3. Data keluaran dari model GB menjadi data masukan dari model IP sehingga model IP bergantung model GB. Penentuan dokter yang ditugaskan, bergantung pada faktor dokter yang memenuhi kondisi.

16 Juli 2013


57

.:Analisa Permasalahan(2):. • Pada percobaan 3 menunjukkan bahwa jumlah kemungkinan dokter yang memenuhi kondisi paling banyak, yaitu 430 dan total running time-nya tidak menunjukkan waktu yang tertinggi, yaitu 0.103 detik. Grafik running time permasalahan 2 Total rata-rata running time pada uji coba 2 0.120 0.100

Jumlah dokter yang memenuhi kondisi

Waktu (detik)

0.080 0.060 0.040 0.020 0.000 Waktu proses 1 Waktu proses 2 Waktu total

16 Juli 2013

1 0.017 0.088 0.105

2 0.020 0.089 0.109

3 0.020 0.083 0.103

4 0.020 0.085 0.105

5 0.015 0.087 0.102

6 0.016 0.086 0.102

7 0.016 0.092 0.108



170 309 430 420 387 391 381

58

.:Analisa Permasalahan(2):. • Pada percobaan 1 menunjukkan bahwa jumlah kemungkinan dokter yang memenuhi kondisi paling sedikit, yaitu 170 namun total running time-nya tidak menunjukkan waktu yang terendah, yaitu 0.105 detik. Grafik running time permasalahan 2 Total rata-rata running time pada uji coba 2 0.120 0.100


Waktu (detik)


16 Juli 2013

1 0.017 0.088 0.105

2 0.020 0.089 0.109

3 0.020 0.083 0.103

4 0.020 0.085 0.105

5 0.015 0.087 0.102

6 0.016 0.086 0.102

7 0.016 0.092 0.108



170 309 430 420 387 391 381

59

.:Analisa Permasalahan(2):. • Pada percobaan 2 menunjukkan bahwa total running time-nya menunjukkan waktu yang tertinggi, yaitu 0.109 detik namun jumlah kemungkinan dokter yang memenuhi kondisi adalah 309. Grafik running time permasalahan 2 Total rata-rata running time pada uji coba 2 0.120 0.100


Waktu (detik)


16 Juli 2013

1 0.017 0.088 0.105

2 0.020 0.089 0.109

3 0.020 0.083 0.103

4 0.020 0.085 0.105

5 0.015 0.087 0.102

6 0.016 0.086 0.102

7 0.016 0.092 0.108



170 309 430 420 387 391 381

60

.:Analisa Permasalahan(2):. • Pada percobaan 6 menunjukkan bahwa total running time-nya menunjukkan

waktu yang terrendah, yaitu 0.102 detik namun jumlah kemungkinan dokter yang memenuhi kondisi tidak menunjukkan jumlah yang terendah adalah 391. Grafik running time permasalahan 2 Total rata-rata running time pada uji coba 2 0.120 0.100


Waktu (detik)


16 Juli 2013

1 0.017 0.088 0.105

2 0.020 0.089 0.109

3 0.020 0.083 0.103

4 0.020 0.085 0.105

5 0.015 0.087 0.102

6 0.016 0.086 0.102

7 0.016 0.092 0.108



170 309 430 420 387 391 381

61

.:BackUp:.

16 Juli 2013


62

Graf Bipartite (GB) • Graf bipartite adalah graf 𝐺(𝑉, 𝐸) yang himpunan atau node 𝑉nya dapat dipartisi menjadi dua subhimpunan 𝑉1 dan 𝑉2 sedemikian sehingga setiap edge dalam 𝐸 insiden pada satu vertek di 𝑉1 dan satu vertek di 𝑉2 . v1

v4 v2

v5 v3

Contoh graf bipartite

16 Juli 2013


63

Graf Bipartite (GB) • Menurut Thomas H. et all [6], dalam suatu permasalahan pemasangan maksimal dalam graf bipartite dapat menggunakan metode Ford Fulkerson. • Oleh karena itu permasalahan pemasangan dimodelkan sebagai suatu jaringan karena Metode Ford Fulkerson digunakan untuk menyelesaikan permasalahan network flow. v1

v1

v4 v2

Contoh graf bipartite yang dibentuk sebagai

v4 s

v2 t

jaringan

v5

v5 v3

v3

16 Juli 2013


64

Algoritma Ford Fulkerson 1. Set 𝑓 𝑢, 𝑣 ← 0 dan 𝑓 𝑣, 𝑢 ← 0 untuk semua edge 𝑢, 𝑣 2. Perulangan selama terdapat sebuah aliran 𝑝 dari 𝑠 menuju 𝑡, di mana kapasitas tersisa 𝑐𝑓 𝑢, 𝑣 > 0 untuk semua 𝑢, 𝑣 ∈ 𝑝: o Temukan 𝑐𝑓 𝑝 = min 𝑐𝑓 𝑢, 𝑣 𝑢, 𝑣 ∈ 𝑝 ] o

Untuk setiap edge 𝑢, 𝑣 ∈ 𝑝 f 𝑢, 𝑣 ← 𝑓 𝑢, 𝑣 + 𝑐𝑓 𝑝 f 𝑣, 𝑢 ← −𝑓 𝑢, 𝑣

16 Juli 2013


65


2

0/12

4

0/16 0/100/4

1

Untuk setiap edge 𝑢, 𝑣 ∈ 𝑝 f 𝑢, 𝑣 ← 𝑓 𝑢, 𝑣 + 𝑐𝑓 𝑝

0/20 0/9

6

0/7

0/13

0/4 3

0/14

5

Contoh graf awal yang akan diselesaikan dengan

algoritma Ford Fulkerson

f 𝑣, 𝑢 ← −𝑓 𝑢, 𝑣

16 Juli 2013


66


2

0/12

4

0/16 0/100/4

1


0/20 0/9

6

0/7

0/13

0/4 3

0/14

5

Contoh graf awal yang akan diselesaikan dengan

algoritma Ford Fulkerson

f 𝑣, 𝑢 ← −𝑓 𝑢, 𝑣

16 Juli 2013


67


Lintasan 1-2-4-3-5-6 2

12

4

16 1

20 10 4

9

6

7

13

4 3

14

5

Untuk setiap edge 𝑢, 𝑣 ∈ 𝑝 f 𝑢, 𝑣 ← 𝑓 𝑢, 𝑣 + 𝑐𝑓 𝑝 f 𝑣, 𝑢 ← −𝑓 𝑢, 𝑣 𝒄𝒇 𝒑 = 4

16 Juli 2013


68


Lintasan 1-2-4-3-5-6 2

4

16 1

20 10 4

9

4 3

2

14

4/12

5

4

4/16 1

20 10 4

4/9

4/4 3


6

7

13

16 Juli 2013

6

7

13


12

4/14

5

69


Lintasan 1-2-3-5-4-6

2

8 4

4

12 4 1

20 10 4

4 5

6

7

13

4 3

10 4

5


16 Juli 2013


70


Lintasan 1-2-3-5-4-6

2

4

12 4 1

20 10 4

4 5

4 3

10 4

5

2

4/12

4

11/16 1

7/20 7/10 4

4/9

4/4 3


6

7/7

13

16 Juli 2013

6

7

13


8 4

11/14

5

71

Algoritma Ford Fulkerson 1. Set 𝑓 𝑢, 𝑣 ← 0 dan 𝑓 𝑣, 𝑢 ← 0 untuk semua edge 𝑢, 𝑣 2. Perulangan selama terdapat sebuah

Lintasan 1-3-2-4-6

2

aliran 𝑝 dari 𝑠 menuju 𝑡, di mana kapasitas tersisa 𝑐𝑓 𝑢, 𝑣 > 0 untuk semua 𝑢, 𝑣 ∈ 𝑝: o Temukan 𝑐𝑓 𝑝 = min 𝑐𝑓 𝑢, 𝑣 𝑢, 𝑣 ∈ 𝑝 ] o

8 4

4

4 5

7

13 7

5 11 1

3 11 13

6 4

3

3 11

5


16 Juli 2013


72


Lintasan 1-3-2-4-6

2



4

4 5

7

13 7

5 11 1

3 11 13

2

3 11

12/12

5

4

11/16 1

15/20 10 1/4

4/9

6

7/7

8/13

4/4 3


6 4

3

f 𝑣, 𝑢 ← −𝑓 𝑢, 𝑣

16 Juli 2013

8 4

11/14

5

73


Lintasan 1-3-4-6 2


12

4 5 15

5 11 1

11 3

4 5

6

7

5 8

4 3

3 11

5


16 Juli 2013


74


Lintasan 1-3-4-6 2

4 5 15

5 11 1

11 3

4 5

6

7

5 8


12

4 3

3 11

2

12/12

5

4

11/16 1

19/20 10 1/4

9

12/13

4/4 3

16 Juli 2013


6

7/7

11/14

5

75

Algoritma Ford Fulkerson • Setelah tidak ditemukan lagi lintasan augmenting, maka pencarian berhenti. • Graf tersebut memiliki 4 jalur yaitu: o 1-2-4-3-5-6 dengan maksimal flow 4, o 1-2-3-5-4-6 dengan maksimal flow 7, o 1-3-2-4-6 dengan maksimal flow 8, dan o 1-3-4-6 dengan maksimal flow 4

16 Juli 2013


76

Operasi Himpunan Union • Union merupakan gabungan dari dua himpunan 𝐴 dan 𝐵 atau himpunan yang terdiri dari semua elemen yang menjadi anggota 𝐴 atau menjadi anggota 𝐵. • Definisi formal dari union 𝑨 ∪ 𝑩 = *𝒙|𝒙 ∈ 𝑨 ∨ 𝒙 ∈ 𝑩+ • Contoh union dari himpunan {1,3,5} dan {1,2,3} adalah {1,2,3,5}

16 Juli 2013


77

Operasi Himpunan Intersection • intersection merupakan irisan dari dua himpunan 𝐴 dan 𝐵

adalah himpunan yang terdiri dari semua elemen persekutuan dari himpunan 𝐴 dan 𝐵. • Definisi formal dari intersection 𝑨 ∩ 𝑩 = *𝒙|𝒙 ∈ 𝑨 ∧ 𝒙 ∈ 𝑩+ • Contoh intersection dari himpunan {1,3,5} dan {1,2,3} adalah {1,3}

16 Juli 2013


78

Langkah-langkah yang digunakan untuk merubah ke model GB menjadi bentuk jaringan dalam penugasan dokter

Langkah-langkah yang digunakan untuk merubah ke model GB menjadi bentuk jaringan dalam penugasan dokter

1. Jika setiap edge-nya dimulai dari 𝑢

ke 𝑣 dan 𝑐(𝑢, 𝑣) adalah kapasitas maka 𝑐 𝑢, 𝑣 ditandai dengan angka 1. 2. Sebuah source dan edge-edge dari source ke masing-masing node yang mewakili keahlian dokter dengan 𝑐 𝑢, 𝑣 = 𝑗𝑢𝑚𝑙𝑎ℎ 𝑑𝑜𝑘𝑡𝑒𝑟 ditambahkan. 3. Sebuah sink dan edge-edge dari masing-masing node yang mewakili dokter ke sink dengan 𝑐 𝑢, 𝑣 = 𝑗𝑢𝑚𝑙𝑎ℎ 𝑘𝑒𝑎ℎ𝑙𝑖𝑎𝑛 ditambahkan.

16 Juli 2013

Keahlian


Dokter

79

Langkah-langkah yang digunakan untuk mengelompokkan dokter berdasarkan keahliannya dengan algoritma Ford Fulkerson

Langkah-langkah yang digunakan untuk mengelompokkan dokter berdasarkan keahliannya dengan algoritma Ford Fulkerson Keahlian 1. Set 𝑓 𝑢, 𝑣 ← 0 dan 𝑓 𝑣, 𝑢 ← 0 untuk semua edge 𝑢, 𝑣 1 2. Perulangan selama terdapat sebuah aliran 𝑝 dari 𝑠 menuju 𝑡, di mana 2 kapasitas tersisa 𝑐𝑓 𝑢, 𝑣 > 0 untuk 3 semua 𝑢, 𝑣 ∈ 𝑝: o Temukan 0 4 𝑐𝑓 𝑝 = min 𝑐𝑓 𝑢, 𝑣 𝑢, 𝑣 ∈ 𝑝 ]

Dokter

O/1

O/1

O/1 O/1

O/7

O/1 O/1

O/7

O/7

f 𝑣, 𝑢 ← −𝑓 𝑢, 𝑣

O/7

O/8

O/8

O/1

O/7


10

O/1 O/1

O/7

o

9

5

O/1 O/1 O/1 O/1 O/1 O/1 O/1

11

O/8

16

O/8

12

O/8

O/7 O/7

6

O/1 O/1 O/1 O/1

7

O/1

8

O/1

O/8

13

O/8

14

15

16 Juli 2013


80


Langkah-langkah yang digunakan untuk mengelompokkan dokter berdasarkan keahliannya dengan algoritma Ford Fulkerson Keahlian 1. Set 𝑓 𝑢, 𝑣 ← 0 dan 𝑓 𝑣, 𝑢 ← 0 untuk semua edge 𝑢, 𝑣 1 2. Perulangan selama terdapat sebuah aliran 𝑝 dari 𝑠 menuju 𝑡, di mana 2 kapasitas tersisa 𝑐𝑓 𝑢, 𝑣 > 0 untuk 3 semua 𝑢, 𝑣 ∈ 𝑝: o Temukan 0 4 𝑐𝑓 𝑝 = min 𝑐𝑓 𝑢, 𝑣 𝑢, 𝑣 ∈ 𝑝 ]

Dokter

O/1

O/1

O/1 O/1

O/7

O/1 O/1

O/7

O/7

O/7

O/8

O/8

O/1

O/7


10

O/1 O/1

O/7

o

9

5

O/1 O/1 O/1 O/1 O/1 O/1 O/1

11

O/8

16

O/8

12

O/8

O/7 O/7

f 𝑣, 𝑢 ← −𝑓 𝑢, 𝑣

6

O/1 O/1 O/1 O/1

7

O/1

8

O/1

O/8

13

O/8

14

Lintasan 0-1-9-16 𝒄𝒇 𝒑 = 1

16 Juli 2013


15

81


Langkah-langkah yang digunakan untuk mengelompokkan dokter berdasarkan keahliannya dengan algoritma Ford Fulkerson Keahlian 1. Set 𝑓 𝑢, 𝑣 ← 0 dan 𝑓 𝑣, 𝑢 ← 0 untuk semua edge 𝑢, 𝑣 1/1 1 2. Perulangan selama terdapat sebuah aliran 𝑝 dari 𝑠 menuju 𝑡, di mana 2 kapasitas tersisa 𝑐𝑓 𝑢, 𝑣 > 0 untuk 1/7 3 semua 𝑢, 𝑣 ∈ 𝑝: o Temukan 0 4 𝑐𝑓 𝑝 = min 𝑐𝑓 𝑢, 𝑣 𝑢, 𝑣 ∈ 𝑝 ] O/1

O/1 O/1

O/1 O/1

O/7

O/7

O/7

10

1/8 O/8

O/1

O/7


9

O/1 O/1

O/7

o

Dokter

5

O/1 O/1 O/1 O/1 O/1 O/1 O/1

11

O/8

16

O/8

12

O/8

O/7 O/7

f 𝑣, 𝑢 ← −𝑓 𝑢, 𝑣

6

O/1 O/1 O/1 O/1

7

O/1

8

O/1

O/8

13

O/8

14

Lintasan 0-1-9-16

16 Juli 2013


15

82


Langkah-langkah yang digunakan untuk mengelompokkan dokter berdasarkan keahliannya dengan algoritma Ford Fulkerson Keahlian 1. Set 𝑓 𝑢, 𝑣 ← 0 dan 𝑓 𝑣, 𝑢 ← 0 untuk semua edge 𝑢, 𝑣 1/1 1 2. Perulangan selama terdapat sebuah aliran 𝑝 dari 𝑠 menuju 𝑡, di mana 2 kapasitas tersisa 𝑐𝑓 𝑢, 𝑣 > 0 untuk 1/7 3 semua 𝑢, 𝑣 ∈ 𝑝: o Temukan 0 4 𝑐𝑓 𝑝 = min 𝑐𝑓 𝑢, 𝑣 𝑢, 𝑣 ∈ 𝑝 ] O/1

O/1 O/1

O/1 O/1

O/7

O/7

f 𝑣, 𝑢 ← −𝑓 𝑢, 𝑣

O/7

10

1/8 O/8

O/1

O/7


9

O/1 O/1

O/7

o

Dokter

5

O/1 O/1 O/1 O/1 O/1 O/1 O/1

11

O/8

16

O/8

12

O/8

O/7 O/7

6

O/1 O/1 O/1 O/1

7

O/1

8

O/1

O/8

13

O/8

14


16 Juli 2013


15

83


Langkah-langkah yang digunakan untuk mengelompokkan dokter berdasarkan keahliannya dengan algoritma Ford Fulkerson Keahlian 1. Set 𝑓 𝑢, 𝑣 ← 0 dan 𝑓 𝑣, 𝑢 ← 0 untuk semua edge 𝑢, 𝑣 1/1 1 2. Perulangan selama terdapat sebuah aliran 𝑝 dari 𝑠 menuju 𝑡, di mana 2 1/1 kapasitas tersisa 𝑐𝑓 𝑢, 𝑣 > 0 untuk 2/7 3 semua 𝑢, 𝑣 ∈ 𝑝: o Temukan 0 4 𝑐𝑓 𝑝 = min 𝑐𝑓 𝑢, 𝑣 𝑢, 𝑣 ∈ 𝑝 ] O/1

O/1

O/1 O/1

O/7

O/7

f 𝑣, 𝑢 ← −𝑓 𝑢, 𝑣

O/7

10

1/8 O/8

O/1

O/7


9

O/1 O/1

O/7

o

Dokter

5

O/1 O/1 O/1 O/1 O/1 O/1 O/1

11

1/8

16

O/8

12

O/8

O/7 O/7

6

O/1 O/1 O/1 O/1

7

O/1

8

O/1

O/8

13

O/8

14

Lintasan 0-1-11-16

16 Juli 2013


15

84



O/1

O/1 O/1

O/7

O/7

f 𝑣, 𝑢 ← −𝑓 𝑢, 𝑣

O/7

10

1/8 O/8

O/1

O/7


9

O/1 O/1

O/7

o

Dokter

5

O/1 O/1 O/1 O/1 O/1 O/1 O/1

11

1/8

16

O/8

12

O/8

O/7 O/7

6

O/1 O/1 O/1 O/1

7

O/1

8

O/1

O/8

13

O/8

14


16 Juli 2013


15

85



O/1

f 𝑣, 𝑢 ← −𝑓 𝑢, 𝑣

O/7

O/1 O/1

O/7

O/1 O/1 O/1

O/7

10

1/8 O/8

O/1

O/7


9

O/1 O/1

O/7

o

Dokter

5

11

1/8

16

O/8

1/1

O/1 O/1 O/1

12

O/8

O/7 O/7

6

O/1 O/1 O/1 O/1

7

O/1

8

O/1

O/8

13

1/8

14

Lintasan 0-1-15-16

16 Juli 2013


15

86



1. Set 𝑓 𝑢, 𝑣 ← 0 dan 𝑓 𝑣, 𝑢 ← 0 untuk semua edge 𝑢, 𝑣 2. Perulangan selama terdapat sebuah



Tabel hasil pengelompokkan dokter Berdasarkan keahlian

Keahlian Bedah Jantung

D1,D4,D5,D6

Kandungan

D2,D3,D6,D7

Kulit Koordinator Asisten Dokter utama Pembantu Dokter

16 Juli 2013

Dokter D1,D3,D7


D2,D5 D6 D2 D2,D3,D5,D6 D1,D4,D7

87

PRESENTASI TUGAS AKHIR KI OPTIMASI PERMASALAHAN PENUGASAN DOKTER MENGGUNAKAN REPRESENTASI GRAF BIPATIT BERBOBOT

Recommend Documents