WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Techniques hybrides de recherche exacte et approchée: application à  des problèmes de transport

( Télécharger le fichier original )
par Boris BONTOUX
Université d'Avignon et des pays de Vaucluse - Doctorat spécialité informatique 2008
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

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.

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy








"Piètre disciple, qui ne surpasse pas son maitre !"   Léonard de Vinci