PLANIFICATION et Ordonnancement
Nous en déduisons le réseau PERT correspondant à l'application proposée : Calculs sur le graphe : La méthode PERT a pour but de planifier la durée d'un projet
Ordonnancement de graphes de tâches
Trouver un ordonnancement optimal est alors un défi algorithmique majeur. Plan du sujet proposé. La partie I introduit la notion d'ordonnancement d'un graphe de.
BTS SIO - Ordonnancement. Méthode MPM
6 avril 2021. BTS SIO. Page 2. On ordonne le graphe des tâches par niveaux en ajoutant une tâche ? Début ? et une tâche ? Fin ?. Chaque sommet est
GRAPHES ET ORDONNANCEMENT
Puissances entières et booléennes de la matrice d'adjacence. Fermeture transitive d'un graphe. Pour un graphe sans circuit : niveau d'un sommet niveaux
Chapitre 4 - Graphes dordonnancement 1 Méthode MPM
La marge totale est toujours supérieure ou égale à la marge libre. • On peut faire apparaître sur le graphe d'ordonnancement les marges mais ce n'est pas l'
Thème 17: Problèmes dordonnancement - 17.1 Introduction
De même il y a un chemin critique : A – C – E – fin (il y a tou- jours un chemin critique dans un graphe MPM). 6) Marge totale. On appelle marge totale le
LE PROBLEME CENTRAL DE LORDONNANCEMENT
La durée minimale des travaux est égale à la longueur du plus long chemin de ? à ? dans le graphe potentiel-tâche. Calcul des dates au plus tôt. Ce calcul
Approche par contraintes des problèmes dordonnancement et d
23 sept. 2005 Bellman-Ford alors que celle sur un graphe potentiels-bornes est réalisée par un algorithme du type. Floyd-Warshall. Page 15. 3 PROPAGATION DE ...
Un domaine très ouvert : les problèmes dordonnancement
- Graphique de Gantt. 3.2 Traitement des problèmes d'ordonnancement à contraintes potentielles. Introduction. Ces méthodes permettent d'ordonnancer
Aperçu sur les problèmes dordonnancement
y Recommencer 9 jusqu'à épuisement du graphe. Cette procédure permet de marquer tous les sommets de manière unique puisque G est sans circuit. Exercice proposé
GRAPHES ET ORDONNANCEMENT - ac-toulousefr
transitive d'un graphe •Mettre en œuvre un algorithme permettant d'obtenir les niveaux dans un graphe sans circuit •Représenter géométriquement un graphe en l’ordonnant par niveaux La définition d’un graphe fini simple orienté est limitée à la donnée d’un ensemble de sommets et d’un ensemble d’arcs On considère
M´ethodes d’Optimisation
3 1 LE GRAPHE 31 •N 3 = {g} On en d´eduit le graphe ordonnanc´e en niveaux suivant : Figure 3 3 – Graphe ordonnanc´e - Exercice corrig´e On a repr´esent´e sur les arcs d’origine a la dur´ee op´eratoire de la tˆache a
Lycée de CachanBTS SIO 2 Chapitre 4 - Graphes d - Free
Pour construire un graphe d'ordonnancement on e ectue les étapes suivantes : 1 On commence par déterminer le niveau de chaque tâche dans le graphe (voir chapitre 3) 2 On représente le projet par un graphe pondéré dans lequel : chaque tâche est représentée par un sommet les sommets sont alignés verticalement par niveau
Graphes et ordonnancement
Le graphe obtenu par la méthode MPM a pour sommets les tâches à e?ectuer classées par niveau avec des informations supplémentaires accolées : la date de début au plus tôt la date de début au plus tard la marge totale et la marge libre
Comment ordonnancer un graphe par niveaux ?
Ordonnancer le graphe par niveaux. Tracer le graphe ordonnanc´e en ´evitant que les arcs se coupent. D´eterminer le (les) chemin(s) critique(s). Ordonnancement par niveaux : on se donne le dictionnaire des pr´ec´edents : N0={A},r(A) = 0, on barreAdans le dictionnaire :
Comment trouver le chemin critique sur un graphe ordonnanc'e ?
Le graphe ordonnanc´e : La tˆache L peut d´ebuter 3 jours apr`es le d´ebut de E alors que E dure 7 jours : La tˆache N suit K 3 jours apr`es son d´ebut, K dure 7 jours, K pr´ec`ede aussi Q, M d´ebute 3 joursapr`es le d´ebut de K : La recherche du chemin critique sera e?ectu´ee sur ce graphe.
Quels sont les différents types d’ordonnancement ?
Cours sur les différents techniques d’ordonnancement qui sont nécessaires à la gestion de projet dans l’entreprise, notons le diagramme de Gantt, les méthode PERT et MPM. L’ordonnancement suit des étapes et tient compte des contraintes (le temps, l’antériorité, la production).
Comment expliquer les méthodes d’ordonnancement ?
Il consiste à expliquer, d’une manière simple, les différentes techniques ou méthodes d’ordonnancement telles que PERT et GANTT. Et il commence par présenter certains objectifs des méthodes. 1. Historique 2. LA méthode PERT 2.2. Notions de base 2.3. Représentation graphique des étapes et des tâches dans un réseau 2.4. Normalisation du graphe : 2.5.
PROBLEMES D'ORDONNANCEMENT 105
3EC - JtJ 2021Thème 17: Problèmes d'ordonnancement
17.1 Introduction
De quoi s'agit-il ?
Il s'agit de savoir planifier l'exécution de tâches qui ont une certaine durée, et qui ont entre elles des relations d'antériorité (par exemple, dans les révisions qu'il faut faire avant de passer un examen, il y a des chapitres qu'il faut revoir avant d'autres).Exemple :
L'entreprise Oméga a procédé à la définition d'un certain nombre de tâches à effectuer. On a rempli la colonne " antériorité » avec les tâches qui doivent être exécutées avant celle considérée. Une évalua- tion du temps de chaque tâche a également été proposée. Tâche Durée en semaines Antériorité A 3 B 4 A C 5 AD 2 A E 2 B, C
F 3 D Proposer un agenda des différentes tâches, en indiquant le nombre de semaines minimum puis maximum à entrevoir avant la fin des diffé- rentes tâches. Il existe plusieurs algorithmes possibles pour résoudre les problèmes d'ordonnancement. Les deux plus fréquemment utilisées sont la mé- thode PERT (méthode américaine) et la méthode MPM (méthode française datant de 1960). Concentrons-nous sur cette dernière.Méthode française MPM
(Méthode Potentiel Métra)1) Le graphe de niveau
À partir du tableau, on réalise un premier graphe appelé graphe de niveau dont les sommets sont les tâches et qui permet de mettre enévidence les antériorités :
niveau 1Aniveau 2
C B D EFniveau 3
106 THEME 17
3EC - JtJ 20212) Le graphe orienté
On crée le graphe orienté dont les sommets sont les tâches ; on crée deux tâches fictives qui sont les tâches " début » et " fin » (sous-entendu " du processus »). Les arcs sont les relations d'antériorité immédiate ; ils sont valués par la durée de la tâche source. Chaque sommet comporte 3 zones qui contiennent respective- ment :3) Dates " au plus tôt »
On traite les sommets par niveaux en partant du début.Pour chaque sommet i on note la date t
i qui est la longueur du plus long chemin de la tâche initiale à la tâche i. Le travail ne pourra donc pas être terminé avant 10 semaines. La tâche E ne pourra pas commencer avant 8 semaines, la tâche F avant 5 semaines, etc. débutA D C B F E fin 3 3 345 22
3
Début au
plus tôtDébut auplus tardNom de la tâche
débutA D C B F E fin 3 3 345 22
3 0 03 3 38
5 10
PROBLEMES D'ORDONNANCEMENT 107
3EC - JtJ 20214) Dates " au plus tard »
On traite les sommets en partant de la fin (en marquant 10 pour le sommet " fin »).Pour chaque sommet on note la date
t i* qui est la longueur du plus court chemin de la tâche i à la tâche " fin ». Pour effectuer l'ensemble des tâches en 10 semaines, il faudra avoir commencé la tâche E au bout de 8 semaines, commencé la tâche F au bout de 7 semaines, etc.Exercice 17.1
On considère un ensemble de tâches proposé dans le tableau ci- dessous :Taches Antériorité Duree (jours)
A 3 B 9 C 5 D A 8 E B 4 F B 7G B 20
H C, F 6
I D, E 5
a) Proposer le graphe de niveau. b) Proposer le graphe orienté. c) Compléter les dates au plus tôt et au plus tard.Suite de l'exemple :
5) Tâches et chemins critiques
• Il y a des tâches critiques, celles pour lesquelles on a t i =t i* la tâche E devra obligatoirement débuter durant la 8 e semaine (ni plus ni moins) pour que le processus soit achevé au bout des10 semaines.
• Les tâches critiques définissent un ou plusieurs chemins cri- tiques composés de tâches dont l'exécution ne doit connaître aucun retard pour que le projet soit achevé au plus tôt. débutA D C B F E fin 3 3 345 22
3 0 03 3 38
5 10 0010 78
5 34
108 THEME 17
3EC - JtJ 2021 Par contre, il y a de la latitude pour les tâches qui ne sont pas cri- tiques : la tâche F pourra être démarrée entre la semaine 5 et la semaine 7. De même, il y a un chemin critique : A - C - E - fin (il y a tou- jours un chemin critique dans un graphe MPM).6) Marge totale
On appelle marge totale le retard maximum que peut avoir une tâche sans retarder la fin du projet (les tâches critiques n'ont pas de marge). On l'obtient en calculant t i* t i • Dans notre exemple, on obtient le tableau suivant :Tâche Marge totale
A 0 B 1 C 0 D 2 E 0 F 2Exercice 17.2
Proposer le tableau des marges totales des tâches de l'exercice précé- dent.Exemple fin :
7) Diagramme de Gantt
Il s'agira de représenter graphiquement le déroulement du projet ; les tâches à effectuer sur les plages à disposition durant les 10 semaines (numérotées de 0 à 9).0 1 2 3 4 5 6 7 8 9 10
A B C D E FPROBLEMES D'ORDONNANCEMENT 109
3EC - JtJ 202117.2 Divers exercices
Exercice 17.3
Proposer le diagramme de Gantt de la planification suivante :Tâche Durée en semaines Antériorité
A 3 B B 8 -C 2 A, B, F
D 6 -E 5 B, D
F 4 B a) Proposer le graphe de niveau. b) Proposer le graphe orienté. c) Compléter les dates au plus tôt et au plus tard. d) Déterminer les marges totales de chaque tâche. e) Proposer le diagramme de Gantt.Exercice 17.4
La mise en exploitation d'un nouveau gisement minier demande la réalisation d'un certain nombre de tâches. Le tableau suivant repré- sente ces différentes tâches avec leurs relations d'antériorité.Tâche Description Durée
(en jours) Tâches antérieuresA obtention d'un permis d'exploitation 120 -
B établissement d'une piste de 6 km 180 A
C transport et installation à pied d'oeuvre de 2 sondeuses 3 B D création de bâtiments provisoires pour le bureau des plans, le logement des ouvriers sondeurs 30 BE goudronnage de la piste 60 B
F adduction d'eau 90 D
G campagne de sondage 240 C,D
H forage et équipement de trois puits 180 E,F,G I transport et installation au fond du matériel d'exploitation 30 J,H J construction de bureaux et logements, ouvriers et ingé- nieurs 240 E,F,GK traçage et aménagement du fond 360 J,H
L construction d'une laverie 240 J,H
a) Déterminer les dates au plus tôt et au plus tard de chaque tâche. b) Déterminer le temps minimum de réalisation de l'ensemble. c) Proposer un chemin critique. d) Préciser les marges totales de chaque tâche.110 THEME 17
3EC - JtJ 2021Exercice 17.5
Un producteur de cinéma est confronté au problème de planning de son prochain film selon les tâches suivantes : Tâche description durée (j) antérioritésA écriture du scénario 30 -
B choix et recrutement des comédiens 12 15 jours après le début de A C choix du lieu de tournage 8 20 jours après le début de A D découpage technique 4 A et C doivent être terminées E préparation des décors 7 C et D doivent être terminées F tournage des extérieurs 10 A, B, C et D doivent être terminées G tournage des intérieurs 12 D, E et F doivent être termi- nées H synchronisation 3 F et G doivent être terminéesI montage 14 H doit être terminée
J accompagnement sonore 7 ne peut commencer que 3 jours après le début de I et après la fin de HK mixage 6 I et J doivent être terminées
L tirage de la copie zéro 1 ne peut commencer que 2 jours après la fin de K a) Déterminer les dates au plus tôt et les dates au plus tard de chaquequotesdbs_dbs8.pdfusesText_14[PDF] calcul matrice booléenne
[PDF] calcul matriciel bts
[PDF] prise de note rapide tableau abréviations
[PDF] sauzay programme
[PDF] programme voltaire
[PDF] un petit paragraphe sur l'environnement
[PDF] exemple de texte argumentatif sur l'environnement
[PDF] texte sur l'environnement
[PDF] texte argumentatif sur l'environnement 4am
[PDF] protection de l'environnement définition
[PDF] graphe probabiliste calculatrice
[PDF] graphe étiqueté
[PDF] una marcha por los derechos de los indigenas comprension escrita
