Solving Employee Timetabling Problems by Generalized Local Search
Solving Employee Timetabling Problems by Generalized Local Search
复制标题
DOI：
10.1007/3-540-46238-4_33
复制
发表时间：
1999-09
期刊：
影响因子：
--
通讯作者：
Andrea Schaerf;A. Meisels
中科院分区：
文献类型：
--
作者：
Andrea Schaerf;A. Meisels
员工时间表是在一段固定的时间内，通常是一周，以一组班次分配给员工的工作。我们给出了员工时间表问题(ETP)的一般定义，它涵盖了许多现实世界的问题公式，并包括复杂的约束条件。我们研究了几种局部搜索技术在求解ETPS中的应用。特别是，我们提出了一种局部搜索的推广，它利用了一种新的搜索空间，该空间也包括部分赋值。我们描述了这种广义局部搜索的显著特征，使其能够有效地在搜索空间中导航。我们证明，在系统搜索失败的真实世界ETP的大型和困难实例上，本地搜索方法表现良好，并解决最困难的实例。根据我们在各种局部搜索技术上的实验结果，广义局部搜索是解决大型ETP实例的最好方法。
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 large ETP instances.