This paper presents a methodology for solving the Nurse Rostering problem. A case study of a hospital located in the city of Barranquilla, Colombia, is considered, in which several conflicting factors guide the decision-making process. The methodology consists of looking for the best nurses rostering where the overtime is reduced and they are fulfilled the restrictions implanted by the hospital. A heuristic procedure is proposed that considers four of the thousand of restrictions that can be presented in similar problems.