--- title: La méthode PERT, optimiser la gestion des tâches tags: algorithmie robots: noindex, nofollow author: Julien Noyer --- # La méthode PERT, optimiser la gestion des tâches ![](https://i.imgur.com/u7dIrJu.jpg) Dans la cadre d'__algorithmes__ qui intégrent des __processus et des fonctionnalités différentes__, il peut être intéressant de s'interroger sur leurs __interconnexions__ et leur __enchainement__ afin d'optimiser leur fonctionnement. Nous allons prendre pour exemple le cas classique du [__voyageur de commerce__](https://fr.wikipedia.org/wiki/Problème_du_voyageur_de_commerce) en exemple pour explorer la méthode du diagramme de [PERT](https://fr.wikipedia.org/wiki/PERT). # L'algorithme du voyageur de commerce ![Les VRP - Remords et tristes pets - 1989](https://i.imgur.com/k18oJ9U.jpg) Cas d'étude classique en algorithme, [le voyageur de commerce](https://fr.wikipedia.org/wiki/Problème_du_voyageur_de_commerce) - ou vendeur représentant placier a.k.a. [VRP](https://www.youtube.com/watch?v=USpiBMaYwlY) - et ses problématiques pour arriver à vendre son produit font partie d'exeption qu'__aucun algorithme n'arrive à résoudre__. Nous n'allons pas tenter de le faire mais nous baser sur __une partie de sa problématique__ en listant une suite de tâches qu'il doit réaliser chaque jour dasn le cadre de sont métier. ## Organiser une journée type ![](https://i.imgur.com/GGX3MXW.jpg) Pour commencer nous allons __lister les étapes de façon purement subjective et arbitraire__ pour permettre à notre VRP de démarrer une journée parfaite : - Se laver - Prendre un petit déjeuner - Se brosser les dents - Appeler la centrale pour avoir sa liste de clients du jour - Définir l'itinéraire du jour - Payer la facture d'hotel - Prendre la voiture En analysant rapidement cette liste nous pouvons constater que les tâche à faire sont __plus ou moins longues__ et que l'enchainement des tâche suit un __ordre plutôt logique__ pour permettre à notre VRP de commencer sa journée de façon idéale. Il à néanmoins __des contraintes de résultat__, sa direction lui à fait le reproche de __prendre trop de temps le matin__ pour se préparer et lui demande de bien vouloire __accélérer le mouvement__ - toutes ressemblance avec un fait réél serait purement fortuite. ## Définition de la méthode PERT ![](https://i.imgur.com/cfSaiYc.jpg) La méthode [PERT](https://fr.wikipedia.org/wiki/PERT) est une méthode conventionnelle utilisable en gestion de projet, ordonnancement et planification développée aux États-Unis par la marine américaine dans les années 195__0. __Un diagramme PERT__ représente le ____planning des tâches__ à effectuer pour une action à réaliser et les __délais nécessaires__ à la réalisation de chaque tâche. Reprenons la liste de notre VRP et plaçons la dans un tableau pour y associer un temps de réalisation pour chaque tâche : ![](https://i.imgur.com/cVM1jMy.jpg) Nous savons à présent que notre VRP __prend une heure pour se préparer__ mais que dans sa liste de tâche, il doit __appeler sa centrale__ pour connaitre sa liste de clients. Le VRP n'est __pas maître de ses horaires__ de travail mais il connait ses contraintes et le cadre dans lequel il travail. Nous allons donc à présent lister __les contrainte du VRP__ afin d'avoir une vision claire de son programme : - Le VRP doit mettre __moins d'1 heure à se préparer__ - Le VRP doit __attendre des informations de la centrale__ - Le VRP doit être __le plus tôt possible chez un client__ ## Définir les liens entre les tâches Avec toutes ces données nous pouvons à présent aider notre VRP à __optimiser son temps de préparation__ pour être encore plus efficace grâce à la méthode [__PERT__](https://fr.wikipedia.org/wiki/PERT) et au diagramme que nous pouvons réaliser. Dans un premier temps nous plaçons les tâches dans des "cartes" contenant __plusieurs cases que nous allons relier entre elles__. ![](https://i.imgur.com/EMbmPA3.jpg) Dans les tâches que le VRP doit réaliser nous constatons __les tâches sont liées mais pas nécessairement toutes ensemble__. Nous avons placer sur le schéma ci-dessus un graduiation de temps allant de __1 à 60 minutes__ pour nous permettre de définir deux informations importantes pour nos tâches : - Le moment ou la tâche doit commencer - Le moment ou la tâche doit être finie ## Définir les temps d'exécution de chaque tâche En plus des liaison entre les tâche nous devons à présent définir le __planning de réalisation__ des tâches en partant du principe qu'elles sont __faites les unes après les autres__. ![](https://i.imgur.com/hIm8F98.jpg) Cette représentation nous offre l'avantage de pouvoir __distinguer 3 groupes de tâches__ dans le planning du VRP : - __Groupe 1__ : se laver payer et partir - __Groupe 2__ : prendre le petit déjeuner, se laver les dents, payer et partir - __Groupe 3__ : appeler la centrale, définir l'itinéraire et partir L'emergence de ces 3 groupes __nous en apprend plus sur les possibilités d'optimisations__ que nous avons pour aider notre VRP à se préparer plus rapidement car nous pouvons à présent __calculer le temps nécesssaire__ à la réalisation des tâches de chaque groupe : - __Groupe 1__ : 10 minutes - __Groupe 2__ : 22 minutes - __Groupe 3__ : 34 minutes Il y à très clairement __le groupe 3 qui se dégage__ selon les informations que nous avons fait ressortir de ce schéma car il est le seul dont __le départ n'est pas consécutif au paiement__ et qu'il à un __temps d'exécution plus long__. ## Organiser et regrouper les tâches Nous pouvons __grâce aux nouvelles données que nous avons généré__ en analysant les tâches de notre VRP, tenter une __optimisation de son planning__ pour lui permettre de répondre aux exigences de sa direction. ![](https://i.imgur.com/7B0N1ZC.jpg) Nous proposons dans notre diagramme de __regrouper les tâches non bloquantes__ ensemble pour que notre VRP puisse les __réaliser en moins de temps__ sans nuire à la bonne réalisation de son but final, à savoir __optimiser son temps de préparation__. Nous prenons des raccourcis dans cette présentation en considérant qu'il est possible de passer un coup de fil en prenant son petit déjeuner ou-bien qu'il est possible de se brosser les dents en même temps que prendre sa douche, ce qui dans le cadre d'un VRP est tout à fait envisageable. La démonstration de l'utilité de la méthode [__PERT__](https://fr.wikipedia.org/wiki/PERT) n'en reste pas moins réélle car si __les tâches__ d'un algorithme peuvent être __traitées en même temps__ de quelque manière que ce soit alors __la rapidité d'exécution de l'algorithme est augmentée__. --- ## Ressources - [__PERT__](https://fr.wikipedia.org/wiki/PERT) _Méthodologie_ - [__Problème du voyageur de commerce__](https://fr.wikipedia.org/wiki/Problème_du_voyageur_de_commerce) _Cas d'étude_ - [__Les VRP__](https://fr.wikipedia.org/wiki/Les_VRP) _Groupe Punk - 1988_ - [__La Gastronomie en Russie__](https://books.google.fr/books?id=684XDgAAQBAJ) _Alphonse Petit - 2015 Collection XIX_ - [Outil pour construire des diagrammes](https://www.lucidchart.com)