Hospitals need to be staffed around the clock to ensure satisfactory care for all patients. To this end, a set of shifts is defined which are assigned to nurses in a work schedule. The nurse rerostering problem (NRRP) occurs when due to unforeseen circumstances some shifts become unassigned: one or more nurses are no longer able to work some of the shifts assigned to them. Changes must then be made to the existing schedule to ensure that the shift occupancy demand is once again satisfied. The number of changes should be minimized to disrupt nurses’ personal plans as little as possible. In this presentation, a heuristic solution method is proposed for the NRRP. The heuristic systematically searches the solution space and estimates the solution quality using the assignment problem.