Problème d'affectation

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Le problème d'affectation est un problème classique de recherche opérationnelle. L'objectif est de déterminer un couplage maximum dans un graphe biparti valué. Le problème d'affectation peut être résolu en temps polynomial par l'algorithme hongrois, il appartient par conséquent à la classe de complexité P.

Définitions[modifier | modifier le code]

Algorithmes[modifier | modifier le code]

Applications[modifier | modifier le code]

L'application la plus classique de ce problème est, en ordonnancement de tâches, l'affectation de n machines à n tâches. Chaque machine ne peut être affectée qu'à une seule tâche et chaque couple (tâche;machine) a un coût. Le but est de minimiser le coût total d'exécution des tâches.

Notes et références[modifier | modifier le code]


Articles connexes[modifier | modifier le code]

Problème des mariages stables