Metaheuristics for handling Time Interval Coverage Constraints

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 still 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 organisational 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