Discussion :

[romfret]

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 ?
Tout piste m'interesse

Merci de m'orienter !

[pseudocode]

Voila l'idee. J'ai cherche du cote d'un algorithme d'ordonnancement mais je n'arrive pas a trouver ce qui me convient.

Il te faut plutôt un algorithme de réservation/booking de ressources.

Une idee d'un algorithme existant se rapprochant de mon probleme ?
Tout piste m'interesse

Ca se rapproche des algos de type "système réducteur", avec du packing (vertical) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
date:            01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17
Paul :              PPPPPPPPPPPPPPPPPPPP
Marc :                                      MMMMMMMMMMMMMMMMMMMM
Jean :                             JJJJJJJJJJJJJJJJJ
 
Emplacement 1 :  --------------------------------------------------
Emplacement 2 :  --------------------------------------------------

[romfret]

Ok merci pour ces infos, je vais fouiller

[romfret]

Bon après des recherches, j'ai eu quelques pistes de base à adopter.

On m'a conseillé l'algorithme "Hill Climbing".

Sinon, que pensez-vous de l'algorithme des noeuds-chapeaux ?
http://www.developpez.net/forums/d51...e/#post3078887

Voilà je parcours un peu tous les algorithmes existant pour le moment, je n'ai pas vraiment de connaissances dans le domaine de ce genre d'algo, tout cela me parait encore flou.

Voilà où j'en suis pour le moment, des suggestions ? ^^

[pseudocode]

Bon après des recherches, j'ai eu quelques pistes de base à adopter.

On m'a conseillé l'algorithme "Hill Climbing".

C'est plus une "technique générale" qu'un algorithme particulier, mais oui c'est une bonne approche

Sinon, que pensez-vous de l'algorithme des noeuds-chapeaux ?
http://www.developpez.net/forums/d51...e/#post3078887

Hum... L'algo de rayrole n'est pas vraiment fait pour optimiser l'allocation des ressources.

[Graffito]

On peut utiliser une approche qui consiste à attribuer un poids (coefficient de difficulté à chaque demande) puis à attribuer les emplacements en traitant en priorité les demandes les plus difficiles.

Pour calculer le coefficient de difficulté, on peut prendre l'ensemble des demandes et faire une attribution dans un ordre aléatoire en prenant le premier emplacement dispo. Une fois ces allocation faites, on atttribue à chaque demande un poids égal au nombre d'autres emplacements susceptibles de satisfaire la demande. Les demandes les plus difficiles auront un poids égal à 0 et les plus faciles (une canadienne en janvier) auront un poids élevé pour ). Pour départager les ex-aequo, on pourra refaire un calcul avec une allocation initiale réalisée avec seulement 80% des demandes.

Après calcul des coeff de difficulté, on attribue donc les emplacements en traitant en priorité les demandes les plus difficiles. Il reste des echecs que l'on peut "retraiter" en faisant des permutations. Une allocation par permutation consiste à trouver un emplacement qui pourrait être dispo à condition de bouger des demandes plus faciles vers d'autres emplacements pouvant convenir à ces demandes. On peut évidement améliorer le processus en cascadant plusieurs permutations (en veillant bien à ce que les mouvements portent sur demandes moins difficiles).