Personal tools
You are here: Home Teaching / Enseignement files IAD Projets M2-IAD 2007-2008 Projets Couplages dans les graphes : Etude et applications
Navigation
Log in


Forgot your password?
 
Document Actions

Couplages dans les graphes : Etude et applications

by François Rioult last modified 2007-11-04 17:04

Objectifs

Etudier certains (pas tous) problèmes de couplage dans les graphes ainsi que les algorithmes qui permettent de les résoudre. Appliquer ces algorithmes pour traiter différents problèmes réels : emplois du temps, gestion de personnel, allocation de ressources, ....


Deux exemples introductifs

  1. Allocation de ressources
    • Une entreprise dispose d’un ensemble de k employés E = {e_1, e_2, …, e_k} et doit pourvoir un ensemble de n postes P = {p_1, p_2, …, p_n}, avec k ≥ n. Chaque poste requiert une certaine qualification, et chaque employé peut occuper un ou plusieurs postes selon ses qualifications.
    • On considère le graphe bipartite : (P, E, U) où (p_i, e_j) appartient à U ssi l’employé e_j est qualifié pour occuper le poste p_i.
    • On souhaite résoudre le problème de satisfaction suivant : existe-t-il une affectation (couplage) des employés aux postes de façon à ce que tous les postes soient occupés ?
  2. Ordonnancement d’ateliers
    • Dans un atelier de production, on souhaite usiner n pièces P = {p_1, p_2, …, p_n} à l’aide de k machines M = {m_1, m_2, …, m_k}, avec k ≥ n. Chaque pièce p_i peut être usinée par plusieurs machines, mais les coûts d’usinage ne sont pas constants.
    • Soit c_ij le coût d’usinage de la pièce p_i par la machine m_j (si m_j ne peut usiner p_i, le coût sera considéré comme infini.).
    • On souhaite résoudre le problème d’optimisation suivant : trouver une affectation (couplage) des machines aux tâches qui soit de coût minimal.


Etapes

  1. Recenser les différents problèmes de couplage dans les graphes ainsi que leurs algorithmes de résolution,

  2. Sélectionner les problèmes que l'on souhaite étudier plus profondément,

  3. Mise en oeuvre et résolution d'applications. La mise en oeuvre pourra se faire, selon les cas,

    • soit à l'aide du logiciel OPL-Studio qui sera étudié au 1er semestre dans l’unité UE 1,
    • soit en mettant en œuvre les algorithmes dans un langage de programmation de votre choix.


« June 2011 »
Su Mo Tu We Th Fr Sa
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30
 

Powered by Plone, the Open Source Content Management System

This site conforms to the following standards: