Répartition de tâches. Quel algorithme ?

[haskouse]

Bonjour,

J'ai le problème suivant :
un ensemble de personne qui doivent faire un ensemble de tâche, sachant que chaque tâche demande un nombre différents d'heure. Par exemple :

Personne1, Personne2, Personne3
puis
Tâche1(2H), Tâche2(5H), Tâche3(6H), Tâche4(1H), Tâche5(3H)

Si je suppose que ces 3 personnes peuvent effectuer n'importe laquelle de ces 5 tâches, je voudrais créer un algorithme qui permet de faire la meilleur répartition des tâches de façon à ce que chacun de ces 3 personnes travaille sur au moins deux tâches et au plus trois tâches, et que la somme des heures travaillée par chacun des employé soit proches (voir égales).

Je ne sais pas si j'ai bien expliqué mon problème.

En fait je veux savoir quel genre d'algorithme faut-il utiliser pour résoudre ce genre de problème ? J'ai fait des recherches et j'ai pu lire quelques trucs sur les algorithmes génétiques, algorithme de la colonnie de fourmi ...

Est ce que quelqu'un pourrait me guider ?
Merci par avance.

[Nehmé]

Le problème que tu essaies de résoudre est un problème d'optimisation. Deux approches sont possibles:
1- Programmation mathématique
2- Algorithmes heuristiques

Avec la programmation mathématique tu peux modéliser mathématiquement ton problème sous forme d'une fonction objective et d'une liste de contraintes. Par la suite, il suffit de passer le modèle mathématique à un solveur de programme mathématique tel que CPLEX qui utilisent des méthodes exactes tel que l'algorithme du simplexe et le "Branch & Bound" pour résoudre ton problème. Pour pouvoir utiliser cette méthode il va falloir que tu apprennes les principes de base de la programmation mathématique.

Sinon les méthodes heuristiques te permet aussi de résoudre ton problème. N'importe laquelle des métaheuristiques comme l'algorithme génétique, colonies de fourmis, recherche local itérée ou autre, te prémetra de résoudre ton problème mais il va falloir que tu apprennes à les utiliser. Des librairies qui implémentent ces métahreuristiques sont disponible sur le net mais pour savoir les utiliser il va falloir que tu comprennes les principes de bases. Je te conseille de passer par un livre. Mon préféré est "Metaheuristics search concepts" mais il est en anglais.

La différence entre les deux est que:
- Les méthodes de programmation mathématique sont généralement des méthodes exactes et déterministes et trouvent la solution optimale au problème dans un temps qui dépend de la taille du problème.
- Les méthodes heuristiques ne trouvent pas nécessairement la solution optimale à ton problème mais sont généralement plus rapides que les méthodes exactes et permet souvent de trouver des tres bonnes solutions rapidement. Par contre, pour qu'elles soient efficaces, ces méthodes nécessitent beaucoup plus d'effort que les méthodes exactes au niveau du codage et de l'adaptation de ces méthodes pour ton problème.

L'optimisation est un domaine très large et ce petit résumé est loin d'être complet.

[souviron34]

Envoyé par Nehmé

ce petit résumé est loin d'être complet.

Certes, mais il est très clair

Note : à mettre dans les "A Lire" ??

[Jimmy_]

Bonjour,

Ce genre de problème quand il y a des millions de tâches doit effectivement être traité avec un algorithme optimisé, car sinon il est impraticable dans un temps raisonnable.
Or ici pour ce cas où tu n'auras jamais des millions de tâches. Je te propose l'algorithme glouton en choisissant par exemple d'attribuer en priorité les taches les plus longues.