Discussion :

[cilia]

Bonjour,
Je travaille sur un projet concerne la planification des ressources humaines
Je fais des recherche sur les algorithmes de recherche opérationnelle permettant d’optimiser au mieux les emplois du temps.
Si vous avez l’amabilité de bien vouloir m’aider je vous en serais infiniment reconnaissante.

Cordialement,
Cilia

[TanEk]

Je ne suis pas un expert là-dedans mais si ton problème peut se résoudre à l'aide de la programmation dynamique je pourrais t'aider :

http://fr.wikipedia.org/wiki/Programmation_dynamique

Dans tous les cas, pose les limites de ton problème. Combien de journées dois-tu traiter ? Les journées sont divisées en heure ? en quart d'heures ? etc. Il faut discrétiser le temps et connaître ses dimensions.

[FrancisSourd]

La grande conférence du domaine s'appelle PATAT;-)

http://www.asap.cs.nott.ac.uk/patat/patat-index.shtml

De nombreux papiers peuvent être téléchargés. La plupart des outils de la RO ont été testés avec plus ou moins de bonheur. A ma connaissance, il n'y a pas une méthode générale qui se dégage pour une large gamme de problèmes

[Nadine]

est-ce que tu connais l'algorithme de projet à coûts minimal?

c'est un algo qui pourrait t'aider, mais il faut que tu connaisses les dépendances entre les projets des personnes. (ex : l'analyse d'un projet ne peut être faite après la programmation)

[cilia]

Bonjour à toutes et à tous,
Jusqu'à maintenant je ne sais pas ce que je peux utiliser comme algo pour mon projet, mais je dois faire de recherches sur les algos de recherche opérationnelle (partie de mon stage de recherche) pour sortir a la fin avec un résultat qui va m’aider dans mon projet (partie programmation)
Donc pour le moment lire tous ce qui concerne les algo de recherche opérationnelle (Articles, livres, doc….)

Cilia

[aoyou]

Bonjour,

Des premiers messages que j'ai lu, je me demande si ta question ne manque pas de précision. Est-ce que tu veux générer les emplois du temps de différentes personnes pour une période donnée ou veux-tu allouer différentes personnes à un projet de telle sorte que le projet dure le moins longtemps ?

++

[cedric49fr2000]

salut,

je me rapelle d'un algo d'ordonnancement de tache avec reduction de temps (il en existe aussia vec reductionde cout mais je le retrouve pas).
je ne sais pas si il est adaptable. il suffit de rechercher algorithm PERT.

il est destine a ordonnancer des taches successive ou paralelle donc potentiellement schematisable par un graphe (ou un reseau dans ce cas plutot).

est ce adaptable ?



autrement j'aurais tendance a definir l'environnement (comme dis plus haut les unite de temps et autre regle definissant le "jeu"), puis les contraintes (dans le cas dune ecole par exemple, deux salle ne peuvent pas etre utilise en meme temps, n ensignant ne peut pas enseigner a deux classe en meme temps, un enseignant ne veux pas enseigner le samedi matin , ect ...).

lors je m'orientrais vers la programmation par contrainte (le probleme je crois est qu'il ne donne pas un resultat en un temps previsible).

il ya aussi les algo genetique de tous poil qui peuvent potentiellement etre utilise je pense puisque le but serait de minimiser les entorce aux contrainte en respectant les regle de vies.

voila pour mes idees.

cedric

[cilia]

Bonjour,
Comme l'exemple qui a donné cedric des salles de cours.
Automatisé l'emplois du temps pour les soignants hospitaliers parexemple et Utiliser des algos de RO a fin d'optimiser les emplois du temps pour chaque soignant.

Merci

[cedric49fr2000]

c'est un probleme d'analyse pas d'algorithme.

l'analyse te permet de rapprocher ton probleme d'une solution connu.

tu dois modeliser avant tout .

cedric

[Strab]

Si il s'agit d'affecter des ressources à des activités et /ou lieux en respectant des contraintes (typiquement allouer un prof à une classe et une salle), tu peux essayer de modéliser le problème par un graphe. Il se résoud ensuite généralement par un algorithme de coloration ou dérivés.

Si c'est un problème d'ordonancement, utilise un diagramme de Gant ou PERT.

La programmation dynamique peut aussi s'avérer judicieuse, comme proposée dans un des premiers posts.

[aoyou]

Bonjour,

Du coup si tu veux faire des emplois du temps, j'espère que mes quelques expériences sur les emplois du temps pourront t'aider.

D'abord, la création d'emplois du temps est un problème compliqué. A l'époque ou je m'y intéressais, je connaissais quelqu'un qui avait essayé d'aborder le problème avec de la programmation par contraintes. Toutefois, les emplois du temps impliquent beaucoup de contraintes. Je ne sais pas ce que c'est devenu.

Pour ma part, je m'étais juste réduit à un problème d'optimisation de l'occupation des salles des emplois du temps. Les emplois du temps étaient faits à la main. Ne restait plus qu'à faire correspond un créneau de l'emploi du temps à une salle. J'avais finalement réduit le problème à un problème d'allocation d'une ressource (une salle) à un unique emploi (un créneau de l'emploi du temps) (en recherche opérationnelle, c'est plus souvent connu sous le problème d'allouer des pilotes à un unique avion et ce de façon optimale). J'avais un peu modifié cet algo pour tenir compte du temps et ça roulait pas si mal que ça.

Un emploi du temps, c'est aussi allouer un créneau de l'emploi du temps à une personne (au lieu d'allouer à une salle) et ce de façon optimale mais beaucoup de contraintes viennent s'ajouter (disponibilités des gens, incompatibilité d'humeur ;-)

Je te souhaite bon courage. D'expérience, la conception des emplois du temps peut être assez simple, de base, mais ça se complique très vite.

++

[ToTo13]

Bonjour

salut,

je me rapelle d'un algo d'ordonnancement de tache avec reduction de temps (il en existe aussia vec reductionde cout mais je le retrouve pas).
je ne sais pas si il est adaptable. il suffit de rechercher algorithm PERT.

L'algo PERT met dans l'ordre des taches, mais ne fait pas un emploi du temps.

Il me semble que les problèmes d'emplois du temps sont considérés comme NP.
Une solution pour les résoudre est l'utilisation de métaheuristiques, notamment la méthode TABOU.

[cedric49fr2000]

Effectivement la methode tabou me dis quelque chose aussi.

va falloir que je ressorte mes vieux cours du grenier lolll.


note : j'ai fait quelque recherche sur la programmation dynamique. mais pas facile de voir vraimetn de quoi on parle. si quelqu'un pouvait exposer les principes. attention , je parle pas de nous fournir le code d'un algo implemnatant ce genre de concept. premierement, ca manque de generalite. deuxiement, c'est gonflant de toujorus devoir se taper du code (dans unlangage que l'on ne prtique pas forcement) a chaque fois que quelqu'un veux explique quelque chose.

cedric