Accueil
Affiche (PDF)
 
Participants
Programme
Inscription
Site
Hébergement
Liens
 
 
Éditions précédentes
2004
2003
2002


    

Séance WA3 - Programmation par contraintes / Constraint Programming

Jour mercredi, le 11 mai 2005
Salle Dutailier International
Président Louis-Martin Rousseau

Présentations

10h30 Constraint Programming Based Column Generation for Employee Timetabling
  Sophie Demassey, Centre de Recherche sur les Transports, CP 6128 Succ Centre-Ville, Montréal, QC, Canada, H3L 3J7
Gilles Pesant, École Polytechnique de Montréal, CRT et Génie informatique, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Louis-Martin Rousseau, École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7

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.


10h55 On Global Warming : Flow Based Soft Gloval Constaints
  Willem Jan van Hoeve, CWI, P.O. Box 94079, NL-1090 GB Amsterdam, The Netherlands
Gilles Pesant, École Polytechnique de Montréal, CRT et Génie informatique, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7
Louis-Martin Rousseau, École Polytechnique de Montréal, Mathématiques et génie industriel, C.P. 6079, Succ. Centre-ville, Montréal, Québec, Canada, H3C 3A7

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 di erent violation measures, achieving hyper-arc consistency for the alldifferent constraint, the global cardinality constraint, the regular constraint and the same constraint.


11h20 Intégration d'une heuristique modulaire à la programmation par contraintes.
  Abdallah Oumha, École Polytechnique de Montréal, CRT et génie informatique, 3800 Bouchette, apt: 32, montreal, Quebec, Canada, H3S 1J2

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.