×

Solving employee timetabling problems by generalized local search. (English) Zbl 0970.68678

Lamma, Evelina (ed.) et al., AI*IA 99: Advances in artificial intelligence. 6th congress of Italian Association for Artificial Intelligence. Bologna, Italy, September 14-17, 1999. Selected papers. Berlin: Springer. Lect. Notes Comput. Sci. 1792, 380-389 (2000).
Summary: Employee timetabling is the operation of assigning employees to tasks in a set of shifts during a fixed period of time, typically a week. We present a general definition of employee timetabling problems (ETPs) that captures many real world problem formulations and includes complex constraints. We investigate the use of several local search techniques for solving ETPs. In particular, we propose a generalization of local search that makes use of a novel search space that includes 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 instances. According to our experimental results on various local search techniques, generalized local search is the best method for solving targe ETP instances.
For the entire collection see [Zbl 0935.00047].

MSC:

68U99 Computing methodologies and applications
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite