Optimisation des Optimisation des horaires de personnelhoraires de personnel

Bernard GendronBernard Gendron

Université de MontréalUniversité de Montréal

Domaines d’applicationDomaines d’application

Transport en communTransport en commun Transport aérienTransport aérien Administration de la santéAdministration de la santé Chaînes de magasinsChaînes de magasins

Contribution de la ROContribution de la RO

A Montréal même, une expertise de plus A Montréal même, une expertise de plus de 30 ans dans ces domaines!de 30 ans dans ces domaines!

Centre de recherche sur les transportsCentre de recherche sur les transports GERADGERAD Quelques compagniesQuelques compagnies Pourtant relativement peu connuePourtant relativement peu connue

RO : peu connue!RO : peu connue! Informatisation très lente dans de nombreuses Informatisation très lente dans de nombreuses

organisationsorganisations Situation aujourd’hui :Situation aujourd’hui :

RO : méthodes de plus en plus sophistiquéesRO : méthodes de plus en plus sophistiquées Essor d’Internet et progrès technologiquesEssor d’Internet et progrès technologiques

Confection d’horairesConfection d’horaires

Deux problèmes distincts :Deux problèmes distincts : Décider des quarts de travail et du nombre Décider des quarts de travail et du nombre

d’employés à affecter en fonction des besoins à d’employés à affecter en fonction des besoins à combler combler

Décider des employés à affecter aux quarts de Décider des employés à affecter aux quarts de travailtravail

Le premier problème peut être résolu par :Le premier problème peut être résolu par : Apprentissage statistique (voir présentation de Apprentissage statistique (voir présentation de

Yoshua Bengio au CIRANO)Yoshua Bengio au CIRANO) Modèles stochastiques et simulationModèles stochastiques et simulation

Le deuxième problème est traité par des Le deuxième problème est traité par des méthodes d’méthodes d’optimisation combinatoireoptimisation combinatoire

Optimisation combinatoireOptimisation combinatoire

Programmation en nombres entiersProgrammation en nombres entiers Génération de colonnesGénération de colonnes Méthodes heuristiquesMéthodes heuristiques Programmation par contraintesProgrammation par contraintes Méthodes hybridesMéthodes hybrides

Objectifs à considérerObjectifs à considérer

Minimiser les coûtsMinimiser les coûts Maximiser la satisfaction des employésMaximiser la satisfaction des employés

Satisfaire les exigences particulièresSatisfaire les exigences particulières Affecter les quarts de façon équitableAffecter les quarts de façon équitable Respecter l’ancienneté des employésRespecter l’ancienneté des employés

Satisfaire des besoins particuliers Satisfaire des besoins particuliers Par exemple, affecter certains quarts en priorité Par exemple, affecter certains quarts en priorité

à certaines catégories d’employésà certaines catégories d’employés

Exemple simplifiéExemple simplifié

II employés employés JJ jours jours KK quarts de travail/jour quarts de travail/jour Contrainte 1 : un employé/quartContrainte 1 : un employé/quart Contrainte 2 : Un quart de travail/jour pour Contrainte 2 : Un quart de travail/jour pour

chaque employéchaque employé Contrainte 3 : Après un soir travaillé, pas Contrainte 3 : Après un soir travaillé, pas

de quart le lendemain matinde quart le lendemain matin 24 heures/jour (cas des salles d’urgence)24 heures/jour (cas des salles d’urgence) Contrainte 4 : Après trois nuits travaillées, Contrainte 4 : Après trois nuits travaillées,

au moins trois jours de congésau moins trois jours de congés

Programmation en nombres entiersProgrammation en nombres entiers

Définir les variables d’affectationDéfinir les variables d’affectation

: employé : employé ii affecté au quart affecté au quart kk du jour du jour jj On peut facilement modéliser les trois On peut facilement modéliser les trois

premières contraintes avec ces variablespremières contraintes avec ces variables La contrainte 4 est plus complexeLa contrainte 4 est plus complexe Une première tentative (n’utilisant que les Une première tentative (n’utilisant que les

variables d’affectation) échoue : plusieurs variables d’affectation) échoue : plusieurs situations valides seraient interditessituations valides seraient interdites

Il faut ajouter des Il faut ajouter des variables de successionvariables de succession

1ijkx

Programmation en nombres entiersProgrammation en nombres entiers

AvantagesAvantages Approche classiqueApproche classique Extension de la programmation linéaireExtension de la programmation linéaire Algorithme de résolution éprouvé Algorithme de résolution éprouvé Algorithme exact Algorithme exact Logiciels performantsLogiciels performants

DésavantagesDésavantages Contraintes de succession difficiles à modéliserContraintes de succession difficiles à modéliser S’il y en a trop, difficile à résoudre!S’il y en a trop, difficile à résoudre! Objectif parfois impossible à exprimer comme Objectif parfois impossible à exprimer comme

une fonction linéaire des variables d’affectationune fonction linéaire des variables d’affectation

Génération de colonnesGénération de colonnes

Modèle basé sur l’affectation d’horairesModèle basé sur l’affectation d’horaires

: employé : employé ii affecté à un horaire affecté à un horaire hh Trop de variables : les générer de façon Trop de variables : les générer de façon

dynamiquedynamique Les deux premières contraintes sont Les deux premières contraintes sont

modélisées dans le modélisées dans le problème maître problème maître :: Programmation linéaire (en nombres entiers)Programmation linéaire (en nombres entiers)

Les deux autres contraintes sont Les deux autres contraintes sont modélisées dans le modélisées dans le problème auxiliaireproblème auxiliaire Souvent résolu par la recherche d’un plus court Souvent résolu par la recherche d’un plus court

chemin avec chemin avec contraintes additionnellescontraintes additionnelles

1ihx

Génération de colonnesGénération de colonnes

AvantagesAvantages Permet de modéliser aisément des situations Permet de modéliser aisément des situations

complexes (contraintes de succession, objectif complexes (contraintes de succession, objectif non linéaire,…)non linéaire,…)

Algorithme exactAlgorithme exact Problème maître a une structure connueProblème maître a une structure connue Algorithmes très efficaces pour le calcul de plus Algorithmes très efficaces pour le calcul de plus

courts chemins courts chemins DésavantagesDésavantages

Développement et implantation peuvent être très Développement et implantation peuvent être très longslongs

S’il y a trop de contraintes additionnelles, le S’il y a trop de contraintes additionnelles, le problème auxiliaire devient difficile à résoudre problème auxiliaire devient difficile à résoudre

Méthodes heuristiquesMéthodes heuristiques

Méthodes ne garantissant pas l’obtention Méthodes ne garantissant pas l’obtention d’une solution optimaled’une solution optimale

Souvent basées sur la notion de Souvent basées sur la notion de voisinage voisinage A partir d’une solution, on atteint une solution A partir d’une solution, on atteint une solution

voisine par une voisine par une modificationmodification Exemple : échanger les affectations de deux Exemple : échanger les affectations de deux

employésemployés Générer une première solution (plusieurs Générer une première solution (plusieurs

contraintes peuvent être violées!)contraintes peuvent être violées!) Passer d’une solution à une autre voisinePasser d’une solution à une autre voisine

En tentant d’améliorer l’objectifEn tentant d’améliorer l’objectif En tentant de réduire la violation des contraintesEn tentant de réduire la violation des contraintes

Méthodes heuristiquesMéthodes heuristiques

AvantagesAvantages Simples à concevoirSimples à concevoir Souvent très efficaces, si elles obéissent aux Souvent très efficaces, si elles obéissent aux

principes fondamentaux des principes fondamentaux des métaheuristiquesmétaheuristiques Permet de s’affranchir des logiciels commerciaux Permet de s’affranchir des logiciels commerciaux

(économie de $...)(économie de $...)

DésavantagesDésavantages Implantation efficace : un Implantation efficace : un artart Aucune garantie d’optimalité (écart à la solution Aucune garantie d’optimalité (écart à la solution

optimale?)optimale?) S’il y a trop de contraintes, difficile de trouver des S’il y a trop de contraintes, difficile de trouver des

solutionssolutions

Programmation par contraintesProgrammation par contraintes

Variables à domaine finiVariables à domaine fini

: employé : employé ii affecté au quart affecté au quart kk du jour du jour jj ContrainteContrainte

Exprime des relations de toute nature entre les Exprime des relations de toute nature entre les variables et leurs domainesvariables et leurs domaines

Lorsque le domaine d’une variable est réduit, Lorsque le domaine d’une variable est réduit, déclenche un algorithme de déclenche un algorithme de propagationpropagation pour pour réduire les domaines d’autres variables réduire les domaines d’autres variables

Algorithme de recherche Algorithme de recherche Réduit les domaines des variables Réduit les domaines des variables Propage l’effet de ces réductions au moyen des Propage l’effet de ces réductions au moyen des

contraintes contraintes

kxij

Programmation par contraintesProgrammation par contraintes

AvantagesAvantages Permet de modéliser toutes sortes de contraintesPermet de modéliser toutes sortes de contraintes Souvent efficace lorsqu’il y a un grand nombre de Souvent efficace lorsqu’il y a un grand nombre de

contraintes difficiles à satisfaire simultanémentcontraintes difficiles à satisfaire simultanément Algorithmes de recherche pouvant s’adapter à Algorithmes de recherche pouvant s’adapter à

des méthodes exactes ou heuristiquesdes méthodes exactes ou heuristiques

DésavantagesDésavantages Difficile d’implanter des contraintes Difficile d’implanter des contraintes efficacesefficaces Domaine relativement jeune (intéressant pour les Domaine relativement jeune (intéressant pour les

chercheurs, mais pas pour les praticiens…)chercheurs, mais pas pour les praticiens…) N’exploite pas encore très bien les algorithmes N’exploite pas encore très bien les algorithmes

éprouvés en ROéprouvés en RO

Méthodes hybridesMéthodes hybrides

Combiner heuristique et programmation par Combiner heuristique et programmation par contraintescontraintes Explorer des solutions par une heuristique à base Explorer des solutions par une heuristique à base

de voisinagede voisinage Explorer chaque voisinage au moyen de la Explorer chaque voisinage au moyen de la

programmation par contraintesprogrammation par contraintes

Combiner génération de colonnes et Combiner génération de colonnes et programmation par contraintesprogrammation par contraintes Résoudre le problème auxiliaire au moyen de la Résoudre le problème auxiliaire au moyen de la

programmation par contraintesprogrammation par contraintes Diriger la recherche de solutions du problème Diriger la recherche de solutions du problème

auxiliaire pour faciliter la résolution du problème auxiliaire pour faciliter la résolution du problème maîtremaître

Application 1 : médecins d’urgenceApplication 1 : médecins d’urgence

Deux hôpitaux de la région montréalaiseDeux hôpitaux de la région montréalaise Programmation en nombres entiersProgrammation en nombres entiers Heuristique en trois phasesHeuristique en trois phases

Affecter les fins de semaineAffecter les fins de semaine Affecter les nuits Affecter les nuits Affecter les autres quartsAffecter les autres quarts

Certaines contraintes sont dures, mais la Certaines contraintes sont dures, mais la plupart sont mollesplupart sont molles

Force de la méthode : capacité de prendre Force de la méthode : capacité de prendre en compte simultanément un grand nombre en compte simultanément un grand nombre de contraintesde contraintes

Application 1 : médecins d’urgenceApplication 1 : médecins d’urgence

Premier cas (1995-98)Premier cas (1995-98) Collaboration des médecinsCollaboration des médecins Implantation informatique rudimentaireImplantation informatique rudimentaire Absence de budget pour poursuivreAbsence de budget pour poursuivre

Deuxième cas (1999-2001)Deuxième cas (1999-2001) Intérêt de la DSPIntérêt de la DSP Implantation informatique incluant interface Implantation informatique incluant interface

graphique et base de donnéesgraphique et base de données Logiciel de programmation en nombres entiers Logiciel de programmation en nombres entiers

jugé trop coûteuxjugé trop coûteux Développement d’une méthode heuristique Développement d’une méthode heuristique

sans logiciel de programmation en nombres sans logiciel de programmation en nombres entiers (2001-2004)entiers (2001-2004)

Application 2 : SAQApplication 2 : SAQ

400 magasins et 3000 employés400 magasins et 3000 employés Division par régionDivision par région Un même employé peut travailler dans Un même employé peut travailler dans

plusieurs succursales d’une même régionplusieurs succursales d’une même région On traite les employés l’un après l’autre, par On traite les employés l’un après l’autre, par

ordre d’anciennetéordre d’ancienneté Pour chaque employé, on résout un modèle Pour chaque employé, on résout un modèle

de programmation en nombres entiersde programmation en nombres entiers Une méthode exacte est nécessaire car une Une méthode exacte est nécessaire car une

solution optimale doit être identifiée!solution optimale doit être identifiée!

Application 2 : SAQApplication 2 : SAQ

Interface accessible dans chaque Interface accessible dans chaque succursale via le Websuccursale via le Web

Base de données centralisée qui reçoit les Base de données centralisée qui reçoit les données et transmet les résultats aux données et transmet les résultats aux succursalessuccursales

Base de données communique avec le Base de données communique avec le moteur d’optimisation via des fichiersmoteur d’optimisation via des fichiers

Nouvelles contraintes faciles à intégrer au Nouvelles contraintes faciles à intégrer au modèle grâce aux librairies pouvant être modèle grâce aux librairies pouvant être intégrées au code C++intégrées au code C++

Implantation depuis septembre 2002Implantation depuis septembre 2002

Caractéristiques des applicationsCaractéristiques des applications

Environnement syndiquéEnvironnement syndiqué Règles rigides et souvent complexesRègles rigides et souvent complexes Méthode exacte souvent nécessaireMéthode exacte souvent nécessaire Satisfaction des employés et anciennetéSatisfaction des employés et ancienneté

Environnement non syndiquéEnvironnement non syndiqué Règles flexiblesRègles flexibles Méthodes heuristiques intéressantesMéthodes heuristiques intéressantes Équité entre employés (mais pas toujours)Équité entre employés (mais pas toujours)

Demande variable : combiner la résolution Demande variable : combiner la résolution des deux problèmes mentionnés au débutdes deux problèmes mentionnés au début

ConclusionsConclusions

Questions de rechercheQuestions de recherche Programmation par contraintesProgrammation par contraintes Méthodes hybridesMéthodes hybrides Demande variableDemande variable

Progrès en pratiqueProgrès en pratique Interface Web et base de donnéesInterface Web et base de données Moteur d’optimisation communiquant avec la Moteur d’optimisation communiquant avec la

base de donnéesbase de données Progrès continus dans les méthodes Progrès continus dans les méthodes

d’optimisation combinatoired’optimisation combinatoire