## PENERAPAN METODE ALGORITMA GENETIKA UNTUK PERMASALAHAN PENJADWALAN PERAWAT
( Nurse Schedulling Problem )
Nadiya Hijriana
Program Studi Teknik Informatika Universitas Islam Kalimantan, Banjarmasin E-mail: nadyahijriana@yahoo.com

## ABSTRACT
Nurse  have  an  important  role  that  influencing  performance  and  quality  of service  user  at  hospital.  Therefore,    hospital  management  needed  to  create  a  good schedule  so  that  user  (patient)  in  the  hospital  can  get  good  service  also.  At  this research, what studied is how to develop a computerized nurse-scheduling model that implemented  a  genetic  algorithm  method.  Making  model  is  accounts  to  some objectives and policies at Islamic Hospital of Banjarmasin.
By using software of Delphi XE2 to developing model, then some experiments used to test the model and giving result that a computerized nurse scheduling with a genetic  algorithm  method  is  more  effiecient  and  effectivethan  manual  made- schedules.
Keywords: Nurse scheduling, Genetic algorithm

## 1. PENDAHULUAN
Di  sebuah  rumah  sakit,  tenaga  medis  perawat  memegang  peranan  penting  yang mempengaruhi  kinerja  dan  mutu  pelayanan  rumah  sakit  tersebut.  Sering  terjadi situasi  dimana  banyaknya  jumlah  pasien  yang  membutuhkan  pelayanan  kesehatan sangat tidak sebanding dengan jumlah perawat  yang ada. Oleh karena itu jam kerja perawat  perlu  diatur  dengan  persiapan  yang  matang  sehingga  dapat  diperoleh penjadwalan yang baik. Dengan adanya penjadwalan yang baik, maka semua pasien akan dapat terlayani dengan baik pula.
Pada penelitian ini, akan diterapkan metode Algoritma Genetika untuk membuat model penjadwalan perawat di Rumah Sakit Islam Banjarmasin. Model yang dibuat berdasarkan peraturan dan kebijakan yang berlaku di rumah sakit tersebut.
Tujuan  Penelitian  ini  adalah  untuk  menerapkan  metode  Algoritma  Genetika dalam melakukan penjadwalan perawat sehingga proses penjadwalan dapat menjadi lebih  mudah  dan  efisien  dibandingkan  dengan  melakukan  penjadwalan  secara manual.
Sedangkan manfaat dari penelitian ini antara lain:
1. Manfaat  praktis  dari  penelitian  ini  adalah  diharapkan  agar  nantinya  dapat digunakan sebagai bahan pertimbangan oleh para pengambil keputusan dalam hal ini  kepala  staf  perawat,  untuk  membuat  penjadwalan  kerja  yang  efektif  dan efisien, tanpa harus mengeluarkan banyak waktu dan tenaga.
2. Manfaat  teoritis  dari  hasil  penelitian  ini  diharapkan  dapat  memberikan sumbangan bagi penerapan maupun pengembangan  teori Artificial Intelligence, khususnya dalam mempelajari Algoritma Genetika.
3. Sebagai acuan untuk penelitian atau pengembangan model penjadwalan perawat selanjutnya.

## 2. TINJAUAN PUSTAKA

## 2.1 Penjadwalan
Pengertian  jadwal  menurut  kamus  besar  bahasa  Indonesia  adalah  pembagian waktu  berdasarkan  rencana  pengaturan  urutan  kerja;  daftar  atau  tabel  kegiatan  atau rencana  kegiatan  dengan  pembagian  waktu  pelaksanaan  yang  terperinci,  sedangkan pengertian  penjadwalan  adalah  proses,  cara,  perbuatan  menjadwalkan  atau memasukkan dalam jadwal [6].

## 2.2 Keperawatan
Menurut hasil Lokakarya Keperawatan Nasional tahun 1983 yang ditulis oleh Sri Praptianingsih  [2]  keperawatan  adalah  suatu  bentuk  pelayanan  profesional  yang merupakan  bagian  integral  dari  pelayanan  yang  didasarkan  pada  ilmu  dan  kiat keperawatan,  berbentuk  pelayanan  bio-psiko-sosiospiritual  yang  komprehensif, ditujukan  kepada  individu,  dan  masyarakat  baik  yang  sakit  maupun  sehat  yang mencakup seluruh siklus hidup manusia.

## 2.3  Algoritma Genetika
Algoritma  genetika  adalah  algoritma  pencarian  yang  berdasarkan  pada mekanisme  sistem  natural  yakni  genetik  dan  seleksi  alam.Berbeda  dengan  teknik
pencarian  konvensional,  algoritma  genetik  berangkat  dari  himpunan  solusi  yang dihasilkan  secara  acak.  Himpunan  ini  disebut  populasi.  Sedangkan  setiap    individu dalam  populasi    disebut    kromosom  yang  merupakan    representasi    dari  solusi. Kromosom-kromosom  berevolusi  dalam  suatu  proses  iterasi    yang  berkelanjutan yang  disebut    generasi.    Pada    setiap   generasi,    kromosom  dievaluasi   berdasarkan suatu  fungsi  evaluasi  [4].  Setelah  beberapa  generasi  maka  algoritma  genetik  akan konvergen  pada  kromosom terbaik,  yang diharapkan  merupakan  solusi  optimal [1].

## A. Representasi Kromosom
Representasi  kromosom  merupakan  proses encoding atau  pengkodean  dari penyelesaian  asli  dari  suatu  permasalahan.  Pengkodean  kandidat  penyelesaian  ini disebut  dengan  kromosom.  Pengkodean  tersebut  meliputi  penyandian  gen,  dengan satu gen mewakili satu variabel [7].

## B. Inisialisasi Populasi
Inisialisasi  populasi  merupakan  salah  satu  tahapan  awal  yang  paling  penting dalam  algoritma  genetika  agar  menghasilkan  solusi  yang  optimal.  Inisialisasi populasi  merupakan  tahap  pembentukan  populasi  yang  dibentuk  dari  sekumpulan individusecara  acak  [5].  Induvidu  bisa  dikatakan  sama  dengan  kromosom  yang merupakan kumpulan dari gen.

## C. Evaluasi Fungsi Fitness
Suatu  induvidu  atau  kromosom  dievaluasi  berdasarkan  suatu  fungsi tertentusebagai ukuran performasinya. Fungsi yang digunakan untuk mengukur nilai kecocokan disebut dengan fitness function [3].Proses evaluasi fungsi fitness ini akan terus berjalan sampai terpenuhinya kriteria berhenti.

## D. Seleksi
Seleksi  merupakan  proses  pemilihan  individu/  kromosom  dari  generasi  lama untuk  dijadikan  orangtua  yang  akan  saling  di- crossover (kawin  silang)  untuk membentuk  individu  baru  di  generasi  baru.  Berdasarkan  teori  evolusi  Darwin, kromosom yang terbaik seharusnya dapat bertahan hidup dan membentuk keturunan baru ( offspring ).

## E.Perkawinan Silang ( Crossover )
Crossover atau  perkawinan  silang  merupakan  salah  satu  operator  dalam algoritma  genetika  yang  melibatkan  dua induk  untuk  menghasilkan  keturunan  yang baru.. Perkawinan silang dilakukan dengan melakukan pertukaran gen dari dua induk secara acak.

## F. Mutasi ( Mutation )
Mutasi  merupakan  proses  mengubah  nilai  dari  satu  atau  beberapa  gen  dalam suatu  kromosom.  Mutasi  ini  berperan  untuk  menggantikan  gen  yang  hilang  dari populasi  akibat  proses  seleksi  yang  memungkinkan  munculnya  kembali  gen  yang tidak muncul pada inisialisasi populasi.

## 3.  Metode Penelitian

## 3.1  Perancangan  Penelitian
Metode penelitian yang dilakukan adalah metode penelitian eksperimen, dengan tahapan penelitian seperti berikut:
1. Identifikasi Masalah
2. Penentuan computing approach
3. Perancangan sistemyang menerapkan computing approach
Untuk perancangan sistem penjadwalan perawat ini terdiri dari dua tahapan yaitu:
a. Perancangan Algoritma Genetika
b. Perancangan Sistem Penjadwalan
4. Eksperimen dan Pengujian Metode ( Method Test and Experiment )
5. Evaluasi dan Validasi Hasil( Result Evaluation and Validation )

## 3.2    Metode Pengumpulan Data
Dalam  penelitian  ini  data  yang  akan  dikumpulkan  terbagi  menjadi  dua  jenis, yaitu:
a. Data sekunder
Data sekunder adalah data yang diperoleh secara tidak langsung bersumber dari dokumentasi,  literatur,  buku,  jurnal  dan  informasi  lainnnya  yang  ada hubungannya dengan masalah yang diteliti.
Data  sekunder  pada  penelitian  ini  adalah  data  penjadwalan  perawat  dalam  satu bulan yang selama ini dibuat oleh manajemen rumah sakit.

## b. Data primer
Data primer adalah data yang diperoleh dari penelitian
Data  primer  dalam  penelitian  ini  adalah  data  ruangan,  data  perawat,  data  shift, dan aturan-aturan untuk penjadwalan.

## 4. HASIL DAN PEMBAHASAN
Dalam  membuat  sistem  penjadwalan  dengan  algoritma  genetika  tentunya  ada tahapan  alur  proses  metode  algoritma  genetika  yang  dijalankan  sehingga  dapat menghasilkan jadwal perawat sesuai tujuan yang ingin dicapai.
Proses tersebut dapat dilihat melalui Gambar 4.1:
Start Input Data Buat Jadwal Seleksi Crossover Evaluasi Nilai Fitness Finish Pembuatan Kromosom dan Populasi Cek apakah F(p) = 1 ? Jadwal Mutasi Tidak Ya
Gambar 4.1. Flowchart Penjadwalan dengan Metode AG
Keterangan:
1. Start
Merupakan awal dari proses untuk membuat penjadwalan pada sistem.
2. Input Data
Merupakan tahapan memasukkan data ruang, data perawat dan data waktu (shift) untuk selanjutnya diproses dengan metode Algoritma Genetika.
3. Pembuatan Kromosom dan Populasi
Selanjutnya  sistem  akan  memproses  pembuatan  kromosom  dan  populasi berdasarkan data yang telah diinputkan.
4. Evaluasi Nilai Fitness
Kromosom yang telah terbentuk akan dievaluasi nilai fitness -nya. Jika didapatkan kromosom dengan nilai fitness = 1, maka proses akan berhenti dan menghasilkan data jadwal perawat.
5. Seleksi
Tahapan seleksi dilakukan jika kriteria nilai fitness =1 tidak tercapai.
6. Crossover
Setelah  didapatkan  kromosom-kromosom  yang  terbaik  (memiliki  nilai fitness terbesar) berdasarkan hasil seleksi maka akan dilakukan proses kawin silang atau crossover .
7. Mutasi
Dilakukan  dengan  cara  mengubah  susunan  gen  terpilih  pada  kromosom  secara acak (random).

## A. Menentukan Representasi Kromosom
Dalam  menentukan  representasi  kromosom  pada  permasalahan  penjadwalan perawat, variabel yang penting adalah perawat dan shift (hari dan jam).
Ada tiga kali waktu pergantian kerja atau shift, yaitu:
1. Shift pagi (shift 1)
a. Kebutuhan dalam 1 hari = 6 jam kerja
b. Durasi waktu = antara pukul 08.00 pagi – 14.00 sore
2. Shift sore (shift 2)
a. Kebutuhan dalam 1 hari = 7 jam kerja
b. Durasi waktu = antara pukul 14.00 sore – 21.00 malam
3. Shift malam (shift 3)
a. Kebutuhan dalam 1 hari = 11 jam kerja
b. Durasi waktu = antara pukul 21.00 malam – 08.00 pagi
Dalam  simulasi  pembuatan  jadwal  perawat  melalui  sistem  penjadwalan  ini, jumlah  perawat  yang  akan  dijadwalkan  sebanyak  16  orang  untuk  satu  ruangan  dan jumlah shift yang ada dalam satu minggu adalah 21 shift (slot waktu). Untuk setiap shift,  jumlah  perawat  yang  harus  berjaga  secara  bersamaan  dalam  ruangan  tersebut terdiri  dari  4  orang.  Sehingga  terbentuk  representasi  genetika  untuk  kromosomnya adalah sebagai berikut:
Allele (nilai gen) berisi slot waktu
1~1  1~2  1~4  2~1  ….  ….  21~4
Gen1 Gen2  Gen3  Gen4   …..   …..Gen 84
Gambar 4.2. Representasi kromosom untuk penjadwalan perawat

## B. Pembuatan Populasi Awal
Untuk  membuat  populasi  awal  dilakukan  dengan  mengacak  secara random nomor  urut  dari  tabel-tabel  yang  telah  ditentukan  yakni  tabel  kode  gen  perawat dalam  satu  shift  dan  tabel  slot  waktu.  Jumlah  kromosom  yang  akan  diinisialisasi dalam populasi awal ini adalah sebanyak 80 kromosom.
Pengkodean dapat dilihat pada Tabel 4.1 dan Tabel 4.2 berikut ini:
Tabel 4.1. Tabel Kode Gen Perawat dalam Satu Shift
no_urut_gen (Kode Gen) Perawat 1 Perawat 1 2 Perawat 2 3 Perawat 3 4 Perawat 4

## Tabel 4.2  Tabel Slot Waktu
No_urut_slot (Kode_slot_ waktu) Kode Hari Hari Jam Mulai Jam Selesai 1 SN1 Senin 08.00   14.00 2 SN2 Senin 14.00 21.00 3 SN3 Senin 21.00 08.00 4 SL1 Selasa 08.00   14.00 5 SL2 Selasa 14.00 21.00 6 SL3 Selasa 21.00 08.00 7 RB1 Rabu 08.00   14.00 8 RB2 Rabu 14.00 21.00 9 RB3 Rabu 21.00 08.00 10 KM1 Kamis 08.00   14.00 11 KM2 Kamis 14.00 21.00 12 KM3 Kamis 21.00 08.00 13 JU1 Jum’at  08.00   14.00 14 JU2 Jum’at  14.00  21.00 15 JU3 Jum’at  21.00  08.00 16 SB1 Sabtu 08.00   14.00 17 SB2 Sabtu 14.00 21.00 18 SB3 Sabtu 21.00 08.00 19 MG1  Minggu  08.00   14.00 20 MG2  Minggu  14.00 21.00 21 MG3  Minggu  21.00 08.00

## C. Evaluasi Nilai Fitness
Fungsi fitness digunakan  untuk  proses  evaluasi  kromosom  agarmemperoleh kromosom yang diinginkan.  Fungsi  ini membedakan kualitas  dari kromosom untuk mengetahui  seberapa  baik  kromosom  yang  dihasilkan  [7].  Fungsi fitness tersebut adalah sebagai berikut:
1
Fitness =
1+ penalty
Keterangan:
penalty =  ∑ Bp ∑ Np
Bp =  Bobot Pelanggaran
Np =  Nilai (jumlah) Pelanggaran
Dari  persamaan  diatas  dapat  dilihat  bahwa  nilai fitness ditentukan  oleh  nilai penalty . Penalty tersebut  menunjukkan  jumlah  pelanggaran  kendala  atau  batasan ( constraint ) pada suatu kromosom. Semakin tinggi nilai fitness akan  semakin  besar kemungkinan  kromosom tersebut  terpilih  ke generasi  berikutnya.Dengan mengacu pada  fungsi fitness tersebut  maka  dalam pembuatan  jadwal  perawat  dibuat  batasan- batasan dan harga bobot untuk masing-masing batasan seperti yang ditunjukkan pada Tabel 4.3:
Tabel 4.3 Batasan atau constraint untuk penjadwalan perawat
Batasan-batasan untuk Penjadwalan Perawat Harga Bobot Tidak boleh terjadi bentrokan shift 1 Satu perawat hanya mendapat satu shift per hari 1 Tidak boleh berjaga pada shift pagi setelah malamnya bertugas jaga 1 Tidak boleh berjaga pada 3 shift malam berturut- turut 1

## D. Kriteria
Kriteria  berhenti  yang  akan  digunakan  dalam  proses  algoritma  genetika  adalah setelah mendapatkan kromosom dengan nilai fitness = 1.

## E. Seleksi
Jika  kriteria  yang  diinginkan  belum  tercapai,  maka  akan  dilanjutkan  dengan proses  seleksi  terhadap  80  kromosom  berdasarkan  nilai fitness masing-masing kromosom.  Proses  seleksi  yang  digunakan  adalah  dengan  menggunakan  metode seleksi  rangking  atau Rank  Selection dimana  kromosom  didalam  populasi  akan diurutkan  atau  dirangking  berdasarkan fitness nya  kemudian  memberi  nilai fitness baru berdasarkan urutannya.

## F. Crossover
Metode  yang  digunakan  pada  tahapan  ini  adalah  dengan  menggunakan  metode Uniform Crossover , yakni dengan cara mengacak angka pada setiap posisi gen dalam kromosom.

## G. Mutasi
Untuk  sistem  penjadwalan  ini  digunakan  proses  mutasi  gen.  Mutasi  dilakukan dengan mengubah susunan gen terpilih pada kromosom secara acak (random).

## 4,1  Hasil Eksperimen dan Pengujian
Pengujian  dilakukan  dengan  dua  cara,  yaitu  pengujian  sistem  ( white  boxdan black box ) dan pengujian metode AG yang digunakan untuk memproses penjadwalan perawat  pada  sistem  sehingga  dapat  diketahui  apakah  sistem  dengan  metode Algoritma Genetika ini dapat bekerja dengan baik dan dapat memberikan hasil sesuai tujuan.

## 4.1.1  Pengujian Sistem
Sistem  penjadwalan  perawat  dengan  metode  algoritma  genetika  ini  akan  diuji dengan  model  teknik  pengujian  yang  dapat  digunakan  untuk  menguji  perangkat lunak yaitu teknik white box dan black box .

## 4.1.2  Pengujian Algoritma Genetika
Pada pengujian ini, data masukan adalah jumlah perawat yang akan dijadwalkan sebanyak 16 orang yang tergabung dalam grup 1 dan akan dijadwalkan di ruang Al- Farabi selama periode satu minggu. Jumlah total shift selama satu minggu adalah 21 shift    atau  21  slot  waktu.  Untuk  setiap  shift  ditentukan  harus  terdiri  dari  4  orang perawat yang bertugas jaga.
Pengujian  Algoritma  Genetika  ini  dilakukan  untuk  mengetahui  apakah  sistem penjadwalan  dengan  medote  Algoritma  Genetika  ini  berjalan  sesuai  dengan  tujuan yang diinginkan yaitu terpenuhinya semua batasan atau constraint yang sebelumnya telah  ditetapkan  dan  berapa  lama  waktu  yang  diperlukan  untuk  memproses penjadwalan.
Untuk pengujian ini akan dilakukan proses AG  sebanyak empat kali, yaitu pada setting generasi  1000,  10.000,  100.000  dan  1000.000.  Adapun  skor  bobot  batasan yang  akan  diuji  pada  masing-masing setting generasi  adalah  nilai  1.  Sedangkan jumlah kromosom yang terdapat dalam populasi adalah sebanyak 80 kromosom.
Gambar 4.2   Proses AG dengan setting generasi 1000
Gambar 4.3   Hasil (jadwal)proses AG dengan setting generasi 1000
Keseluruhan  data  hasil  pengujian  Algoritma  Genetika  dapat  dilihat  pada  tabel  4.4 berikut ini:
Tabel 4.4 Hasil Pengujian Proses Algoritma Genetika
Setting Generasi Nilai fitness = 1 diperoleh pada generasi ke : Kromosom Terbaik Lama Iterasi (Proses) 1000 225 K74 2 detik 10000 297 K45 3 detik 100000 561 K68 5 detik 1000000 241 K79 3 detik

## 4.2  Evaluasi Dan Validasi Hasil Penelitian
Dari  pengujian  yang  telah  dilakukan  melalui  empat  kali  proses  penjadwalan dapat dilihat bahwa penerapan metode Algoritma Genetika pada sistem yang dibuat telah mencapai hasil yang diharapkan. Meskipun lama waktu (iterasi) untuk masing- masing proses penjadwalan berbeda-beda, namun semuanya dapat memenuhi kriteria nilai fitness yang optimal yakni nilai 1 dan ini berarti tidak ada satu pun batasan atau constraint yang dilanggar pada saat perhitungan  nilai fitness (lihat Gambar 4.3).
Setelah  melakukan  pengujian  yang  berulang-ulang  pada  proses  penjadwalan Algoritma  Genetika,  dapat  diketahui  bahwa  proses  waktu  iterasi  untuk  setiap penyelesaian  hasil  penjadwalan  yang  diperoleh  tidak  menentu.  Hal  ini  dikarenakan dalam  proses  Algoritma  Genetika  terjadi  pemakaian  nilai  acak  ( random )  pada pembentukan gen dalam suatu kromosom, proses seleksi, crossover dan mutasi.

## 4.3  Implikasi Penelitian
Berdasarkan  pengujian  yang  telah  dilakukan  dapat  diketahui  bahwa  penerapan metode  Algoritma  Genetika  dalam  suatu  sistem  penjadwalan  terbukti  dapat meningkatkan  efisiensi  proses  penjadwalan  perawat.  Untuk  mencapai  hasil  akhir proses  penjadwalan  juga  tidak  memerlukan  waktu  yang  lama.  Semua  batasan  atau aturan  penjadwalan  di  rumah  sakit  dapat  terpenuhi  dengan  dicapainya  hasil  nilai f itness yang optimal.

## 5. KESIMPULAN
Dengan  menerapkan  metode  Algoritma  Genetika  dalam  sistem  penjadwalan komputasi, maka proses penjadwalan perawat akan menjadi lebih mudah dan efektif
dibandingkan  dengan  proses  penjadwalan  secara  manual.  Waktu  yang  dibutuhkan untuk  penyelesaian  hasil  penjadwalan  juga  relatif  singkat  sehingga  lebih  efisien dibandingkan dengan proses penjadwalan secara manual.

## DAFTAR PUSTAKA
[1]   Goldberg,D.E (1989). Genetic Algorithm in Search, Optimization, and Machine Learning , Addition Wesley Publishing Company, Inc, USA.
[2]   Praptiningsih,  Sri.  (2006). Kedudukan  Hukum  Perawat  dalam  Upaya Pelayanan Kesehatan di Rumah Sakit . Raya Grafinda Persada, Jakarta.
[3]   Suyanto (2005). Algoritma Genetika dalam Matlab . Penerbit Andi. Yogyakarta.
[4]   Suyanto  (2007). Artificial  Intelligence,  Searching,  Reasoning,  Planning  and Learning . Penerbit Informatika, Bandung.
[5]   Syadid,  Muhammad  (2008). Penjadwalan  Perkuliahan  Menggunakan Algoritma Genetika . Jurusan Ilmu Komputer. Fakultas MIPA Institut Pertanian Bogor (IPB). Bogor.
[6]   Tim  Penyusun  Kamus  Pusat  Pembinaan  dan  Pengembangan  Bahasa  Kamus Besar Bahasa Indonesia (1997). Kamus Besar Bahasa Indonesia . Departemen Pendidikan dan Kebudayaan, Balai Pustaka. Jakarta.
[7]  Widyastuti,  Novandry,  dkk.  (2008) .  Optimasi  Penjadwalan  Kegiatan  Belajar Mengajar dengan Algoritma Genetik. Jurusan Matematika. Universitas Sebelas Maret. Surakarta .
(Halaman ini sengaja dikosongkan)