Algorithmique Avancée -->dijkstra

Bonjour à toutes et à tous !

J'ai un problème à résoudre, je dois appliquer un algorithme sur le problème suivant, j'utiliserais bien l'algorithme de dijkstra mais je vois pas comment. Pourriez vous m'aider svp. C'est assez urgent en fait. PLEASSSSSEEEE

SUJET:

Vous venez de créer votre SSII, une Entreprise de métallurgie vous commande un outil de gestion de tâches. Cette entreprise fabrique des pièces sur mesure et chaque pièce commandée est gérée comme un projet. Leur mode de fonctionnement est le suivant :
Première étape : étude de faisabilité par un ingénieur, il en résulte toujours que la pièce commandée est un assemblage d’autres pièces de base
Chaque pièce de base est alors décrite dans l’étude de faisabilité
Grâce à ces descriptions les programmateurs industriels peuvent alors programmer les machines pour qu’elles produisent les pièces de base
L’opérateur déclenche la machine et suit sa fabrication
En fin les pièces sont assemblées par un soudeur homologué ISO 2020


Chacune de ces étapes est effectuée par une et une seule personne, Sachant aussi que l’on peut calculer le temps pour chacune de ces étapes. L’entreprise souhaite automatiser la gestion du planning pour ses employés : les ingénieurs, les programmateurs industriels, les opérateurs et les soudeurs.

Les utilisateurs
Les utilisateurs de cette application seront les chefs d’ateliers. Ils devront simplement saisir une liste de tâches, les dépendances entre ces tâches en fonction de chaque projet (pièce commandée). Une fois cette saisie effectuée, une analyse est déclenchée et le chef d’atelier obtient des informations type gestion de projet : durée du projet, les dates de début et de fin au plus tôt et au plus tard pour chaque tâche dans le même temps les tâches sont réparties au mieux dans le planning des employés
Besoins de l’entreprise
Vous serez en concurrences avec d’autres SSII. Pour vous départager vous serez évalué sur les points suivants :
1. L’outil devra alors produire automatiquement le planning optimal des employés
2. L’outil devra identifier les tâches critiques et les dates au plus tôt et au plus tard pour chaque tâche
3. Les temps de réponse de votre logiciel
Théories nécessaires
Vous êtes libres sur le langage et les technologies mais vous aurez certainement besoin des théories suivantes :
Théorie des graphes
o Pour modéliser le problème
Calcul de complexité
o Pour justifier l’efficacité de votre solution
IA
o Pour générer une planification optimale


FIN SUJET

Merci d'avance.

Commence par imaginer le graphe des dépendances, chaque arc étant une durée pour accomplir une tâche, par exemple.

Bonjour.

Ton projet ressemble à de la recherche opérationnelle :

http://www.nawouak.net/?doc=course.o...duling+lang=fr

Je voulais savoir si mon choix de l'algo de dijkstra est bon, ou est ce qu'il faut utiliser un autre?

Bonjour.

L'algorithme de Djikstra est très intéressant à partir du moment où les valeurs des arcs du graphe sont positives ou nulles. Il permet de déterminer les dates au plus tôt. Il est plus optimisé que celui de Bellman, mais il est un peu plus complexe à mettre en place. L'algorithme de Bellman sera intéressant pour la détermination des dates au plus tard. J'en déduis que tu vas utiliser la méthode PERT et les graphes (détermination des tâches critiques).

Je ne dois pas utiliser PERT, je dois utilisé un algo, celui qui est le plus adapté au sujet.

Le problème c'est qu'il y a plusieurs algos qui sont adaptés au sujet, pas un seul...

Citation:

---

2. L’outil devra identifier les tâches critiques et les dates au plus tôt et au plus tard pour chaque tâche

---

Si ce n'est pas la méthode PERT ou assimilée qui doit être utilisée ici, bah j'ai rien compris.

Pas faux... mais si je dis qu'il faut un algo c'est parce que mes tuteurs me bassine comme quoi il faut utiliser un algo

La méthode PERT ne sert qu'à modeliser le graphe sur lequel tu va appliquer l'algorithme . pour déterminer les dates au plus tot et au plus tard il faut rechercher un plus long chemin ; donc l'utilisation de l'algorithme de djkstra ( modifié bien sur ) ou de bellman ou un quelconque algorithme est valide .