Employee timetabling is the operation of assigning employees to tasks in a set of shifts during a flxed period of time, typically a week, We present a general definition of employee timetabling problems (ETPS0 that captures many real world problem formulations and includes complex constraints. We investigate the use of several local serach techniques for solving ETPs. In particular, we propose a generalization of local search that makes use of a nvel search space that in-cludes also partial assignments. We describe the distinguishing features of this generalized local search that allows it to navigate the search space effectively. We show that, on large and difficult instances of real world ETPs, where systematic search fails, local search methods perform well and solve the hardest in-stances. According to our experimental results on various local search techniques, generalized local search is the best method for solving large ETP instances.
展开▼
