Ordonnancement et planification des tâches d’un projet industriel

Cours ordonnancement et planification des tâches d’un projet industriel, tutoriel & guide de travaux pratiques en pdf.

Problématique

Le problème qui se pose c’est de déterminer un calendrier d’exécution de toutes les tâches du projet, respectant les contraintes de précédence, de manière à terminer les travaux dans les meilleurs délais. Egalement, il faudra avoir un calendrier comprenant suffisamment d’informations afin qu’il servira comme un outil d’aide pour le contrôle de l’avancement du projet et le respect des délais.

Intérêts de l’ordonnancement et la planification

L’ordonnancement et la planification des tâches composant un projet complexe sont devenues des outils incontournables dans la gestion des projets, notamment les projets de grande envergure. Elles consistent à :
 Planifier et piloter la réalisation d’un projet,
 Améliorer l’organisation des ateliers,
 Prévoir la chronologie du déroulement des tâches,
 Organiser et optimiser l’utilisation des outils disponibles,
 Augmenter le rendement de chaque tâche dans la zone de production,
 Garantir la réalisation des projets dans les temps prévus,
 Définir le suivi des échéances afin de contrôler l’avancement et la fin des tâches, et prendre en compte les écarts entre les prévisions et les réalisations.

Modèles d’ordonnancement

Un ordonnancement est un calendrier possible pour la réalisation de toutes les tâches du projet, et ce en respectant les contraintes de précédences. Lorsque ce calendrier conduit à la durée totale la plus courte on dit l’ordonnancement est optimal.
Dans la perspective de répondre aux besoins des entreprises en termes d’amélioration de la gestion des projets, plusieurs techniques ont été développées dans la littérature, nous allons donner au-dessous, les plus pertinents modèles d’ordonnancement et planification.

 Méthode PERT

C’est une modélisation du problème central de l’ordonnancement par un graphe, elle permet d’évaluer la durée de réalisation d’un projet complexe et de détecter les parties de ce projet ne supportant aucun retard. Ce graphe porte le nom de graphe PERT (Program Evaluation and Review Technique) ou graphe potentiel-étape. Nous donnons ici quelques éléments sur cette modélisation.
Dans cette représentation, les arcs sont associés aux tâches; ils sont valués par la durée des tâches, et les sommets représentent certains événements qui regroupent en général la fin de certaines tâches et le début d’autres.

Modélisation en graphe

Le graphe orienté et valué G = (X, U) (un graphe où chaque arc de U est associée une valeur réelle de la durée d’une tâche) défini par :
– A chaque tâche x on associe un sommet i X de départ et un sommet j X de fin tel que i < j.
– On définira un arc (i, j) de longueur di,j pour chaque tâche x avec di,j la durée d’exécution de la tâche.
Le graphe reflète les précédences requises dans l’exécution des différentes tâches du projet. Ce graphe est sans circuit du fait que l’existence d’un circuit impliquerait une contradiction dans les précédences; une tâche devant en même temps précéder et succéder à une autre. Il est moins facile à représenter ; il faut définir les événements correspondant aux sommets. Certaines contraintes de succession nécessitent l’introduction de tâches fictives. Enfin, la prise en compte de contraintes qui ne sont pas des contraintes de succession peut être plus délicate.
Supposons par exemple que l’on ait les tâches suivantes A, B, C, D avec :
A précède C et D
B précède D
A ces 4 tâches sont associés 4 arcs : A, B, C, D.
A précède C et D se traduit par : l’extrémité de l’arc correspondant à la tâche A coïncide avec l’origine de l’arc correspondant à la tâche C et avec l’origine de l’arc correspondant à la tâche D.
B précède D est traduit par : l’extrémité de l’arc correspondant à la tâche B coïncide avec l’origine de l’arc correspondant à la tâche D. Cela peut conduire à la représentation suivante :
Dans cette représentation, C et D ont même origine ce qui impose la contrainte : B précède également C qui n’était pas dans les données du problème.
Il faut alors introduire une tâche fictive de longueur 0.

Ordonnancement au plus tôt

On appelle date de début au plus tôt d’une tâche la plus petite date à laquelle elle peut être lancée.
Le calendrier de l’ensemble des tâches est appelé « ordonnancement au plus tôt ».
Proposition 1
La date de début au plus tôt d’une tâche est égale à la longueur du plus long chemin entre le sommet « début » et le sommet représentant cette tâche dans le graphe.
Preuve
A chaque contrainte de précédence on associe un arc (i, j) : la contrainte tj ≥ ti + di,j est associée l’arc (i, j) de longueur di,j, où ti représente la date de début de la tâche i.
Si on additionne ces inégalités pour tous les arcs du chemin, on arrive à ti ≥ tdébut + somme des longueurs des arcs de n’importe quel chemin reliant le sommet début et au sommet i.
Comme tdébut = 0, on en déduit que la date de début de la tâche i est au moins égale à la longueur du plus long chemin.
Ce résultat est vrai pour tous les chemins reliant le sommet « début » au sommet i, la date de début au plus tôt de la tâche i est égale à la longueur du plus long chemin du sommet « début » au sommet i.
Remarque
Si on considère le sommet « fin » associé à la fin des travaux, la date tFin qui représente la durée des travaux est au moins égale à la longueur de n’importe quel chemin du sommet « début » au sommet « fin », donc au plus long d’entre eux.
Calcul des dates au plus tôt
D’après la proposition précédente, le calcul des dates au plus tôt revient à calculer celui de la longueur d’un plus long chemin. On peut donc utiliser les algorithmes adaptés à la détermination de plus longs chemins.
Nous allons nous intéresser aux algorithmes qui permettent la détermination des plus longs chemins sur un graphe orienté, valué et sans circuit dans la section suivante.

Ordonnancement au plus tard

Il s’agit en l’occurrence de déterminer la date à laquelle chacune des tâches doit impérativement avoir commencé si on veut que la durée totale des travaux soit respectée.
Définition
On appelle date de début au plus tard d’une tâche la date à laquelle elle doit impérativement avoir commencé afin que la date de fin de travaux soit respectée.
Le calendrier correspondant est l’ordonnancement au plus tard.
Proposition 2
La date de début au plus tard d’une tâche est égale à la différence entre la date de fin des travaux et la longueur du plus long chemin du sommet représentant cette tâche dans le graphe au sommet « fin ».