Algo de placement par rapport a des periodes donees
romfret1
Messages postés6Date d'inscriptionmardi 18 mai 2010StatutMembreDernière intervention14 février 2011
-
11 févr. 2011 à 20:59
JulSoft
Messages postés354Date d'inscriptiondimanche 3 juin 2001StatutMembreDernière intervention11 mars 2013
-
15 févr. 2011 à 01:15
Bonjour le forum,
Dans un projet de Gestion de camping, je voudrais un algorithme permettant l'optimisation d'attributions d'emplacements par rapport aux periodes reservees par un camper.
Je m'explique avec un petit exemple tres simpliste:
Soit un camping a 2 emplacements.
Paul reserve du 2 au 8. => Emplacement 1 attribue
Marc reserve du 10 au 16. => Emplacement 2 attribue
Si Jean veut reserver du 7 au 12, aucun emplacement ne sera disponible !
(Alors qu'il aurait ete possible en attribuant a Marc l'emplacement 1)
Voila l'idee. J'ai cherche du cote d'un algorithme d'ordonnancement mais je n'arrive pas a trouver ce qui me convient.
Une idee d'un algorithme existant se rapprochant de mon probleme ?
Toute piste m'interesse
romfret1
Messages postés6Date d'inscriptionmardi 18 mai 2010StatutMembreDernière intervention14 février 2011 13 févr. 2011 à 16:34
Salut,
Merci pour ta réponse et ton enthousiasme ! =)
J'ai lu tes 3 liens, je trouve cela intéressant mais le problème est que ça reste super flou. Je n'ai aucune expérience dans le domaine de ce genre d'algorithme, je ne fais que découvrir ce qui existe pour le moment, après pour les comprendre plus en profondeur c'est autre chose... =/
Effectivement, le Hill Climbing semble être une bonne piste, mais m'a l'air relativement compliqué au premier abord, j'ai du mal à y projeter les données de mon problème.
Je continue à regarder tout cela, si tu a d'autres idées n'hésite pas
romfret1
Messages postés6Date d'inscriptionmardi 18 mai 2010StatutMembreDernière intervention14 février 2011 13 févr. 2011 à 17:37
Bon, au fil de mes recherches, je pense avoir trouvé quelque chose d'intéressant :
L'algorithme des noeuds-chapeaux (ou algorithme de Rayrole). Je pense que ça pourrait être une bonne base.
JulSoft
Messages postés354Date d'inscriptiondimanche 3 juin 2001StatutMembreDernière intervention11 mars 2013 13 févr. 2011 à 18:46
PErso j'ai un problème un poil différent à organiser (plutôt une question d'optimisation de ressources en fait), du coup je vais attaquer Hill Climbing et voir comment on peut essayer d'y projetter un problème du type "allocation de ressources"
Vous n’avez pas trouvé la réponse que vous recherchez ?
romfret1
Messages postés6Date d'inscriptionmardi 18 mai 2010StatutMembreDernière intervention14 février 2011 13 févr. 2011 à 22:27
Ok merci beaucoup !
De mon coté je cherche toujours d'autres pistes, j'ai du mal à attaquer quelque chose de concret =/ . Je vais tout de même essayer de comprendre plus en détail l'algo de Rayrole. Le problème avec cet algorithme est que je ne vois pas comment y intégrer le fait d'avoir plusieurs "Emplacements".
JulSoft
Messages postés354Date d'inscriptiondimanche 3 juin 2001StatutMembreDernière intervention11 mars 2013 13 févr. 2011 à 22:29
Je me suis posé la même question en le découvrant (Rayrole donc) sur wikipedia tout à l'heure... Bien pour planifier pour un seul emplacement, par contre plusieurs j'ai du mal à voir...
BunoCS
Messages postés15472Date d'inscriptionlundi 11 juillet 2005StatutModérateurDernière intervention25 mars 2024103 14 févr. 2011 à 10:58
Hello,
Je me rappelles quand j'étais étudiant la tonne d'erreurs qu'on retrouvait dans l'élaboration du planning de la semaine, avec les réservations de salles etc.
Du coup, je ne pense pas qu'il existe un algo vraiment efficace.
Bon courage en tout cas...
@+
Buno
----------------------------------------
L'urgent est fait, l'impossible est en cours. Pour les miracles, prévoir un délai...
JulSoft
Messages postés354Date d'inscriptiondimanche 3 juin 2001StatutMembreDernière intervention11 mars 2013 14 févr. 2011 à 11:04
Hmmm toujours étudiant, donc j'ai la joie d'avoir des planings automatiques. Chez nous ça marche pas trop mal. Il parrait (d'après le prof qui s'en occupe) qu'il y'a un soft d'optimisation derrière (un truc du genre Hill Climbing dans l'idée), et que les retouches sont faites à la main.
JulSoft
Messages postés354Date d'inscriptiondimanche 3 juin 2001StatutMembreDernière intervention11 mars 2013 15 févr. 2011 à 01:15
J'ai lu la discussion sur programmez... En gros, les dernières propositions reviennent à faire de l'optimisation (dans le genre Hill Climbing, ou similaire).
On part d'une solution existante, et on cherche une permutation permettant de l'améliorer (genre rajoutter une réservation). Si on peut le faire, alors on considere que la solution est acceptable,e t on cherche à lôptimiser encore. Quand on peut plus, alors elle est (localement) optimale. Après, c'est pas certain que globalement elle soit la meilleure...
C'est implémentable relativemetn facilement à mon avis (tester si on peut rajoutter/déplacer une réservation est assez simple, le faire aussi). Le plus complexe est faire en sorte de ne pas tomber dans une boucle infinie (réservation r1 sur A déplacée en B, puis redéplacée en A et aisni de suite).