The Employee Timetabling Problem (ETP) is a general class of problems widely encountered in service organizations (such as call centers for instance). Given a set of activities, a set of demand curves (specifying the demand in terms of employees for each activity for each time period) the problem consists of constructing a set of work shifts such that each activity is at all time covered by a sufficient number of employees. Work shifts can cover many activities and must meet work regulations such as breaks, meals and maximum working time constraints. Furthermore, it is often desired to optimize a global objective function such as minimizing labor costs or maximizing a quality of service measure. This paper presents variants of this problem which are modeled with the Dantzig formulation. This approach consists of first generating all feasible work shifts and then selecting the optimal set. We proposed to address the shift generation problem with constraint satisfaction techniques based on expressive and efficient global constraints such as gcc and regular. The selection problem, which is modeled with a integer linear program, is solved by by column generation. Since a column generation procedure needs to generate only shifts of negative reduced cost, the optimization constraint cost-regular is introduced and described. Preliminary experimental results are given on a typical ETP.

In case a CSP is over-constrained, it is natural to allow some constraints, called soft constraints, to be violated. We propose a generic method to soften global constraints that can be represented by a flow in a graph. Such constraints are softened by inserting violation arcs to the graph. Then we compute a minimum-weight flow in the extended graph to measure the violation. We present efficien propagation algorithms, based on dierent violation measures, achieving hyper-arc consistency for the alldifferent constraint, the global cardinality constraint, the regular constraint and the same constraint.

Dans un système de PPC, les heuristiques d’incitations servent à guider la recherche en permettant un meilleur choix de variable ou de valeur, afin d’améliorer la robustesse du système. La présentation traitera principalement de l’implémentation d’une heuristique d’incitation pour la contrainte de cardinalité et la présentation de quelques résultats préliminaires. L’application traitée est Hibiscus, un système modulaire de confection d'horaires d’infirmières.