1.9.2 Application au problème d'Emploi du Temps de
Garde d'Infirmières
Notre méthode a été ensuite
appliquée à un problème issu d'une application pratique.
Ce problème est un problème de rotation de personnel avec
contraintes, connu sous le nom de problème d'emploi du temps pour les
gardes d'infirmières ou Nurse Rostering Problem (voir (Cheang
et al., 2003) pour plus de détails sur ces problèmes).
Ce problème est un problème de satisfaction de contraintes dont
le but est de satisfaire les contraintes de compétences tout en assurant
que les employés ayant plusieurs compétences soient
employés pour chacune de leurs compétences d'une manière
équilibrée. Le problème d'emploi du temps pour les gardes
d'infirmières est un problème NPdifficile (Osogami et Imai,
2000). Le problème étudié est un problème concret,
proposé
dans le cadre d'un partenariat avec Daumas Autheman et
Associés, qui concerne une rotation de personnel dans une entreprise de
déchargement de ferries.
Soit n le nombre d'employés.
Xijk est l'activité de l'employé i,
le jour j et semaine k, avec i = 1, . . . ,
n, j = 1, . . . , 7, k = 1, . . . , l.
Xijk est égal à 0 quand l'employé ne
travaille pas. S = 1, . . . , t est l'ensemble des
activités considérées. Soit Ci c S pour
i = 1, . . . , n, l'ensemble des activités que
l'employé i est capable d'exécuter.
Emjk est le nombre d'employés requis pour
l'activité m au jour j et semaine k. Les
contraintes sont les suivantes :
|{Xijk|Xijk = m}| = Emjk j =
1, .. . ,7 k = 1, ... , l m = 1, .. . , t (1.6)
|{Xijk|Xijk = 0}| = 2 i = 1, . . . ,
n k = 1, . . . , l (1.7)
|{Xi6k|Xi6k = 0}| = r i
= 1, .. . , n k = 1, .. . , l (1.8)
|{Xi7k|Xi7k = 0}| = r i
= 1, .. . , n k = 1, .. . , l (1.9)
b 5
|Ci|c = |{Xijk|Xijk = m}| = [
5
|Ci|1 m E Ci i = 1, .. . , n k
= 1, .. . , l (1.10)
Xijk E Ci i = 1, ... , n j = 1, ...
,7 k = 1, ... , l (1.11)
Les contraintes (1.6) assurent que, pour chaque période
de temps, le nombre d'employés assignés à
l'activité m est égal au nombre requis
d'employés. Les contraintes (1.7) assurent que chaque employé est
en repos au moins deux jours par semaine. Les contraintes (1.8) et (1.9)
assurent que le nombre de samedis et dimanches vaqués est
supérieur à r (où r est une
donnée du problème). Enfin, la contrainte (1.10) indique que si
un employé possède plusieurs compétences, il doit
être employé pour chacune de ses compétences (5
étant le nombre moyen de jours travaillés par semaine).
Nous avons implémenté une version
préliminaire de la méthode DLS telle que décrite dans la
section 1.3 et nous avons comparé notre méthode avec des
politiques (goals) proposées par le solver commercial ILOG
Solver.
Le tableau 1.2 montre nos résultats sur un ensemble de
25 instances générées aléatoirement sur un horizon
de temps allant de 4 à 75 semaines et un nombre d'employés
égal à 5. Les résultats présentent la moyenne des
temps d'exécution (en secondes) pour obtenir une solution. La limite de
temps est fixée à 600 secondes. Notre méthode est
comparée avec deux politiques par défaut dans ILOG Solver. Les
colonnes ILOG Solver et DLS correspondent à la
politique de choix des valeurs : plus petite valeur possible pour la colonne
ILOG Solver et plus grande pondération pour la méthode DLS. Les
lignes correspondent à la politique de choix des variables :
Première Variable Non Bornée ou First Unbound qui
choisit en premier la première variable non bornée, Plus Petit
Domaine ou dom qui choisit en premier la variable non bornée
avec le plus petit domaine) (ces deux méthodes sont des politiques par
défaut dans ILOG Solver), puis les politiques présentées
dans la section 1.8.1), Moyenne maximale, Moyenne minimale, Plus petit
écart aux extrêmes.
La lecture des résultats nous permet de comparer
l'efficacité des choix dans les variables. Il semble évident que
la politique de choix de variable ayant la plus grande
|
Ilog Solver
|
DLS
|
|
First unbound
|
94 s
|
117 s
|
|
Plus petit domaine
|
52 s
|
24,34 s
|
|
Moyenne minimale
|
|
0,75 s
|
|
Moyenne maximale
|
|
130,28 s
|
|
Écart aux extrêmes
|
|
3,98 s
|
TABLE 1.2 - Résultats
expérimentaux pour plusieurs méthodes appliquées au
problème d'emploi du temps pour les gardes d'infirmières
moyenne des pondérations n'est pas une politique
efficace ici. En appliquant cette politique, les résultats sont plus
mauvais que dans les politiques par défaut d'ILOG Solver. On peut
remarquer que cette politique va a l'encontre de la politique de « First
Fail >>. En choisissant la variable qui a la plus petite moyenne des
pondérations, les variables instanciées ont tendance à
couper rapidement l'arbre de recherche. Ces résultats montrent ainsi que
la politique de « First Fail>> semble la plus efficace. En
conclusion, les résultats montrent que la méthode DLS est
jusqu'à 50 fois plus rapide que les politiques par défaut d'ILOG
Solver.
| 
