Discussion :

[mehdi_m1986]

Salut tout le monde,
Je cherche un algorithme qui fait l'affectation des personnes à des postes en respectant leurs choix.

ces personnes sont favoriser entre eux par un nombre de points.
ces poste sont deux categories : une est déja occuper et une libre (attendent une occupation)
Mon cas est une affectation selon l'offre et la demande + prise on consideration que les personnes qui occupe des poste avant l'affectation peuvent demander de changer leurs poste

régle :
un seul poste par personne
priorité par points
Les personnes participant à l'affectation ont deja des poste mais demande un chegement de poste soit par un existant soit par un nouveau (offre)

j'espère que j'ai suffisament expliquer mon probleme, je serai tres reconnaissant d'avoir des tuaux pour la solution. merci d'avance

[ToTo13]

Bonjour,

ce genre de problème possède une compléxité élevée.
Une bonne méthode est d'utiliser des heuristiques de type Tabou. Ca te fait varier ton personnel jusqu'à converger vers une bonne solution (par forcément la solution optimale).

Donc :
- tu implémentes les règles de mutations, affectations, ...
- tu crées une fonction de coût, qui dépendra de la satisfaction de chaque personne à son poste.
- tu lances la méthode tabou sur le problème qui te donnera une affectation.

[mehdi_m1986]

Mais
pourriez vous m'expliquer comment puis je adapter ces heuristique avec mon prob pcq je suis debutant en cette inteligence artificielle,et comment faire cette methode tabou merci d'avance

en ce qui concerne l'affectation j'ai pensé à trié la liste du personnels en fonction des points du bonus (ils ont des points de binification que j'ai pas cité ci dessus),
En suite je vais prendre le premier poste libre et je chercherai les gents qui le demande,
Le plus bonifier va le prendre et j'elimine la personne et le poste des deux liste
et ainsi de suite tantque la liste du personnel est ( list.count <> 0)
mais pour la mutation ce me parrais un peux delicate

[ToTo13]

Bonjour,

je ne peux pas te faire un cours sur la méthode Tabou, regardes sur google, il y beaucoup de chose dessus.
Grosso modo :
- tu proposes une solution.
- tu évalues sa valeur avec ta fonction de coût.
- Si c'est la meilleure pour le moment tu la gardes.
- Elle est déclarée Tabou pour quelques itérations.
- Tu proposes d'autres solutions
- ...

Fais bien ta fonction de coût. Tu peux effectivement accorder des priorités aux personnes avec des points bonus, c'est réaliste.
Ensuite la fonction de coût dépendra de la somme des satisfaction de chaque personne au nouveau poste qu'elle occupe :
- Meileur poste => Satistaction +
- Meileur poste et poste demandé => Satistaction ++++
- Moins bon poste => Satistaction ------------- (ne pas en arriver là).
- Poste non demandé=> Satistaction ----------------------- (ne jamais en arriver là).

Pour rester réaliste, il faut pénaliser très fort l'affectation à un poste inférieur afin que cela n'arrive jamais.

Bon courage

[borisd]

Bonjour,
si ton problème n'est pas plus complexe que ce que tu décris, il s'agit d'un problème "d'affectation simple", classique en optimisation combinatoire. Tu peux le résoudre optimalement grâce à un algorithme plutôt simple et très efficace (méthode hongroise).

Cet algorithme fonctionne lorsque le nombre de postes est égal au nombre d'agents. Cependant, si tu as plus de postes que d'agents, tu peux, je pense, créer des agents fictifs qui n'ont aucune préférence, et te ramener à ce cas.

Une méthode taboue ne sera utile que si tu as d'autres contraintes que tu n'as pas cité ; ici, rien ne sert de calculer une solution de moins bonne qualité de manière plus compliquée

[mehdi_m1986]

Merci pour vos contributions j'ai déja essyeé la methde hongroise et m'as données de bonnes solutions, merci
mais :s ya des etape dont l'implementation est un peu deficile
merci bcp

[ToTo13]

Pense à la balise