Nurse Rostering Problem (NRP) merupakan permasalahan krusial di industri rumah sakit yang bersifat kombinatorial kompleks. NRP tergolong ke dalam masalah NP-Hard yang berarti belum terdapat algoritma pasti yang dapat menyelesaikan permasalahan tersebut hingga saat ini. Paper ini mengajukan penyelesaian NRP menggunakan pendekatan metaheuristik dengan reward-based pada tiap pergerakan pembangunan solusi parsialnya (RBMBCO). Data set yang digunakan adalah kasus penjadwalan untuk 30 perawat dengan rentang waktu penjadwalan untuk 4 minggu kerja pada The Second Internasional Nurse Rostering Competition (INRC-II) dataset. Dari penelitian yang dilakukan, solusi yang dibangun menggunakan RBMBCO menghasilkan solusi yang lebih baik dibandingkan dengan BCO standar.