COMBINING RULES AND CONSTRAINTS FOR EMPLOYEE TIMETABLING

Employee Timetabling Problems (ETP) are all around us. One possible ap proach for solving ETPs is to use constraint processing techniques. An other approach is to model human knowledge which is commonly used for solving such problems into knowledge-based systems for timetabling. It is difficult to represent the complex constraints of timetabling expl icitly in constraint networks. On the other hand, knowledge-based repr esentations of constraints are implicit and cannot support most of the heuristics of constraint-based processing that have been developed ov er the last decade. The present article presents an approach to repres enting and processing employee timetabling problems by a combination o f explicit representations of some constraints and rule-based processi ng with heuristics for generic ETP constraints. This mixed-mode approa ch has been implemented in the form of a software package for defining and solving real-world ETPs. A general description of the design and organization of this software tool is given. Results for solving a typ ical real-world employee timetabling problem are presented and a compa rison with the use of standard CSP (Constraint Satisfaction Problems) techniques is made. (C) 1997 John Wiley & Sons, Inc.