INNOVATIVE: Journal Of Social Science Research Volume 4 Nomor 2 Tahun 2024 Page 3358-3369 E-ISSN 2807-4238 and P-ISSN 2807-4246
Website: https://j-innovative.org/index.php/Innovative
Penerapan Pewarnaan Graf dalam Penjadalan Kerja Menggunakan Algoritma Welch-Powell
(Studi Kasus: Rumah Sakit Grand Medistra Lubuk Pakam)
Rizki Khoiriah Harahap 1 ✉ , Nerli Khairani 2
Universitas Negeri Medan
Email: riskikhoiriyah19@gmail.com 1 ✉

## Abstrak
Permasalahan penjadwalan sering terjadi di instansi yang bergerak dibidang pelayanan, salah satunya Rumah  Sakit.  Penyusunan  jadwal  yang  dilakukan  secara  manual  mengakibatkan  sering  terjadinya kesalahan.  Kesalahan  tersebut  seperti  terjadinya  tumpang  tindih  jadwal  antar  perawat,  sehingga  ini menyebabkan  kekosongan  perawat  dishift  lain.  Penjadwalan  juga  seharusnya  dapat  menyesuaikan terhadap keadaan yang tak terduga, seperti suatu keadaan pasien darurat yang membutuhkan perawat dengan suatu kriteria yang khusus. Sehingga, penjadwalan pada rumah sakit ini seharusnya memenuhi semua kriteria yang dibutuhkan pada suatu ruangan untuk  mengatasi keadaan darurat tersebut. Ini bertujuan untuk memberikan cara alternatif penyusunan jadwal yang menghindari terjadinya tumpang tindih jadwal antar perawat, dan memenuhi semua kriteria perawat yang dibutuhkan. Metode yang digunakan dengan teknik pewarnaan graf dengan menggunakan algoritma Welch-Powell. Hasil yang diperoleh  dengan  menerapkan  algoritma Welch-Powell  pada  pewarnaan  simpul  pada  graf menghasilkan  penjadwalan  perawat  yang lebih    efisien  dengan  meminimalkan  terjadi  lagi  tumpang tindih  jadwal antar  perawat, dan  memastikan    kriteria  yang dibutuhkan  pada  setiap  ruangan  sudah terpenuhi untuk menghadapi suatu keadaan yang tak terduga terjadi.
Kata Kunci: Penjadwalan, Rumah Sakit, Graf, Pewarnaan Graf, Algoritma Welch-Powell

## Abstract
Scheduling problems often occur in agencies engaged in services, one of which is a hospital. Manual schedule  preparation  results  in  frequent  errors.  Such  errors  include  overlapping  schedules  between nurses, so that this causes vacancies for nurses in other shifts. Scheduling should also be able to adjust to unforeseen circumstances, such as an emergency patient situation that requires a nurse with a specific criteria. Thus, scheduling in this hospital should fulfill all the criteria needed in a room to overcome the emergency.  It  aims  to  provide  an  alternative  way  of  preparing  schedules  that  avoid  overlapping schedules between nurses, and meet all the criteria for nurses needed. The method used is a graph coloring  technique  using  the  Welch-Powell  algorithm.  The  results  obtained  by  applying  the  Welch- Powell algorithm to the coloring of the vertices on the graph produce a more efficient scheduling of nurses by minimizing overlapping schedules between nurses, and ensuring the criteria needed in each room are met to deal with an unexpected situation.
Keywords: Scheduling, Hospital, Graph, Graph Coloring, Welch-Powell Algorithm

## PENDAHULUAN
Penyusunan jadwal sangat diperlukan untuk membantu mengatur jalannya aktivitas kegiatan. Suatu pekerjaan dapat berlangsung secara efektif dengan adanya penjadwalan. Karena  penjadwalan  dapat  membantu  aktivitas  sehari-hari  dalam  menjalankan  kegiatan rutin  yang  tersusun  secara  rapi  (Yustina,  2019).  Banyak  jenis  masalah  penjadwalan  yang sering kita temui dalam kehidupan sehari-hari, salah satunya adalah masalah penjadwalan kerja. Penjadwalan kerja merupakan sebuah penjadwalan yang dilakukan untuk membantu pekerja melakukan tugas mereka secara efektif. Agar pekerja bekerja sesuai dengan jadwal yang  sudah  ditetapkan,  maka  dilakukan  penyusunan  jadwal  kerja  sebelum  pekerjaan berlangsung (Damanik, 2020).
Penyusunan  jadwal kerja  sangat  dibutuhkan  oleh suatu  perusahaan yang bergerak dibidang  pelayanan.  Salah  satunya  adalah  rumah  sakit.  Rumah  sakit  merupakan  suatu instansi yang bergerak dibidang pelayanan kesehatan bagi masyarakat dengan karakteristik tersendiri. Banyaknya jumlah orang yang bekerja di rumah sakit tersebut, diperlukan adanya penjadwalan jam kerja agar dapat melakukan pekerjaan dengan baik. Oleh karena itu, setiap rumah sakit selalu mengatur jadwal jam kerja di setiap ruangan untuk memastikan bahwa setiap pasien mendapatkan pelayanan secara baik, salah satunya yaitu Rumah Sakit Grand Medistra Lubuk Pakam.
Proses penyusunan jadwal kerja yang dilakukan setiap kepala ruangan di rumah sakit ini masih dilakukan secara manual. Dalam melakukan penyusunan jadwal secara manual ini membutuhkan  waktu  yang  cukup  lama,  dan  tidak  jarang  hasil  yang  diperoleh  terdapat kesalahan. Kesalahan yang terjadi seperti terjadinya tumpang tindih antar jadwal perawat.
Tumpang tindih  ini mengakibatkan kurangnya  perawat  dengan kriteria yang dibutuhkan pada shift lain, sehingga menyebabkan kekosongan dalam jadwal shift. Apabila tumpang tindih ini terjadi pada jadwal, kepala ruangan diharuskan untuk mengubah jadwal kembali dari awal yang membutuhkan waktu cukup lama. Sering terjadi keadaan yang tak terduga pada  rumah  sakit,  seperti  suatu  keadaan  pasien  darurat  yang  membutuhkan  perawat dengan suatu kriteria yang khusus. Sehingga, penjadwalan pada rumah sakit ini seharusnya memenuhi semua kriteria yang dibutuhkan pada suatu ruangan untuk mengatasi keadaan darurat tersebut.  Oleh karena itu, untuk mempermudah proses penyusunan jadwal ini yang menghindari  tumpang  tindih  antar  perawat  dan  untuk  memenuhi  semua  kriteria  yang dibutuhkan dalam suatu ruangan dapat menggunakan konsep teori pewarnaan simpul pada graf dengan algoritma Welch-Powell.
Pewarnaan simpul adalah jenis pewarnaan graf yang banyak digunakan. Pewarnaan simpul adalah proses memberikan setiap pasangan simpul yang terhubung dalam sebuah graf  sebuah  warna  yang  unik.  Bilangan  kromatik  adalah  jumlah  minimum  warna  yang dibutuhkan untuk pewarnaan.
Teori  graf  dapat  digunakan  untuk  menyelesaikan  masalah  penjadwalan  dengan menggunakan  beberapa  teknik,  diantaranya  adalah  Algoritma  Tabu  Search,  Algoritma Backtracking,  Algoritma  Welch  Powell,  dan  lain-lain.  Algoritma  yang  digunakan  dalam penelitian ini adalah Algoritma Welch Powell. Algoritma Welch Powell merupakan salah satu teknik  pewarnaan  graf  yang  mewarnai  graf  sesuai  dengan  derajat  terbesar  dari  simpul- simpulnya. Metode Welch Powell memiliki beberapa kelebihan, diantaranya prosedur yang lebih sederhana dan mudah digunakan untuk penyusunan penjadwalan (Munir, 2014).
Beberapa  penelitian  terdahulu  telah  melakukan  penelitian  terkait  penerapan pewarnaan graf dengan algoritma Welch-Powell seperti (Rusdiana & Mulviani, 2019) yang menerapkannya pada penjadwalan perkuliahan. Selanjutnya penelitian Dina Ulfa Mahfuza dan Mulyono (2020) yang melakukan penerapan pada keefektivan pengaturan lampu lalu lintas. Dan selanjutnya penerapan pada dokter spesialis yang dilakukan oleh Ade Novita, dkk pada tahun (2022). Hasil penelitian terdahulu tersebut rata-rata menyimpulkan bahwa penerapan pewarnaan graf dengan algoritma welch-powell dapat menghasilkan hasil yang memecahkan permasalah  tersebut.
Berdasarkan paparan penelitian terdahulu di atas, pewarnaan graf dengan algoritma welch-powell telah berhasil dilakukan pada beberapa bidang. Namun, belum banyak yang melakukan penerapan  penjadwalan pada perawat  dengan teori  pewarnaan  graf dengan algoritma welch-powell.

## METODE PENELITIAN
Tempat penelitian ini bertempat di Rumah Sakit Grand Medistra Lubuk Pakam. Rumah sakit ini berlokasi di Jalan Raya Medan – Lubuk Pakam KM.25 No.66 Kel, Petapahan, Kec. Lubuk Pakam, Kabupaten Deli Serdang. Populasi dari penelitian ini adalah perawat yang bekerja di Rumah Sakit Grand Medistra Lubuk Pakam. Sedangkan sampel yang digunakan dalam  ini  adalah  perawat  yang  berada  di  ruang  laboratorium,  ruang  IGD,  ruang  CVCU, ruang ICU, dan ruang HDU .
Jenis  penelitian  yang  digunakan  dalam  penelitian  ini  adalah  penelitian  kuantiatif dengan metode studi kasus. Dimana,  penelitian  ini dilakukan untuk mendapatkan  solusi yang  dapat  diaplikasikan  pada  perusahaan  dalam  keperluan  penjadwalan  perawat.  Data yang digunakan adalah data dari kepala ruangan, yaitu dari ruang ICU, ruang CVCU, ruang IGD, ruang laboratorium dan ruang HDU.
Agar  langkah penelitian yang dilakukan sistematis dan efisien,  diperlukan prosedur penelitian.  Prosedur  penelitian  digunakan  sebagai  landasan  untuk  melakukan  penelitian. Langkah-langkah yang digunakan yaitu :
1. Mengkaji studi literatur mengenai pewarnaan graf.
2. Mengumpulkan data (nama-nama) dan kriteria yang dimiliki perawat disetiap ruangan.
3. Mengelompokkan perawat berdasarkan kriteria yang sama yang dimiliki perawat.
4. Merepresentasikan  simpul  sebagai  perawat  dan  sisi  akan  merepresentasikan hubungan  antar  perawat  dengan  kriteria  yang  sama.  Sehingga  dapat  diketahui hubungan simpul dari garis terhubung.
5. Membuat matriks ketetanggaan untuk melihat keterhubungan antar perawat, dimana jika antar perawat memiliki kriteria yang sama diberi nilai 1, jika tidak diberi nilai 0.
6. Mengimplementasikan algoritma Welch-Powell untuk melakukan pewarnaan simpul pada penjadwalan kerja di rumah sakit. Pewarnaan simpul dengan algoritma welch- powell ini dilakukan secara manual.
7. Memperoleh  hasil penjadwalan  dari pewarnaan graf yang  dilakukan menggunakan algoritma Welch-Powell sesuai pembagian shift pada rumah sakit.
8. Menarik kesimpulan.

## HASIL DAN PEMBAHASAN
Populasi  dari  penelitian  ini  adalah  perawat  yang  bekerja  di  Rumah  Sakit  Grand Medistra Lubuk Pakam. Sedangkan sampel yang digunakan dalam ini adalah perawat yang berada di ruang laboratorium, ruang IGD, ruang CVCU, ruang ICU, dan ruang HDU .
Kepala  ruangan  diwawancarai  secara  langsung  sebagai  bagian  dari  proses pengumpulan data. Hasil wawancara menunjukkan bahwa perawat di Rumah Sakit Grand Medistra Lubuk Pakam ditugaskan dalam empat shift kerja yang berbeda: shift pagi, yang berlangsung dari pukul 07.00 hingga 14.00 WIB, shift sore, yang berlangsung dari pukul 14.00 hingga 21.00 WIB, shift malam, yang berlangsung dari pukul 21.00 hingga 07.00 WIB, dan shift  lepas malam, yaitu saat perawat beristirahat setelah  bekerja pada shift malam. Dalam ruang ICU terdapat 20 perawat, ruang CVCU erdapat 18 perawat, ruang IGD terdapat 33 perawat IGD, ruang LAB terdapat 26 perawat, dan di ruang HDU terdapat 20 perawat.

## 1. Ruang ICU
Perawat  di  ruang  ICU  berjumlah  20  perawat  yang  terdiri  dari  kepala  ruangan, Perawatan Pasien Utama (PPU), dan Perawatan Pasien Kritis (PPK). Pekerjaan kelompok kerja ini akan diselesaikan dalam urutan shift pagi, sore, malam dan lepas malam. Oleh karena itu,  empat  kelompok  akan  dibuat  untuk  penjadwalan  perawat  sesuai  dengan  peraturan. Pembagian  kelompok  ini  akan  dilakukan  untuk  19  perawat  yang  tersisa,  karena  kepala ruangan hanya bekerja pada shift pagi.
Tabel 1. Pembagian Kelompok Ruang ICU Kelompok Kriteria Perawat 1 Senior, PPU P 2 , P 3 , P 13 , P 14 , P 20 2 Junior, PPU P 5 , 𝑃 8 , 𝑃 10 , 𝑃 17 , 𝑃 18 3 Senior, PPK 𝑃 6 , 𝑃
7 , 𝑃 9 , 𝑃 16 , 𝑃 19 4 Junior, PPK 𝑃 4 , 𝑃 11 , 𝑃 12 , 𝑃 15
Selanjutnya dibuat matriks ketetanggaan yang mana baris ke-i dan kolom ke-j disebut perawat. Baris dan kolom diberi nilai 1 jika perawat berhubungan dan diberi nilai 0 jika tidak berhubungan. Lalu dibangun sebuah graf yang merepresentasikan simpul dan sisi tersebut, dan dilakukan pewarnaan simpul.
Gambar 1. Pewarnaan Simpul Ruang ICU
Dari pewarnaan simpul pada graf di atas diperoleh hasil sebagai berikut :

## Tabel 2. Hasil Pewarnaan Graf ruang ICU
Dari hasil pewarnaan di atas, maka diperoleh hasil penjadwalan yang telah memenuhi aturan  setiap  ruangan  yang  memiliki  lima  kelompok  kerja,  dimana  nantinya  empat kelompok pertama bekerja sesuai pergantian shift, yaitu shift pagi, sore, malam dan lepas malam. Dan satu kelompok warna terakhir menjadi kelompok pertahanan, yang bertugas menggantikan perawat yang berhalangan hadir.

## 2. Ruang CVCU
Perawat  di  ruang  CVCU  berjumlah  18  perawat  yang  terdiri  dari  kepala  ruangan, Perawatan  Pasien  Post  Catheterisasi  Jantung  (PCI),  dan  Perawatan  Pasien  Kritis  (PPK). Pekerjaan kelompok kerja ini akan diselesaikan dalam urutan shift pagi, sore, malam dan lepas malam. Oleh karena  itu, empat kelompok akan dibuat untuk penjadwalan perawat sesuai dengan peraturan. Pembagian  kelompok akan diterapkan untuk 17 perawat yang tersisa, karena kepala ruangan hanya dipekerjakan selama shift pagi.
Tabel 3. Pembagian Kelompok Ruang CVCU Kelompok Kriteria Perawat 1 Senior, PCI P 2 , P 3 , P 10 , P 15 2 Junior, PCI P 5 , 𝑃 6 , 𝑃 7 , 𝑃 12 3 Senior, PPK 𝑃 4 , 𝑃 8 , 𝑃 9 , 𝑃 11 , 𝑃 13 4 Junior, PPK 𝑃 14 , 𝑃 16 , 𝑃 17 , 𝑃 18
Warna Merah Kuning Hijau Biru Hitam Perawat (P) 𝑃 2 , 𝑃 4 , 𝑃 5 , 𝑃 6 𝑃 3 , 𝑃 7 , 𝑃 8 , 𝑃 11 𝑃 9 , 𝑃 10 , 𝑃 12 , 𝑃 13 𝑃 14 , 𝑃 15 , 𝑃 16 , 𝑃 17 𝑃 18 , 𝑃 19 , 𝑃 20
Selanjutnya dibuat matriks ketetanggaan yang mana baris ke-i dan kolom ke-j disebut perawat. Baris dan kolom diberi nilai 1 jika perawat berhubungan dan diberi nilai 0 jika tidak berhubungan. Lalu dibangun sebuah graf yang merepresentasikan simpul dan sisi tersebut, dan dilakukan pewarnaan simpul.

## Gambar 2. Pewarnaan Simpul Ruang CVCU
Dari pewarnaan simpul pada graf di atas diperoleh hasil sebagai berikut :

## Tabel 4. Hasil Pewarnaan Simpul Graf Ruang CVCU
Dari hasil pewarnaan di atas, maka diperoleh hasil penjadwalan yang telah memenuhi aturan  setiap  ruangan  yang  memiliki  lima  kelompok  kerja,  dimana  nantinya  empat kelompok pertama bekerja sesuai pergantian shift, yaitu shift pagi, sore, malam dan lepas malam. Dan satu kelompok warna terakhir menjadi kelompok pertahanan, yang bertugas menggantikan perawat yang berhalangan hadir.

## 3. Ruang IGD
Perawat di ruang IGD berjumlah 33 perawat yang terdiri dari kepala ruangan, Triange, Perawatan Gawat Darurat (PGD), dan Observasi dan Monitoring. Pekerjaan kelompok kerja ini akan dilakukan dalam urutan shift pagi, sore, malam dan lepas malam.  Dengan demikian, empat kelompok akan dibuat untuk penjadwalan perawat sesuai dengan peraturan. Namun demikian,  32  perawat  lainnya  akan  dibagi  menjadi  beberapa  kelompok  karena  kepala ruangan hanya bekerja pada shift pagi.
Warna Merah Kuning Hijau Biru Hitam Perawat (P) 𝑃 2 , 𝑃 4 , 𝑃 5 , 𝑃 14 𝑃 3 , 𝑃 6 , 𝑃 8 , 𝑃 16 𝑃 7 , 𝑃 9 , 𝑃 10 , 𝑃 17 𝑃 11 , 𝑃 12 , 𝑃 15 , 𝑃 18 𝑃 13

## Tabel 5. Pembagian Kelompok Ruang IGD
Kelompok Kriteria Perawat 1 Senior, Observasi & monitoring P 2 , P 6 , P 18 , P 20 , P 30 2 Junior, Observasi & monitoring P 8 , 𝑃 13 , 𝑃 14 , 𝑃 23 , 𝑃 29 3 Senior, Triange 𝑃 3 , 𝑃 7 , 𝑃 12 , 𝑃 17 , 𝑃 26 , 𝑃 28 4 Junior, Triange 𝑃 5 , 𝑃 10 , 𝑃 21 , 𝑃 25 5 Senior, PGD 𝑃 9 , 𝑃 19 , 𝑃 27 , 𝑃 32 , 𝑃 24 6 Junior, PGD 𝑃 4 , 𝑃 11 , 𝑃 15 , 𝑃 16 , 𝑃 22 , 𝑃 31
Selanjutnya dibuat matriks ketetanggaan yang mana baris ke-i dan kolom ke-j disebut perawat. Baris dan kolom diberi nilai 1 jika perawat berhubungan dan diberi nilai 0 jika tidak berhubungan. Lalu dibangun sebuah graf yang merepresentasikan simpul dan sisi tersebut, dan dilakukan pewarnaan simpul.

## Gambar 3. Pewarnaan Simpul Ruang IGD
Dari pewarnaan simpul pada graf di atas memperoleh hasil yaitu :
Tabel 6. Hasil Pewarnaan Simpul Graf Ruang IGD Warna Merah Kuning Hijau Biru Ungu Hitam Perawat (P) 𝑃 2 , 𝑃 3 , 𝑃 4 , 𝑃 5 , 𝑃 8 , 𝑃 9 𝑃 6 , 𝑃 7 , 𝑃 10 , 𝑃 11 , 𝑃 13 , 𝑃 19 𝑃 12 , 𝑃 14 , 𝑃 15 , 𝑃 18 , 𝑃 21 , 𝑃 27 𝑃 16 , 𝑃 17 , 𝑃 20 , 𝑃 23 , 𝑃 25 , 𝑃 17 𝑃 22 , 𝑃 24 , 𝑃 26 , 𝑃 29 , 𝑃 30 𝑃 18 , 𝑃 19 ,
𝑃 20
Dari hasil pewarnaan di atas, maka diperoleh hasil penjadwalan yang telah memenuhi aturan  setiap  ruangan  yang  memiliki  lima  kelompok  kerja,  dimana  nantinya  empat kelompok pertama bekerja sesuai pergantian shift, yaitu shift pagi, sore, malam dan lepas
malam. Dan satu kelompok warna terakhir menjadi kelompok pertahanan, yang bertugas menggantikan perawat yang berhalangan hadir.

## 4. Ruang LAB
Perawat  di  ruang  LAB  berjumlah  26  perawat  yang  terdiri  dari  kepala  ruangan, sampling, cek hasil, dan pemeriksaan awal. Pekerjaan kelompok kerja ini akan diselesaikan dalam  urutan  shift  pagi,  sore,  malam  dan  lepas  malam.  Menurut  pedoman  yang  telah ditetapkan,  penjadwalan  perawat  akan  dibagi  menjadi  empat  kelompok.  Pembagian kelompok ini akan diterapkan untuk 25 perawat yang tersisa, karena kepala ruangan hanya dipekerjakan pada shift pagi.
Tabel 7. Pembagian Kelompok Ruang LAB Kelompok Kriteria Perawat 1 Senior, Sampling P 2 , P 8 , P 22 , P 23 2 Junior, Sampling
P 13 , 𝑃 16 , 𝑃 17 , 𝑃 20 , 𝑃 26 3 Senior, Cek Hasil 𝑃 4 , 𝑃 5 , 𝑃 6 , 𝑃 18 , 𝑃 21 4 Junior, Cek Hasil 𝑃 11 , 𝑃 12 , 𝑃 14 , 𝑃 25 5 Senior 𝑃 3 , 𝑃 9 , 𝑃 10 , 𝑃 19 6 Junior 𝑃 7 , 𝑃 15 , 𝑃 24
Selanjutnya dibuat matriks ketetanggaan yang mana baris ke-i dan kolom ke-j disebut perawat. Baris dan kolom diberi nilai 1 jika perawat berhubungan dan diberi nilai 0 jika tidak berhubungan. Lalu dibangun sebuah graf yang merepresentasikan simpul dan sisi tersebut, dan dilakukan pewarnaan simpul.
Gambar 4. Pewarnaan Simpul Ruang LAB
Dari pewarnaan simpul pada graf di atas memperoleh hasil yaitu :

## Tabel 8. Hasil Pewarnaan Simpul Graf Ruang LAB
Warna Merah Kuning Hijau Biru Hitam Perawat (P) 𝑃 2 , 𝑃 3 , 𝑃 4 , 𝑃 7 , 𝑃 13 𝑃 5 , 𝑃 8 , 𝑃 9 , 𝑃 12 , 𝑃 15 , 𝑃 16 𝑃 6 , 𝑃 10 , 𝑃 14 , 𝑃 17 , 𝑃 22 , 𝑃 24 𝑃 18 , 𝑃 19 , 𝑃 20 , 𝑃 23 , 𝑃 25 𝑃 21 , 𝑃 26
Dari hasil pewarnaan di atas, maka diperoleh hasil penjadwalan yang telah memenuhi aturan  setiap  ruangan  yang  memiliki  lima  kelompok  kerja,  dimana  nantinya  empat kelompok pertama bekerja sesuai pergantian shift, yaitu shift pagi, sore, malam dan lepas malam. Dan satu kelompok warna terakhir menjadi kelompok pertahanan, yang bertugas menggantikan perawat yang berhalangan hadir.

## 5. Ruang HDU
Perawat  di  ruang  HDU  berjumlah  20  perawat  yang  terdiri  dari  kepala  ruangan, Pengawasan  dan  Pemantauan  Pasien,  dan  Pengelolaan  Peralatan  Medis.  Pekerjaan kelompok kerja ini akan diselesaikan dalam urutan shift pagi, sore, malam dan lepas malam. Dengan demikian, empat kelompok akan dibuat untuk penjadwalan perawat sesuai dengan pedoman yang ditetapkan. Pembagian kelompok akan dilakukan untuk 19 perawat yang tersisa, karena kepala ruangan hanya bekerja pada shift pagi.
Tabel 9. Pembagian Kelompok Ruang HDU Kelompok Kriteria Perawat 1 Senior, PPM P 11 , P 13 , P 14 , P 18 2 Junior, PPM P 4 , 𝑃
6 , 𝑃 7 , 𝑃 10 , 𝑃 17 3 Senior, P3 𝑃 2 , 𝑃 5 , 𝑃 8 , 𝑃 9 , 𝑃 16, 𝑃 19, 𝑃 20 4 Junior, P3 𝑃 3 , 𝑃 12 , 𝑃 15
Selanjutnya dibuat matriks ketetanggaan yang mana baris ke-i dan kolom ke-j disebut perawat. Baris dan kolom diberi nilai 1 jika perawat berhubungan dan diberi nilai 0 jika tidak berhubungan. Lalu dibangun sebuah graf yang merepresentasikan simpul dan sisi tersebut, dan dilakukan pewarnaan simpul.
Gambar 5. Pewarnaan Simpul Ruang HDU
Dari pewarnaan simpul pada graf di atas diperoleh hasil sebagai berikut :

## Tabel 10. Pembagian Kelompok Ruang HDU
Dari hasil pewarnaan di atas, maka diperoleh hasil penjadwalan yang telah memenuhi aturan  setiap  ruangan  yang  memiliki  lima  kelompok  kerja,  dimana  nantinya  empat kelompok pertama bekerja sesuai pergantian shift, yaitu shift pagi, sore, malam dan lepas malam. Dan satu kelompok warna terakhir menjadi kelompok pertahanan, yang bertugas menggantikan perawat yang berhalangan hadir.

## SIMPULAN
Berdasarkan hasil penelitian yang telah dilakukan, dapat disimpulkan bahwa teknik pewarnaan  graf  pada  simpul  dengan  menerapkan  algoritma Welch-Powell  dapat dilakukan pada penyusunan penjadwalan perawat di Rumah Sakit. Dimana, penjadwalan nantinya  akan  meminimalkan  tumpang  tindih  jadwal  antar  perawat,  dan  penjadwalan telah memenuhi aturan pada setiap ruangan dengan kriteria yang telah ditetapkan.
Dari  hasil  penjadwalan  di  atas,  keempat  kelompok  kerja  di  atas  nantinya  akan bekerja  sesuai  shift  yang  telah  ditentukan.  Penjadwalan  di  atas  akan  meminimalkan terjadinya  tumpang  tindih  jadwal  antar  perawat,  sehingga  tidak  terjadi  kekosongan perawat di shift lain. Hasil penjadwalan di atas juga membuktikan bahwa sudah terpenuhi semua  kriteria  yang  dibuuthkan  oleh  suatu  ruangan,  sehingga  tidak  terjadi  lagi
Warna Merah Kuning Hijau Biru Hitam Perawat (P) 𝑃 2 , 𝑃 3 , 𝑃 4 , 𝑃 11 𝑃 5 , 𝑃 6 , 𝑃 12 , 𝑃 13 𝑃 7 , 𝑃 8 , 𝑃 14 , 𝑃 15 𝑃 9 , 𝑃 10 , 𝑃 18 , 𝑃 20 𝑃 16 , 𝑝 17 , 𝑝 19
kekurangan kriteria yang dibutuhkan pada suatu.

## DAFTAR PUSTAKA
Damanik, R. R. (2020). Aplikasi Penjadwalan Perawat Rs Porsea Menggunakan Algoritma Genetika. Journal  Information  System  Development  … , 5(1),12 – 18. https://ejournal.medan.uph.edu/index.php/isd/article/view/405
Yustina, Amelia. & dkk. (2019). Penerapan Metode Pewarnaan Graf untuk Penjadwalan Mata Kuliah . Jurnal Media Informatika Budidarma. 3(3), 153-158.
Munir, R. (2012). Matematika Diskrit, Edisi Kelima. Bandung: Penerbit Informatika.
Rusdiana, Y., & Maulani, A. (2019). Algoritma Welch-Powell Untuk Pewarnaan Graf pada Penjadwalan Perkuliahan. Science and Physics Education Journal (SPEJ), 3(1), 37 – 47. https://doi.org/10.31539/spej.v3i1.915
Mahfuza, D. U., & Mulyono. (2020). Penerapan Pewarnaan Graf Menggunakan Algoritma Welch- Powell Untuk Keefektifan Pada Pengaturan Lampu Lalu Lintas. Karismatika, 6(2), 52 – 65.
Andriani, A. N., Tonis, M., & Zaky, A. (2022). Optimization of Emergency Installation Doctor Practice  Scheduling  Using  Graph  Coloring  Method  in  Petala  Bumi  Hospital  Riau Province Optimasi Penjadwalan Praktek Dokter Instalasi Gawat. 3(2), 1 – 8.
Chartrand, G., Lesniak, L., & Zhang, P. (2010). Graphs & digraphs. In Graphs and Digraphs. https://doi.org/10.1201/b19731
Rahayuningsih,  S.  (2018).  Teori  Graph  dan  Penerapanya. Program  Studi  Pendidikan Matematika IKIP Budi Utomo Malang, 1 – 151.