Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

C Ch ha ap pi it tr re e 0 07 7 : : P Pr ro ob bl lè èm me es s d d’ ’a af ff f

C Ch ha ap pi it tr re e 0 07 7 : : P Pr ro ob bl lè èm me es s d d’ ’a af ff fe ec ct ta at ti io on n P Pr ré ép pa ar ré é p pa ar r M Mr r: : A A. .S SA AC CI I Module : Recherche Opérationnelle, 3ème Année Ingénieur Année universitaire : 2007/2008 D Dé ép pa ar rt te em me en nt t d d’ ’I In nf fo or rm ma at ti iq qu ue e ( (U Un ni iv ve er rs si it té é d de e B BA AT TN NA A) ) P Pa ag ge e 1 1/ /4 4 d11 Ouvrier 1 Ouvrier 2 Ouvrier i Ouvrier n Tâche 1 Tâche 2 Tâche j Tâche n 1 . . . . . . . . 2 i n 1 . . . . . . . . 2 j n d12 d1j dnn dij d22 1. Introduction Le problème d’affectation est souvent présenté sous la forme suivante : Un chef de projet veut affecter « n » ouvriers à la réalisation de « n » tâches différentes, de façon à minimiser le temps de réalisation de toutes les tâches à la fois. Le problème sera donc la recherche d’une affectation minimale des « n » ouvriers aux « n » tâches. Ce problème peut être représenté par le graphe biparti G=(X1,X2,U) suivant : Où, X1 : représente l’ensemble des ouvriers X2 : représente l’ensemble des tâches. U : est l’ensemble des arêtes, où les valeurs des arêtes représentent le temps mis par chaque ouvrier pour réaliser chaque tâche (dij : durée de réalisation de la tâche « j » par l’ouvrier « i »). 2. Description du problème d’affectation On considère les deux ensembles suivants : P={p1,p2, …, pn} ensemble de personnes et T={t1,t2, …, tm} ensemble de tâches. Il s’agit de répartir les différentes tâches entre les différentes personnes de façon optimale en tenant compte des préférences de chaque personne aux différentes tâches, allant de la satisfaction générale à la satisfaction individuelle. La préférence de chaque personne « pi » à la tâche « tj » est représentée par un nombre noté « aij », qui peut correspondre à un temps, un rendement, un coût, un profit, …, etc. Soit G=(X1,X2,U) le graphe biparti correspondant à ce problème où : X1=P : est l’ensemble de personnes, X2=T : est l’ensemble de tâches. U={(pi,tj)/i=1,…,n et j=1,…, m} : est l’ensemble des arêtes reliant les sommets de P aux sommets de T. Le problème sera ainsi modélisé par une matrice A=(aij) appelée matrice d’affectation. 3. Résolution du problème d’affectation par la méthode Hongroise La recherche d’une affectation optimale (maximale ou minimale) par la méthode hongroise est basée sur la notion de zéros indépendants dans une matrice carrée. Définition : Ñ Zéros indépendants : on appelle zéros indépendants, les zéros qui n’appartiennent ni à la même ligne ni à la même colonne d’une matrice carrée. Chapitre P Pr ro ob bl lè èm me es s d d’ ’a af ff fe ec ct ta at ti io on n C Ch ha ap pi it tr re e 0 07 7 ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = nm nj n2 n1 im ij i2 i1 2m 2j 22 21 1m 1j 12 11 a ... a ... a a . . . . . . a ... a ... a a . . . . . . a ... a ... a a a ... a ... a a A C Ch ha ap pi it tr re e 0 07 7 : : P Pr ro ob bl lè èm me es s d d’ ’a af ff fe ec ct ta at ti io on n P Pr ré ép pa ar ré é p pa ar r M Mr r: : A A. .S SA AC CI I Module : Recherche Opérationnelle, 3ème Année Ingénieur Année universitaire : 2007/2008 D Dé ép pa ar rt te em me en nt t d d’ ’I In nf fo or rm ma at ti iq qu ue e ( (U Un ni iv ve er rs si it té é d de e B BA AT TN NA A) ) P Pa ag ge e 2 2/ /4 4 Exemple : Soit la matrice suivante : Les zéros encadrés ne sont ni sur la même ligne ni sur la même colonne, ils sont dit alors « zéros indépendants ». Remarques : La méthode hongroise est applicable sur une matrice d’affectation carrée (de type n*n). L’algorithme est basé sur la détermination de zéros sur chaque ligne et chaque colonne de la matrice d’affectation. Pour que chaque personne soit affectée à une seule tâche, il faut choisir des zéros indépendants. Le but de la méthode Hongroise est alors d’obtenir « n » zéros indépendants. 4. L’algorithme de recherche d’une affectation minimale La résolution du problème d’affectation par la méthode hongroise se fait en deux grandes étapes suivantes : Algorithme Hongrois Entrée : Matrice d’affectation A. Sortie : Affectation optimale. Début Première étape : c On fait apparaître au moins un zéro sur chaque ligne et chaque colonne de la matrice d’affectation, en retranchant de chaque ligne, le plus petit élément (on fait de même pour chaque colonne). d On choisit sur chaque ligne un zéro en l’encadrant, et on barre les zéros qui se trouvent sur la même ligne et la même colonne. e Si (on a obtenu « n » zéros indépendants), Alors L’affectation est optimale. Tout zéro encadré correspond à la valeur « aij » dans la matrice d’affectation, alors la personne « pi » est affectée à la tâche « tj » ; et la valeur de l’affectation minimale est égale à la somme des « aij » de la matrice de départ dont la position (i,j) de la matrice finale contient un zéro encadré. Sinon Aller à la deuxième étape FSi Deuxième étape : c Marquer toutes les lignes ne contenant pas de zéro encadré. d Marquer toutes les colonnes contenant un zéro barré sur une marquée. e Marquer toutes les lignes contenant un zéro encadré sur une colonne marquée. f Répéter d et e jusqu’à ne pouvoir plus marquer ni de lignes ni de colonnes. g On barre toutes les lignes non marquées et toutes les colonnes marquées. h On considère les éléments non barrés de la matrice, soit min le plus petit élément d’entre eux. Ñ A chaque élément non barré de la matrice, on retranche l’élément min. Ñ A chaque élément barré deux fois de la matrice, on rajoute l’élément min. Ñ On laisse inchangé les éléments barrés une seule fois dans la matrice. i On intègre les nouveaux éléments calculés dans A, on obtient ainsi une nouvelle matrice. j On choisit de nouveaux zéros pour les lignes ne contenant pas de zéro encadré. k Si (on a « n » zéros indépendants), Alors Aller à e de la première étape. Sinon Aller à d de la première étape FSi Fin A= 00 1 2 1 1 00 3 00 0 C Ch ha ap pi it tr re e 0 07 7 : : P Pr ro ob bl lè èm me es s d d’ ’a af ff fe ec ct ta at ti io on n P Pr ré ép pa ar ré é p pa ar r M Mr r: : A A. .S SA AC CI I Module : Recherche Opérationnelle, 3ème Année Ingénieur Année universitaire : 2007/2008 D Dé ép pa ar rt te em me en nt t d d’ ’I In nf fo or rm ma at ti iq qu ue e ( (U Un ni iv ve er rs si it té é d de e B BA AT TN NA A) ) P Pa ag ge e 3 3/ /4 4 Remarques : Soit « n » le nombre de personnes et « m » le nombre de tâches. Ñ Si (n>m), pour obtenir une matrice carrée on doit rajouter (n-m) tâches dites fictives et leurs valeurs d’affectation aux différentes personnes sont nulles ; c.-à-d., on rajoute « n-m » colonnes. Ñ Si (n<m), pour obtenir une matrice carrée on doit rajouter (m-n) personnes dites fictives et leurs valeurs d’affectation aux différentes tâches sont nulles ; c-à-d, on rajoute « m-n » colonnes 5. Exemple Quatre ouvriers doivent être affectés à quatre tâches différentes, le temps mis par chaque personne pour la réalisation de chaque tâche est donné par la matrice d’affectation suivante : On cherchera une affectation des ouvriers aux tâches minimisant le temps de réalisation. Soit A la matrice d’affectation correspondante au problème : Première étape : c On retranche des lignes 1, 2, uploads/Management/ chapitre-7-tg.pdf