Discussion :

[Alikendarfen]

Bonjour,

Un petit problème... je ne sais par quel bout le prendre.

Merci de vos contributions.

L'objectif est d'affecter un travail à des ressources matérielles selon une contrainte liée au nombre de personnes pour les utiliser (une personne est nécessaire par ressource et une personne ne peut utiliser qu'une ressource à la fois).

A chaque ressource matérielle correspond un calendrier indiquant l'occupation actuelle de la ressource.
Ce calendrier est défini par un ensemble ordonné d'intervalles ]d ; f] où "d" est la date de début et "f" celle de fin. Chaque intervalle indique que la ressource est déjà occupée sur cette période.
Les "trous", intervalles non définis de l'ensemble, indiquent que la ressource est disponible.

Nous avons également le calendrier des ressources humaines.
Ici nous connaissons un unique calendrier.
Celui ci est constitué d'un ensemble ordonné d'intervalles valués : (]d ; f], x)
Où "d" est la date de début, "f" la date de fin et x le nombre de personnes disponibles sur cette période.
Par convention, une période sans intervalle indique qu'aucune personne n'est disponible.


Voici maintenant le problème :

Soit un travail nécessitant une durée de travail D. Ce travail doit être réparti sur différentes ressources.

Nous voulons choisir n (donné) ressources matérielles pour effectuer ce travail au plus tôt à partir d'une date donnée D.

Est-il possible de trouver une solution sans analyser toutes les combinaisons ?
Comment trouver ces n ressources ?

Les contraintes :

Utiliser un langage de type C/C++/C# ou Java (aucun moteur d'inférence n'est disponible a priori, comme prolog, programmation par contraintes).

La performance : cet algo sera utilisé des milliers de fois dans un algorithme plus large avec une forte contrainte de temps de réponse.

[Zavonen]

Peut être n'ai-ja pas très bien compris, mais
Ce problème me parait simple avec une représentation adéquate des données.
J'ai eu par le passé à résoudre des problèmes de gestion analogues (gestion d'EMOP équipes mobiles d'ouvriers).
Pour une planification sur l'année.
Prévoir pour les ressources une matrice binaire A:
Les lignes représentent les ressources
Les colonnes les jours.
Ainsi un 1 placé sur la ligne n°7 et la colonne 35, signale, par exemple que la ressouce n°7 est disponible le 35-ième jour, et un 0 placé sur le ligne n°2 et la colonne 200 indique que la ressource n°2 est indisponible le 200-ième jour de l'année.
Pour le personnel un tableau unidimensionnel B suffit, le contenu de la case i correspond au nombre de personnes disponibles le jour i.
Maintenant si on a une tâche nécessitant 2 personnes et 2 ressources pendant x jours à accomplir à la date D, pour le savoir on se reporte à la colonne D de la première matrice et on effectue un balayage sur les lignes pour un total t(D). On regarde simultanément si B[D]>=2.
On regarde ensuite si ces conditions sont à nouveau réunies pour D+1, D+2, ...,D+x si oui c'est OK pour la date D.
Si pas OK on essaie avec D+1 and so on..
On peut même spécialiser les tâches et les ressources.
On peut même programmer des tâches 'à trous'.
Telle type de tâche nécessite la ressource 1 et la ressource 5, par exemple.
NB: La représentation initiale sous forme d'intervalles me parait inadéquate, et je crois qu'il est bon d'en changer dès le début.

[Alikendarfen]

Merci Zavonen.

J'avais pensé à cette représentation, puis l'avais écartée. Plusieurs raisons :

- La première, la plus mauvaise, est que je souhaite rester à la minute sur des calendriers portant sur plusieurs semaines. Bon c'est la plus mauvaise raison parce qu'au total ça ne génère pas de volumes gigantesque.
- La seconde est que cette fonction d'affectation fait partie d'un tout plus large impliquant des retours arrière nombreux. Ceux ci impliqueraient des copies de la représentation des calendriers à chaque choix. Sur les tests élémentaires que j'ai effectué, cela pèse beaucoup.

Cependant, je vais réanalyser tout cela dans la voie que tu indiques.

Merci encore

[benDelphic]

salut
cela me parait comme une version du scheduling .
une représentation Gantt peut t aider énormément.
sinon essaye le Backtracking.