[Back]

W. Slany:
"Theory and practice of the shift design problem";
Talk: 4^th international conference on the Practice And Theory of Automated Timetabling, Gent, Belgium (invited); 08-21-2002 - 08-23-2002; in: "Proc. of the 4^th international conference on the Practice And Theory of Automated Timetabling (PATAT 2002)", E. Burke, P. DeCausmaecker (ed.); Kaho, Gent, Belgien (2002), ISBN: 90-806096-1-7; 53 - 56.

Generating high-quality schedules for a rotating workforce is a critical task in all situations where a certain staffing level must be guaranteed, such as in industrial plants, hospitals, or airline companies. Shift scheduling comprises several problems, one of primordial importance being the shift design problem qhich is concerned with finding optimal starting times and lenghts of shifts. This problem presents an interesting challenge both from practical as well as theoretical points of view. We describe our results in both areas, stressing in particular how our quest for complexity results lead to improved practical algorithms which are now part of a successful commercial package.