Algo de placement par rapport a des periodes donees

Signaler
Messages postés
6
Date d'inscription
mardi 18 mai 2010
Statut
Membre
Dernière intervention
14 février 2011
-
Messages postés
354
Date d'inscription
dimanche 3 juin 2001
Statut
Membre
Dernière intervention
11 mars 2013
-
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

Merci de m'orienter !

11 réponses

Messages postés
354
Date d'inscription
dimanche 3 juin 2001
Statut
Membre
Dernière intervention
11 mars 2013

Hello,

Intéressant comme question. Il me semble qu'en cherchant du côté des algorithmes de génération d'horaires, on trouve pas mal de choses.

A première vue (je n'ai pas lu les articles que je te propose, mais ça semble une base de départ interessante, mais en anglais), jette un oeil là dessus:
http://www.emo.org.tr/ekler/76e76856c7fea3b_ek.pdf (technique de coloration de graphe)
http://secretgeek.net/content/bambrilg.pdf (version génétique)
http://en.wikipedia.org/wiki/Hill_climbing (un algo d'optimisation locale, part d'une solution et essaie de l'améliorer)

Ca devrait te donner une base de départ.

Je n'ai encore rien lu sur la question, mais le problème m'interesse, on va donc creuser un peu ;-)
Messages postés
6
Date d'inscription
mardi 18 mai 2010
Statut
Membre
Dernière intervention
14 février 2011

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

Encore merci pour ton intérêt !!
Messages postés
6
Date d'inscription
mardi 18 mai 2010
Statut
Membre
Dernière intervention
14 février 2011

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.

http://www.developpez.net/forums/d514050/c-cpp/c/contribuez/calendrier-dallocation-ressources-algorithme-rayrole/#post3078887
Messages postés
354
Date d'inscription
dimanche 3 juin 2001
Statut
Membre
Dernière intervention
11 mars 2013

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"
Messages postés
6
Date d'inscription
mardi 18 mai 2010
Statut
Membre
Dernière intervention
14 février 2011

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".

Voilà pour le moment ;-)
Messages postés
354
Date d'inscription
dimanche 3 juin 2001
Statut
Membre
Dernière intervention
11 mars 2013

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...
Messages postés
792
Date d'inscription
mardi 8 juillet 2003
Statut
Membre
Dernière intervention
12 juillet 2019
8
Bonjour,
Ce projet pourrait être un début d'inspiration:
http://www.codeproject.com/KB/recipes/GaClassSchedule.aspx


louis
Messages postés
14955
Date d'inscription
lundi 11 juillet 2005
Statut
Modérateur
Dernière intervention
27 janvier 2021
93
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...
Messages postés
354
Date d'inscription
dimanche 3 juin 2001
Statut
Membre
Dernière intervention
11 mars 2013

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.
Messages postés
6
Date d'inscription
mardi 18 mai 2010
Statut
Membre
Dernière intervention
14 février 2011

Je suis un peu embêter puisque je jongle entre ce forum et developpez.net ou j'ai également quelques pistes.
J'ai penser à une méthode cette après-midi que j'ai posté sur developpez. Je sais pas si j'ai trop le droit de faire ça (un admin me le dira si c'est le cas ;)) mais voici mon post :
http://www.developpez.net/forums/d1037192/autres-langages/algorithmes/algo-placement-rapport-periodes-donnees/#post5778392
Messages postés
354
Date d'inscription
dimanche 3 juin 2001
Statut
Membre
Dernière intervention
11 mars 2013

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).