inicioir al DIIbuscar
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
approaches and see when and where each of them is appropriate. We will also illustrate how these models, which are able to return near optimal solution on traditional problems, can scale on difficult industrial problems.