can formal languages be usefull in
The challenge in shift scheduling lies in the construction of a set of work shifts, which are subject to specific regulations, in order to cover fluctuating staff demands. This problem becomes harder when multi-skill employees can perform many different activities during the same shift. In this presentation, we show how formal languages (such as regular and context-free languages) can be enhanced and used to model the complex regulations of the shift construction problem. From these languages we can derive 1) specialized graph structures that can be searched efficiently 2) MIP models that are much easier to solve (and sometime even possess integer vertices!) 3) Constraint Programming based Column Generation taking advantage of powerful Global Constraint. We will discuss the relations between these three |

| Contacto
| Departamento de Ingeniería Industrial | | Facultad de Ciencias Físicas y Matemáticas | Universidad de Chile | República 701, Santiago, Chile | Teléfono:(562)978-4072 | Fax:(562)978-4011 |