Penerapan Pewarnaan Graf pada Penjadwalan Kerja Menggunakan Metode Largest Degree Ordering (LDO): Studi Kasus

Natalia Lumban Tobing (Universitas Negeri Medan)
Arnah Ritonga (Universitas Negeri Medan)

Catha : Jurnal Penelitian Kreatif dan Inovatif
Vol. 3 No. 3 (2026): In-Progress

Penjadwalan kerja perawat merupakan aspek penting dalam operasional rumah sakit untuk menjamin kelancaran pelayanan dan meningkatkan kualitas perawat pasien.  Namun, proses penyusunan jadwal kerja di RSUD Dr.  Tengku Mansyur Kota Tanjungbalai masih dilakukan secara manual. Sehingga berpotensi menimbulkan  konflik  jadwal  dan  kurang  efisien. Penelitian  ini  bertujuan untuk menerapkan metode pewarnaan graf dalam penjadwalan kerja perawat dengan  menggunakan  algoritma  Largest  Degree  Ordering  (LDO).  Pewarnaan graf digunakan untuk meminimalkan konflik antar jadwal, sedangkan algoritma LDO dipilih karena kesederhanaan dan efektivitasnya dalam menyelesaikan permasalahan penjadwalan. Implementasi algoritma LDO dilakukan menggunakan perangkat lunak Pyhton untuk mensimulasikan penjadwalan kerja perawat di ruang Perinatologi, Obgyn, IGD, Bedah dan Anak. Hasil penelitian menunjukkan bahwa penerapan algoritma LDO mampu menghasilkan penjadwalan kerja perawat yang memenuhi aturan pada setiap ruangan tanpa terjadi benturan jadwal.   Dengan demikian, metode pewarnaan graf menggunakan algoritma LDO dapat menjadi solusi alternatif yang efektif dan efisien dalam penyusunan jadwal kerja di RSUD Dr.   Tengku Mansyur Kota Tanjungbalai serta berkontribusi pada peningkatan kualitas pelayanan rumah sakit.