Nurse scheduling in hospitals is important decision because it affects the quality of nurses’ working condition and so quality of care to patients. But by the fact that there are many complicated constraints and requirements for hospital nurse staffing and scheduling, nurse scheduling problem has been a difficult problem. In this paper we present solutions for nurse scheduling problem in two ways. First one is a heuristic algorithm of nurse scheduling which considers realistic conditions of hospitals with penalty cost minimization. Second one is rule-based heuristic algorithm which approaches reality very closely.