ordonnancement, graphes, tâches

Bonjour,
Je cherche à réaliser un petit logiciel permettant de gérer mes projets et donc de travailler avec GANTT et PERT/CPM. J'aimerais pour cela que mes algo fonctionnent et soient si possible optimisés (ordonnancement de 1000 à 10000 tâches).

- Les dépendances entre tâches sont un graphe orienté (relation de précédences)
- J'ai des tâches parentes dont la période doit correspondre à min(début((taches_filles)) --> max(fin (tâches_filles))
- des jours de travail et des jours chômés

Ma question est double:
- Quelles sont les structures de données les plus adaptées
- Quels aglos employer pour
- savoir si le graphe ne comporte pas de circuit
- définir le rang de chaque tâche
- gérer mes jours de travail / repos
- déterminer mes dates de début et de fin compte tenu de ces contraintes.

J'ai déjà regarder sur internet et sur le forum pour ces questions mais je n'ai rien trouvé de convainquant.

Merci d'avance pour votre aide! ;)

Citation:

---

Envoyé par AP

- J'ai des tâches parentes dont la période doit correspondre à min(début((taches_filles)) --> max(fin (tâches_filles))

---

Je ne comprends pas cette contrainte

Citation:

---

Envoyé par AP

- Quelles sont les structures de données les plus adaptées

---

Le graphe est en général peu dense et on le représente par la liste des successeurs

Citation:

---

Envoyé par AP

- Quels aglos employer pour
- savoir si le graphe ne comporte pas de circuit
- définir le rang de chaque tâche

---

Ca ce sont des algos classiques de la théorie des graphes que tu trouveras sur internet ou dans n'importe quel bouquin traitant de PERT

Citation:

---

Envoyé par AP

- gérer mes jours de travail / repos
- déterminer mes dates de début et de fin compte tenu de ces contraintes.

---

Cela dépent si tu as un critère d'optimisation. Pour les dates au plus tôt, tu peux calculer comme dans le PERT classique sauf que si cette date tombe dans une période de repos, tu mets sa date de début au plus tôt à la fin de cette période.
Pour la contrainte parent/fille, je n'ai pas compris ce que tu voulais exactement...

Merci pour votre réponse.
Par tâche parente j'entends une tâche qui regroupe des tâche filles (dans l'exemple suivant: Etude)
http://img100.imageshack.us/img100/1...enttaskro1.png

Je pense que pour le groupe (tâche parente pour toi), cela doit être modélisé par la structure de donnée que tu choisis.

Citation:

---

Envoyé par AP

Merci pour votre réponse.
Par tâche parente j'entends une tâche qui regroupe des tâche filles

---

Dans ce cas-là, il semble suffisant de faire l'ordonnancement des tâches filles uniquement et, une fois leurs dates calculées, d'en déduire les dates des tâches parent.

Merci Francis et le prog fou pour vos réponses.
J'ai cependant une question supplémentaire:

pour un graphe non orienté, il est facile de trouver si il y a un cycle en faisant un parcours en profondeur en marquant son passage. Pour un graphe orienté défini par sommet, liste de successeur, je n'ai pas réussi à trouver sur internet une méthode simple et zfficace pour déterminer la présence de circuit lors de l'ajout d'un arc. Savez-vous comment faire?

Merci par avance ;)

Citation:

---

Envoyé par AP

pour un graphe non orienté, il est facile de trouver si il y a un cycle en faisant un parcours en profondeur en marquant son passage. Pour un graphe orienté défini par sommet, liste de successeur, je n'ai pas réussi à trouver sur internet une méthode simple et zfficace pour déterminer la présence de circuit lors de l'ajout d'un arc. Savez-vous comment faire?

---

Le plus simple est là aussi de faire un parcours en respectant l'orientation des arcs. Il faut partir d'un noeud sans prédécesseur (s'il n'y en a pas, c'est que le graphe a forcément un circuit). Lors du parcours, si on retombe sur un noeud déjà visité, c'est qu'il y a un circuit.

Merci pour ta réponse Francis. :)
J'ai essayé de faire ce que tu m'as préconisé mais malheureusement cela ne fonctionne pas trop.
Pourrais-tu me donner pus de détail sur la partie parcours du graphe (utilisation de pile, file, ...)

Merci par avance !

EDIT: petite précision mon graphe est défini par liste d'adjacence

J'ai vu que ce point précis était maintenant discuté dans le thread
http://www.developpez.net/forums/sho...d.php?t=208872