This paper constructs a two-stage mathematical programming model to solve the nurse scheduling problem in order to assign nurses to shifts over a scheduling period so that certain constraints (organizational and personal) are satisfied. In the first stage, the nurse optimal vacation schedules are solved by a self-schedule programming that can check for any violation of government regulations, hospital management requirements, and scheduling fairness. In the second stage, the nurse roster schedule is arranged and a Genetic Algorithm (GA) is further adopted to derive the optimal schedule. An empirical case study is performed and the results show that the proposed approach can solve the nurse scheduling problem efficiently. In addition, it can also be easily modified to suit different cases encountered in hospitals.