(précision : je suis nul en maths, g du avoir un max de 15h de cours sur la théorie des graphs, donc je suis un noob total dans le sujet hein, donc je prends tout (cours, liens, explications), pas la peine de m'insulter pour mon ignorance)
 
Voilà : je vais essayer de décrire le problème simplement.
En gestion de projet pour ordonnancer des taches. Chaque tache possède un poids (le temps nécessaire pour l'exécuter), et éventuellement des contraintes (date de début imposée, date de fin imposée, recouvrement possible, taches pré-requises etc...) le but est de trouver un ordonnancement optimal satisfaisants aux contraintes, permettant d'obtenir le temps de projet le plus cours possible.
 
Pour calculer l'ordonnancement des taches, on peut utiliser 2 méthodes :  
- les diagrammes de Gantt (histogramme horizontal avec un baton par tache, la longueur des batons étant proportionnelle à la longueur des taches.
 
- un graph PERT/CPM, dont voici un exemple avec 2 taches seulement :  

 
(explications de la méthode PERT, avec exemple de tableau de taches : http://www.mindtools.com/critpath.html)
 
Le chmin critique est le chemin composé de toutes les taches dont la durée influence la durée totale du projet (en clair)...ce sont des taches n'ayant aucune marge, et que si on les allonge, ou diminue, on change la durée totale du projet (et éventuellement se forme un nouveau chemin critique)
 
On part avec un tableau qui contient les taches à faire, et qui ressemble à ca :  
 
Nom de la tache - Durée - Prédécesseurs - Contraintes éventuelles
 
exemple :  
 
A - 3 - n/a - n/a
B - 4 - n/a - n/a
C - 3 - A,B - n/a
D - 4 - C - peut recouvrir C de 1j
 
Je voudrais un algo (ou des pistes pour le créer) qui me permette de remplir le les infos dans les noeuds (ordonnancement), sortir le chemin critique, et une sorte de liste en chaine de prédécesseur me permettant de dessiner le graph facilement etc...
 
sachant que, pour faciliter, le graph n'a qu'une source, et qu'un puit (taches fictives de durée nulle)
 
Complexification n°1 : sous contrainte de ressources : imaginons qu'on a que 5 gars qui peuvent bosser sur le projet, chaque tache a besoin de X hommes jours...il faut qu'à n'importe quel jour X on n'aie pas plus de 5 gars nécessaires (ce qui peut totalement boulverser l'ordonnancement des aches)
 
Complexification n°2 : la durée peut etre sous forme de loi de probabilité

Cela ressemble vaguement aux problèmes de "bin packing".

d'autres idées ?

up

les trucs qui me passent par la tête sont "méthode des potentiels" ou bien "Ford-Fulkerson" (quoique ce dernier, me semble t'il, s'applique aux graphes de flots)
mais c'est un peu trop loin pour moi ces trucs là pour en dire plus

je comptais bcp sur toi ...
 
nraynaud m'a dit que ct l'enfance de l'art, mais le post a 2j et finalement personne répond ...j'en viens à croire que c pas si facile
 
je sais le faire tourner à la main le graph, le constuire et tout...g les formules pour calculer les numéros...mais je pense qu'il doit y avoir un algo plus systématique...

au niveau code, je ne l'ai jamais vraiment codé ce truc là...
j'ai vu ça en cours de math il y à... 10 ans
donc à part te donner des noms de méthodes qui me reviennent comme ça, je ne puis t'aider plus là
(d'autant que là, j'ai pas hyper le temps de m'y pencher plus et de le faire tout seul...)

ok c pas grave, merci bcp qd même ...

Il est vrai que c'est assez complexe. Deja est tu sur de pouvoir trouver un ordonnancement valide selon les contraintes etablies ?
Sinon, tu ne peux pas le résoudre avec un arbre ton truc ?
Tu aurais en profondeur 0 un noeud factice, en profondeur 1 toutes tes taches en profondeur 2 toutes les taches possibles de realiser suivant la tache parente, etc etc...
Ensuite avec ton arbre de solution, tu vois la meilleure (car pour chaque chemin tu calcules la duree de chacune des taches sur le chemin)

non, y'a ps toujours une solution...à cause des contraintes, c parfois impossible...et des fois y'a un ordonnancement sans chemin critique (cad pas optimal, mais l'optimal n'existe pas)
 
ex :  
B dépend de A
 
C dépend de B
 
on a :  
A = 3 jours
B = 4 jours
C = 3 jours
 
si c a une date imposé de début à 5 jours, c insoluble (c rarement aussi évident, mais c pour shématiser)

et donc jusque la, tu regardais a la main pour voir si c'était possible d'ordonnancer les taches .
Moi je vois la solution de construire l'arbre de solution comme je l'ai dis. Ensuite pour chaque solution, ben tu regardes si elle satisfait toutes les contraintes (faut regarder tous les criteres). Si oui alors tu regardes si elle est meilleure que une précédemment trouvée. Si oui tu la gardes, si non, tu l'ignores.
Bon maintenant tu peux couper des branches de ton arbre de solution (ca serait plus rapide), c'est a dire au fur et a mesure que tu construits les profondeurs, tu regardes en meme temps que les contraintes soient tjs satisfaites. Si non, tu arretes d'explorer la branche. Si oui, tu continues d'explorer la branche en la creusant davantage.

A vu d'oeil , le problème à l'air NP-complet. Une chose est sure : si on parcourt toutes les solutions, il y en aura bien une qui sera meilleure que les autres. En revanche si il y a bcq de taches, cela risque de mettre un sacrée moment avt de cracher la réponse.  
Si tu restes sur une idée de parcours d'arbre fais des recherches sur les algos de branch and bound.
Sinon tu peux regarder du coté des problèmes d'optimisation, tu trouveras des algos pas trop dur à mettre en oeuvre qui te permettent d'aller vers l'optimal (glouton, recuit simulé, méthode tabou....)

c du grec pour moi NP complet...
 
vous avez des liens de cours sur les graphs ?

NP-complet en gros cela veut dire que c'est difficile et que tu ne pourras pas trouver un algo qui donne la solution exacte à tous les coups

si tu passes par Angoulême, j'ai mon poly là sous la main

recherche google :
http://www.iutbayonne.univ-pau.fr/~grau/D/intro.html

Jubijub => en fait faudrait connaître la taille de ton problème. S'il n'est pas trop gros, tu peux tenter la recherche exhaustive sinon d'autres méthodes que la construction de l'arbre des solutions te permettent d'avoir bonne solution en un temps d'attente raisonnable; par contre tu n'est pas sûr d'avoir la meilleure solution.
 
Par "taille du problème" j'entends ici cela clairement par le nombre de tâches.
Par "meilleure solution" j'entends par la que tes contraintes seront toutes satisfaites et que le chemin critique s'effectue en un temps minimal.
Par "bonne solution" j'entends par la que tes contraintes seront toutes satisfaites mais par contre le chemin critique comme tu l'appelles n'est pas sur de s'effectuer en un temps minimal (c'est à dire qu'il pourrait être executée en moins de temps) mais en un temps plus proche de l'optimal que du pire des cas.

ben un gros projet peut avoir des centaines de taches...ca doit pas monter plus haut que quelques milliers...mais déjà 1000 ca fait pas mal de possiblités...

 
OK, donc la recherche exhaustive c'est pas la peine car ça donnerait un arbre de solution avec un facteur de branchement de 1000, c'est trop énorme.
Euh une question, comment faisait tu jusque là pour résoudre de tels problèmes ?  

Bon, je vais au resto, je t'explique comment c'est con après.
 
(drapal déguisé)

lol, merci
 
--> giz : je sais le faire tourner à la main...y'a une méthodologie...
- déjà faut dessiner le graph : pour ca tu repères les transitivités, et après ben tu suis betement ce que dis le tableau (si B dépend de A, alors A est relié à B)
 
si y'a transitivité, ben tu en tiens compte.
 
Après chaque case du petit tableau associé au noeud a une formule particulière, mais qui est néenmoins la même pour tt les neouds du graphe, hormis les extremités.
 
par ex : date au plus tot du neoud X = date au plus tot du neouds X-1 ayant la date au plus tot la plus tardive + durée de X +1, etc...
 
le fait est qu'il n'existe que très peu de graphes valables pour chaque tableau de données...le graph c pas le plus dur à obtenir, c son analyse, et surtout le remplissage des cases...là encore c pas dur, mais c long et fastidieux...et totalement infaisable à la main si y'a plus de 10-15 taches...
 
edit : après c le dessin du graph qui est chiant : faut minimiser les croisements entre branches...on ordonnance les taches par niveau (0 = noeud origine, après tt les noeuds ayant rien comme origine (donc le noeud origine), etc... jusqu'à mettre en dernier le noeud terminal...)
 
les trier par colonne c pas le plus dur, c trouver comment les ranger dans la colonne pour minimiser les croisements...

T'as de la chance, j'ai presque rien bu. Et j'ai trouvé une idée plus simple que mon truc de départ.
 
Je donne le cas le plus simple, j'ai pas d'éditeur java sous la main, donc je le fais au fil de l'eau, on discute de ça et on introduira les contraintes plus tard.
 
Un détail : on a affaire à un graphe dirigé acyclique, c'est important de le préciser, sinon on explose tout. Un exemple de cycle c'est la grue qu'on doit faire monter en même temps que la pile du pont, on l'élimine en déroulant la boucle.  
Je vérifie pas les données saisies.
 
Heu, comme j'ai un trou, je vais supposer que Float c'est bien la marge (j'hésitait entre leeway et margin en plus)
 
je mets aucun cache sauf celui des suivants, la complexité est donc balaise.
 

 
On voit que  
1) on peut avoir plusieur taches de départ
2) on peut avoir plusieurs taches de fin
3) j'ai recopié les équations avec la feinte "computationnelle" suivante : un temps au plus tôt ça se calcule en une seule passe de gauche à droite, donc ça implque des résultats sur les précédents, les temps au plus tard se calculent "au retour" de droite à gauche ça implique donc des résultats sur les suivants. donc calculer les temps de départ au plus tôt de la première tâche, c'est faire l'aller retour, comme dans une interro.
4) Il faut *vraiment* mettre des caches dans la réalité, mais là on a un code plus court, donc plus facile à comprendre.

heu, avec ton sys y'a pas de taches factices en début et fin non ? (en pert c facultatif, en CPM par contre il les faut...les 2 ont marge nulles, la première a des 0 partout, et la dernière a les même en haut et en bas, et marge nulle aussi)...
 
faudrait que je scanne un graphe CPM d'un de mes cours, pour qu'on puisse s'en servir de testcase...
 
en tout cas ^1000, tu assures nraynaud ...
 
je le teste demain au boulot, je te donnerai mon feedback sur la question )

en fait si /o\
 
si tu le fais pas, il va merder /o\

Je passe mon temps à le répéter, mais personne ne me croit.

 
perso, je le crois aussi...

 
euh, les lignes de code que j'ai indiqué par une flèche, la récursivité ne cache pas un arbre derrière les buissons ?    
Sinon avec les 1000 taches ca risque d'exploser.   et le pire c'est que tout l'arbre se construit sur la pile (=> stockage de tout l'arbre).

giz > tu veux pas apprendre l'info avant d'intervenir dans les discussions d'adultes ?
 
Y'a pas que ça qui est récursif. C'est volontairement récursif, le code est calqué sur les définitions (le temps de départ au plus tôt d'une tache est les max des temps des départ au plus tard de ses prédécesseurs, le temps de fin au plus tard d'une tache est le min des temps de départ au plus tôt de ses suivants). Non, il va falloir y aller avec un peu plus que 1000 taches pour exploser la pile, et enfin, la presence de caches diminuerait la profondeur de pile en moyenne.

bon, session scan de tableaux
 
to be edited
 
finalement g percuté que le prof à l'arrache au dernier cours nous avait autorisé à prendre le PDF sur clé USB...
 
==>mon cours d'ordonnancement en PDF (39 pages, mais les 18 premières résument tout...d'ailleurs en le relisant l'algo ressort plus...
 
- l'algo de base qui ressort est le suivant :  
1) trier les taches par niveau, en incluant alpha en niveau 0 et omega au dernier niveau (les fameuses taches fictives)
2) parser ce truc en appliquant les relations d'antériorité données par le tableau (j'ajouterai : tenir compte de la transitivité)
3) faire un prégraphe CPM (donc juste avec le nom des taches) pour chercher une représentation qui minimise les croisements...c facultatif pour résoudre le problème, mais faudra que j'y réfléchisse pour plus tard
4) PREMIERE PASSE (début vers fin) : remplissage des durées au plus tot (début et fin) : l'algo est tel que tu l'a pensé, cad par rapport à l'ancetre immédiat (si plusieurs ancetre, date de fin de l'ancetre le plus tardif)
5) DEUXIEME PASSE (fin vers début) : remplissage des durées au plus tard
6) TROISIEME PASSE (fin vers début) : calcul des marges.
7) génération du calendrier du projet (conversion des dates jour X en date calendrier standard.)
 
8) génération gantt (plus tot plus tard)
9) génération MPM (plus tot plus tard)
 
10) prise en compte de la notion de ressources
11) prise en compte des notions de :  
- recouvrement de taches
- dates imposées
 
12) analyse occupation de ressources, calcul cout/avantage (intégration des contraintes genre astreintes de retard, etc...)
 
13) détection des deadlocks genre projet infaisable, etc...et si possible détection de la tache qui fout le bordel
 
 
voilà

nraynaud > "le temps de départ au plus tôt d'une tache est les max des temps des départ au plus tard de ses prédécesseurs"
 
Pour mettre ca en bon français tu veux dire :
"Le plus tôt que peut commencer une tache a s'executer est égal au pire (le plus tard) des temps de départ de ses predecesseurs??:
 
nraynaud > "le temps de fin au plus tard d'une tache est le min des temps de départ au plus tôt de ses suivants"
 
Pour mettre ca en bon français tu veux dire :
"au pire (le plus tard) une tache se termine au bout du temps auquel la tache suivante parmi les taches suivantes commence au plus tôt"

cf mon poly, où c'est expliqué clairement (par ailleurs la formulation de nraynaud est proche de celle du cours)

up : sauf erreur, je crois pas que ton algo tienne compte de la transitivité (il se base que sur la liste des successeurs ?)
 
un tweak qui me vient à l'idée, serait de détecter la transitivité, et de modifier ensuite la liste des prédecesseurs en en tenant compte...

on peut en tirer quoi de la transitivité ?

et moi les marges elles sont faites à la volée.
 
enfin quand je dis "moi", c'est exactement le même truc que toi, que tout le monde voit en cours, que j'ai refait de mémoire.

on en tire rien, mais c faux si on tiens pas compte...
 
ex :  
- B dépend de A
- C dépend de B et de A
 
le graph doit etre A --> B --> C
et non pas :  
A---------------> C
  \----> B -----/
 
autre remarques : je pense qu'on peut faire les 2 passes retour en 1... edit : ben c ce que tu dis

Oui, mais tout tu truc la, c'est basé sur l'hypothèse suivante :
 
Avant de débuter le projet, on a fait une analyse !    
 
 
C'est pour ca que personne répond    
 

 
------------------------------------------------

up pour nraynaud...
 
sinon est-ce que d'après toi on pourrait intégrer proprement à l'algo le calcul des niveaux ? (avec dans l'optique l'idée d'avoir les taches par niveau, ce qui facilitera la création du graph)

ouaip, le niveau se calcule de manière proche du temps de démarrage au plus tôt
 
Si c'est vrai : une tache a le niveau du max de ses taches précédentes + 1, la tâche de départ a un niveau 0.
 
je te laisse faire le code en petit exercice, tu as un modèle au-dessus et une définition récursive.
 
pour bien te mettre la similarité sous le nez :  
Le temps de démarrage au plus tôt c'est le max des temps de fin au plus tôt des taches précédentes, la tache de départ a une un temsp de démarrage au plus tôt de 0.

je v pas y toucher avant la fin de mon stage (cad 1 semaine) ...mais je v déjà réfléchir à un petit parseur de tableau texte...
 
cad qqc genre un fichier props ou autre, qui donne :  
A-10-*
B-5-A
C-5-A,B
D-2-B
E-10-C,D
 
de la que ca déduise une liste d'antécédents propre, cad avec transitivité :  
A-*
B-A
C-B
D-B
E-C,D
 
et après selon ton algo, on crée pour chaque tache une liste de successeurs, une liste de prédécesseurs, et une variable indiquant son niveau...
 
ton algo est bien trouvé, j'aurais pas pensé au coup de la liste de successeurs, qui pourtant facilite gravement le truc...sinon pour le coup de s'autoenregistrer successeur de ses prédécesseurs, je vois pas où est le mal ? (un coup de pelle à clou ?)
 
edit2 : question : avec une chiée de tache, ca va faire de gros  qd même...vu qu'il y a 2 tableaux par tache...(il est certain que les tableaux sont minuscules, mais bon)