The problem of finding a high quality timetable for personnel in a hospital ward has been addressed by many researchers, personnel managers, and schedulers over a number of years. Nevertheless, automated nurse rostering practice is not common yet in hospitals. Many head nurses are currently spending several days per month on constructing their rosters by hand. In recent years, the emergence of larger and more constrained problems has presented a real challenge because finding good quality solutions can lead to a higher level of personnel satisfaction and to flexible organizational procedures. Compared to many industrial situations ( where personnel schedules normally consist of stable periodic morning-day-night cycles) health care institutions often require more flexibility in terms of hours and shift types. The motivation for the research presented in this paper has been provided by real-world hospital administrators/schedulers and the approach that we describe has been implemented in over 40 hospitals in Belgium. This paper consists of two main contributions: modeling the real-world situation more accurately than has previously been done in the literature; and presenting and evaluating an efficient and effective tabu search procedure to solve these problems ( as represented in the real-world model).