Atelier de création
d'un outil MPM.


Objectif de l'atelier.

Ecrire un programme en Visual Basic qui, à partir d'un tableau contenant :

  • des tâches,
  • leur durée,
  • les contraintes d'antériorité entre ces tâches,

donne les dates au plus tôt et dates au plus tard de toutes les tâches, classées par niveau. Vous pouvez télécharger la version de Sébastien PASTORE pour voir le résultat (puis cliquer sur random). Nécessite le RunTime VB5.

Cet atelier est présentable à l'épreuve pratique, dans les compétences suivantes (par ordre décroissant de pertinence) :

  • C32 - Développer à l'aide d'un langage de programmation procédural ;
  • C34 - Développer à l'aide d'un langage de programmation à objets (à condition de choisir une structure de données qui soit une classe d'objet, ce qui n'est pas le cas ici). ;
  • C33 - Maquetter une application, la développer à l'aide d'un langage de programmation événementiel (à condition de faire les améliorations graphiques) ;
  • C31 - Gérer un projet de développement de logiciel (à condition de rajouter le suivi de projet et/ou la gestion de ressources).

1
Choix des structures de données.

Réfléchissez aux structures de données que vous allez utiliser pour stocker le tableau des contraintes d'antériorité, ainsi que les résultats.

Pour une tâche, il y a des données d'origine (nom, durée, liste des tâches antérieures) et des données calculées (niveau, date au plus tôt, date au plus tard, marge totale, marge libre).

Vérifier que vos structures de données permettent d'implémenter facilement les codes suivants :

Vous devez ensuite implémenter ces structures de données en Visual Basic.

2
Ecriture des fonctions élémentaires
de traitement des tâches.

Sous Visual Basic, écrivez les trois fonctions dont il est question à l'étape précédente. Prenez soin de bien paramétrer vos fonctions (elles reçoivent en paramètre une ou deux tâches).

Rappels sur... Programmer proprement !

Pour que votre programme soit lisible par vous, par le prof et par ceux qui sont susceptibles de maintenir vos applications, n'oubliez pas les points suivants, tous fondamentaux :

  • utilisez des noms de variables explicites, quitte à les rallonger. Par exemple :
    • n'utilisez pas : i, j, k ; n , max ;
    • utilisez : iNiveaux, iTâches, iPrédecesseurs ; NbTâches, NiveauMax ;

  • Indentez le code quand il le faut, et uniquement quand il le faut. Je ne corrigerai pas les codes qui ne sont pas indentés comme il faut. Pour savoir comment indenter, inspirez-vous des algorithmes plus bas.

  • Commenter votre code. En général, un commentaire par fonction suffit (à condition que vous ayez fait un découpage fonctionnel équilibré).

  • En Visual Basic, ajoutez l'option de compilation Option Explicit (qui permet en général d'éliminer 40 à 50% des erreurs).

3
Classer les tâches par niveau.

Ecrivez, en respectant votre structure de données, l'algorithme qui permet de classer les tâches par niveau. N'hésitez pas à écrire un premier algorithme très général, puis à le détailler petit à petit, jusqu'à obtenir un algorithme facilement transposable en Visual Basic.

Pour le choix de l'algorithme, il y a deux écritures possibles :

Pour vous aider, voici les algorithmes (de haut niveau, c'est à dire peu détaillés) de cette étape :

Algorithme récursif (conseillé).

Algorithme très général :

Fonction Niveau (Tâche) : entier
  Si la tâche n'a pas de prédécesseur alors
  | Niveau = 0
  Sinon
  | MAX <- Niveau maximum des prédécesseurs
  | Niveau = MAX + 1
  Fin Si
Fin Fonction

Algorithme un peu plus détaillé :

Fonction Niveau (Tâche) : entier
  Si la tâche n'a pas de prédécesseur alors
  | Niveau = 0
  Sinon
  | Max = 0
  | Pour chaque prédécesseur
  | | Si Niveau (prédécesseur) > Max alors
  | | | Max = Niveau (Prédécesseur)
  | | Fin Si
  | Fin Pour
  | Niveau = Max + 1
  Fin Si
Fin Fonction

A ce stade, il est impossible de donner un niveau de détail supplémentaire : celui-ci va dépendre des choix effectués pour la représentation des données.


Algorithme itératif.

Algorithme très général :

Procédure Niveau()
  Répéter
  | Pour chaque tâche
  | | Si elle n'a pas de prédécesseur et qu'elle n'a pas encore été classée
  | | | Classer la tâche au niveau courant
  | | Fin Si
  | Fin Pour
  | Pour chaque tâche qu'on vient de classer
  | | Supprimer cette tâche de la liste des prédécesseurs des autres tâches
  | Fin Pour
  Jusqu'à ce qu'on ait classé toutes les tâches
Fin Procédure

Algorithme un peu plus détaillé :

Procédure Niveau()
  Niveau_Courant = 0
  Nb_Tâches_Classées = 0
  Répeter
  | Pour chaque tâche
  | | Si elle n'a pas de prédécesseur et qu'elle n'a pas encore été classée
  | | | Niveau de la Tâche = Niveau_Courant
  | | | Incrémente Nb_Tâches_Classées
  | | Fin Si
  | Fin Pour
  | Pour chaque tâche i
  | | Si Niveau de la tâche i = Niveau_Courant
  | | | Pour chaque tâche j
  | | | | Si i est prédécesseur de j alors
  | | | | | Supprimer i de la liste des prédécesseurs de j
  | | | | Fin Si
  | | | Fin Pour
  | | Fin Si
  | Fin Pour
  | Incrémente Niveau_Courant
  Jusqu'à ce que Nb_Tâches_Classées = Nombre total de tâches
Fin Procédure

A ce stade, il est impossible de donner un niveau de détail supplémentaire : celui-ci va dépendre des choix effectués pour la représentation des données.

On constate que la fonction récursive est beaucoup plus courte que la fonction itérative. En effet, le MPM se prête bien à une écriture récursive car la plupart des définitions sont elles-mêmes récursives. Et il est toujours très facile de traduire une définition récursive en une fonction récursive correspondante.

Ce sera également le cas pour les dates au plus tôt et les dates au plus tard, dont la définition est également récursive.

4
Validation des premières étapes
Avec un jeu d'essai.

En Visual Basic :

5
Création d'une tâche finale fictive
pour faciliter la suite des calculs.

Pour résoudre certains problèmes qui vont se poser par la suite, il est conseillé de créer une tâche fictive, qui représente l'étape finale du projet. En général, quand on trace un graphe, cette étape est représentée par un sommet nommé Fin.

Cette tâche fictive a les particularités suivantes :

Modifiez votre programme pour qu'il rajoute automatiquement, dans la structure de données, cette tâche fictive.

Attention, le code que vous allez taper ne doit pas marcher uniquement pour le tableau d'antériorité choisi en exemple, il doit fonctionner quelque soit le tableau d'antériorité, le nombre de tâches...

6
Calcul des dates au plus tôt.

Ecrivez puis validez la fonction qui permet de calculer, pour chaque tâche, sa date au plus tôt.

De la même façon que pour les niveaux, il y a deux algorithmes possibles :

Les algorithmes généraux seront les suivants.

Algorithme récursif (conseillé).

Fonction DatePlusTôt(tâche) : entier
  Si la tâche est du niveau 0 alors
  | DatePlusTôt = 0
  Sinon
  | DatePlusTôt = Maximum des (dates au plus tôt + durée) des prédécesseurs
  Fin Si
Fin Fonction

Algorithme itératif.

Procédure DatePlusTôt()
  Pour chaque tâche de niveau 0
  | DatePlusTôt = 0
  FinPour
  Pour chaque niveau
  | Pour chaque tâche de ce niveau
  | | DatePlusTôt = Maximum des (dates au plus tôt + durée) des prédécesseurs
  | Fin pour
  Fin pour
Fin procédure


7
Calcul des dates au plus tard.

Ecrivez et validez l'algorithme qui permet de calculer, pour chaque tâche, sa date au plus tard.

8
Améliorations possibles.

Toutes ces améliorations ont été développées dans le programme qui accompagne cet atelier.

  Amélioration 1 : calcul des marges (très facile).

Faites calculer au programme les marges totales et les marges libres.

  Amélioration 2 : interface de saisie (difficulté moyenne).

Faites un outil de saisie simplifié au maximum, qui permet à l'utilisateur de saisir un tableau de contraintes d'antériorité en un minimum de temps, ou qui permet éventuellement de lire un tableau de contraintes d'antériorité à partir d'un fichier texte.
  Amélioration 3 : sortie graphique (très difficile).

Faites afficher les résultats sous formes graphique, par exemple comme ceci :



Sébastien PASTORE.