Abstract: Penjadwalan kerja perawat khususnya keperawatan dirumah sakit sering menjadi suatu masalah yang dihadapi oleh setiap rumah sakit. Hal ini dikarenakan banyaknya persoalan dan adanya batasan-batasan yang harus dipenuhi. Selama ini RSUD Drs. H. Amri Tambunan masih menggunakan cara manual dalam menyusun jadwal kerja perawat sehingga sering mengalami kesulitan dan jadwal kerja yang dihasilkan pun masih belum merata dan teratur. Permasalahan penjadwalan ini dapat diselesaikan dengan pewarnaan simpul graf.iSalah satu algoritma untuk menyelesaikan masalah pewarnaan verteks graf pada penjadwalan adalah Algoritma Tabu Search. Algoritma Tabu Search adalah salah satu metode pemecahan permasalahan optimasi kombinatorial. Metode ini bertujuan untuk mengefektifkan proses pencarian solusi terbaik dari suatu permasalahan. Maka dapat diperoleh kesimpulan bahwa Algoritma Tabu Search dapat diterapkan untuk menyelesaikan masalah penjadwalan perawat dirumah sakit, salah satunya di RSUD Drs. H. Amri Tambunan. Penerapan Pewarnaan simpul dengan menggunakan Algoritma Tabu Search menghasilkan penjadwalan perawat yang lebih efisien dimana tidak ada terjadi jadwal yang bentrok, artinya tidak ada perawat yang mendapat dua shift di hari yang sama.