generation d'emploi du temps Fermé

Question

salut je suis un etudiant qui fait un projet concernant l'emploi du temps la prb c'est la generation d'emploidu temps si qlq a une idee sur des algorithme de generation d'emlpoi du temps m'aide svp
merci d'avant

mamiemando · Accepted Answer

Les problème de planification et de génération d'emploi du temps sont des problème classique de la recherche opérationnelle. Le mieux ce serait de faire une recherche google sur ces problématiques. Si tu disposes de solveurs genre COIN et CPLEX tu peux réutiliser les formulations exactes que tu trouveras (problème linéaires en nombres entiers etc...), sinon il faut plutôt recoder une recherche locale.

Dans tout les cas il faut te demander
- ce que tu cherches à optimiser
- quelles sont les variables
- quelles sont les valeurs que peuvent prendre ces variables
- quelles sont les contraintes

Bonne chance

katyoucha · Answer

salut
j ai lu votre intervention, moi aussi j ai le meme sujet;je dois realiser un generateur d emploi du temps.
je vous pouriez m aider ça serait vraiment trop sympa.
Merci d avance.

mamiemando · Answer

Un peu de lecture
http://www-poleia.lip6.fr/~fouilhoux/JFRO/article.php3?id_article=8

Bonne chance

katyoucha · Answer

merci bcp de m avoir repondu.
j essai de lire cette doccumentation, mais je vous nie pas que je commence à avoir peur surtout que je dois la realiser en 7 semaine et ça sur uneplatforme j2EE

mamiemando · Answer

Commence déjà par répondre au post <1>. 
1- quelles sont les variables ? (cours ? classe ? prof ? matière ?)
2- quelles sont les contraintes ? (par exemple un prof de peut donner qu'un cours à la fois, un emploi du temps doit etre consitué de temps d'heure de telle matière, les heures/jours possibles sont... etc)
3- quel est l'objectif ? favoriser les pauses le midi ? compresser l'emploi du temps le plus possible ?

Ensuite demande toi quelle méthode tu vas utiliser pour résoudre ton problème :
1- une résolution exacte avec un solveur genre cplex ou coin (sachant qu'en 7 semaines si tu as pas d'exemple et que tu en as jamais fait il vaut mieux oublier)
2- une résolution approchée (recherche locale)

En tout cas si tu n'as jamais programmé et que tu n'as pas ton modèle mathématique à ta place je commencerais à m'affoler assez sérieusement.

katyoucha · Answer

merci bcp pour vos reponses rapides.
au fait je suis eleve ingenieur en 4 eme année,mais franchement j ai jamais programmer un truc du genre.
on m a demandé de le faire sur un palteforme j2ee.
je me suis doccumenté un peu sur les systeme multi agent,mais franchement j ai rien piger..
j aimerai bien savoir le truc le plus facile pour faire ce genre de truc.est ce que je dois absolment passer par un modele mathematique?et qu est ce que voulez vous dire par "solveurs".
merci d avance

mamiemando · Answer

C'est quoi comme école ?
Tu as eu des cours de recherches opérationnelle dans ton cursus ? Si oui as-tu entendu parlé de méta heuristique, de recherche locale, de simplexe, ou de branch & bound ?
Pour ce qui est des solveurs : as-tu déjà entendu parler de cplex ou de coin ?
Concrètement c'est un sujet de stage ou un projet donné par un de tes profs ?

Concrètement il faut :

1) définir par écrit ce qu'on cherche (variables), ce qu'on aimerait idéalement (objectif), ce qu'on ne veut pas (contraintes).

2) transformer chacunes des contraintes et l'objectif sous forme d'expression mathématique (inéquations, inéquations, contraintes de domaine,...). De manière générale il faut essayer d'avoir un seul objectif (le critère qu'on va optimiser), des contraintes ayant une "bonne tête" (par exemple préférer des contraintes linéaires à des contraintes quadratiques). Les méthodes approchées servent en particulier quand un problème est trop difficile à résoudre à l'exact. Tu auras alors défini ce fameux modèle mathématique.

3) Ensuite il faut te demander si tu veux la (une) solution optimale (résolution exacte) ou si tu peux te contenter d'une résolution approchée. Le choix de la méthode de résolution dépend fortement de la taille du problème, de la forme des contraintes etc...

a- Une résolution exacte est généralement plus longue (Branch & bound + simplexes) et nécessitent à priori un solveur comme coin ou cplex. Dans ce genre de modélisation on a intérêt à utiliser dans la mesure du possible des variables continues et des contraintes linéaires. Cf simplexe, branch and bound, branch and cut... 

b- Une résolution approchée est plus rapide mais reste approchée et on ne connaît pas forcément le gap entre la solution trouvée et la solution optimale. C'est en général assez simple à programmer (cf meta heuristiques, recherche tabou par exemple). Ces approches sont particulièrement adaptées quand on a beaucoup de variables discrètes (variables entières par exemple) bornées (par exemple {0,1,2,3}. A noter que dans cette approche on peut aisément manipuler des variables discrète non numériques. Cf par exemple un tutoriel sur les CSP et les métaheuristiques...


Bonne chance

mamiemando · Answer

Je pense que tu devrais déjà demandé à ton encadrant 
- quelle sont les contraintes
- comment il veut que le problème soit résolu (exact, approché ?). demande-lui si dans son idée il voulait que tu utilises un solveur (cf google pour voir ce que c'est).
- lire des présentations de recherche opérationnelle sur la plannification d'emploi du temps (cf lien que je t'ai donné)
- lire un cours pour te raffraîchir la mémoire.
En tout cas ne perds pas de temps car si tu dois revoir des bases de RO, trouver ton modèle, et ensuite le coder, ça te laisse vraiment très peu de temps.

katyoucha · Answer

Salut
Mon encadrant n est pas initié à ça, j ai l impression de nager tt seul.En plus je passe le stage à distance ce qui veux dire que je vois mon encardrant tres rarement.
je crois que je vais commencer par lire les presentation que vous m avez donner.
cordialement.

mamiemando · Answer

Yep, bonne lecture.

mamiemando · Answer

Ben tu reviens sur le forum, tu expliques ce que tu as fait, ce qui te bloque etc, avec un titre explicite. Ou tu continues dans ce thread...

Utilisateur anonyme · Answer

STP moi aussi je travaille sur le mème projet alors si t'a fait UML pour la modélisation je te prie de me passer le diagramme de déploiement,c'est vraiment urgent merci

mamiemando · Answer

Ca me surprendrait katyoucha n'a même pas son modèle, ça me semble prématuré dans son cas de commencer à coder.

katyoucha · Answer

cher rajensias,
Come notre ami mamiemando a dit j ai meme pas fait le modele, mais je reste optimiste,car au fait j ai vu une lumiere un peu diaphane.
j ai trouvé un truc qui va vraiment  aider dans la conception et  le code.
Si ça vous derange pas donnez moi votre msn et on partagera nos idées.
Cordialement.

mamiemando · Answer

Désolée je fonctionne uniquement par le forum en ce qui me concerne.

katyoucha · Answer

Salut 
J ai demandé l msn de rajensias, je me suis di que peut etre on peut etre un binome virtuel:)
on a le meme projet et peut etre meme on est de la meme ville.
Cordialement.
email:katyoucha@gmail.com

katyoucha · Answer

Salut
je me demande si vous avez enfin generer votre emploi du temps?
merci d avance

yves_4309712 · Answer

Bonsoir, tu trouveras exactement ce que tu cherches ici :
https://cloud.bitang.net/FR/acceuil.aspx

Le logiciel s'appelle Academy System
Il est disponible en version :
- windows : client-serveur
- web : ASP .NET

Il beaucoup plus de fonctions que ce que tu as demandé.
- élèves/étudiants, dossiers, parents, inscriptions, absence, infirmerie...
- recouvrement des frais de scolarité, moratoire, réduction, augmentation...
- matières, enseignants, programme officiel, emplois de temps, cours...
- génération automatique des emplois de temps
- notes, conseil de classe, bulletins, relevés, statistiques, analyse...
- stages, travaux de recherche, jury, thèses, soutenances, diplômes...
- bibliothèque, librairie, parc informatique, parc automobile, location, dépôts, stocks...
- autres dépenses et recettes

Pour états il y en a de toute sorte
De plus tu as plusieurs options d'administration :
utilisateur, groupe, droit, audits...

Generation d'emploi du temps

18 réponses

Discussions similaires