Ordonnancement et planification des tâches de production

Cours ordonnancement et planification des tâches de production, tutoriel & guide de travaux pratiques en pdf.

Échéancier des tâches

La fabrication d’un faisceau électrique se réalise en plusieurs étapes de production, chaque étape est indépendante mais elle peut nécessiter que d’autres étapes soient préalablement réalisées avant de commencer sa réalisation, ce qui s’exprime dans le tableau ci-dessous par les contraintes d’antériorités. Le programme complet de la matricule P55260137_0202_ENGINE 1.8 d’un faisceau électrique est présenté dans le tableau suivant, appelé échéancier, il fait apparaître : les tâches de production, leurs codes, leurs durées de réalisation en seconde ainsi que les relations de précédences (ou d’antériorité) entre les différentes tâches.

Niveaux des tâches

Définition

Un niveau désigne le commencement ou bien le départ d’une ou plusieurs tâches, il est distingué à l’aide d’une matrice, appelé matrice d’antériorité.

Exemple d’application

D’après l’échéancier au-dessus (Tableau 1), on détermine les niveaux des tâches selon les étapes suivantes :
Soit la matrice représentant la priorité entre les tâches de production. Cette matrice est défini par :
– Si il existe une antériorité, on tape 1 dans l’intersection de la ligne de la tâche avec la colonne de la tâche antérieure
– Sinon on tape 0.
Algorithme de détermination des niveaux des tâches
– Cherchons les lignes des tâches qui contiennent seulement des 0. Donc dans la 1ère itération, les tâches de niveau 0 sont : A, B et C
– On barre les lignes et les colonnes des tâches A, B et C.
– Cherchons encore dans la nouvelle matrice les lignes des tâches qui contiennent seulement des
2ème itération : les tâches de niveau 1 sont D, E et F.
– On barre les lignes et les colonnes des tâches D, E et F.
3ème itération : les tâches de niveau 2 sont G et I
– On barre les lignes et les colonnes des tâches G et I.
– Cherchons dans la matrice les nouvelles lignes des tâches qui contiennent seulement des 0. On trouve la ligne de la tâche H et K qui construis seulement avec des 0.
Alors la 4ème itération : c’est des tâches H et K de niveau 3.
Et ainsi de suite jusqu’à la suppression de tous les lignes et les colonnes de la matrice.
On détecte 11 niveaux des tâches, l’ordonnancement par niveaux donne le tableau suivant :
Tableau 3 : les tâches de chaque niveau de réseau PERT.

Les tâches commençantes, convergentes et finissantes

Les tâches commençantes

Ce sont les tâches sans tâche antérieure, elles partent d’entrée du graphe (sommet 1), dans notre exemple les tâches commençantes sont : A, B et C

Les tâches convergentes

Ce sont les tâches que l’on rencontre toujours ensemble c’est à dire jamais l’une sans l’autre, ces tâches auront le même sommet terminal dans le graphe. Dans notre exemple elles sont : H et I ; E K et L

Les tâches finissantes

Les tâches qui ne sont pas antérieures à d’autres tâches, elles arrivent à la sortie du graphe (sommet terminal). Dans notre exemple c’est la tâche R.

Modélisation en graphe

A partir des données précédent du projet ; on construit un graphe 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.
Pour compléter le graphe parfois on utilise des tâches fictives (une tâche fictive est une tâche de durée nulle). En effet la finalisation de la tâche D est nécessaire pour commencer les tâches G et H, donc il est nécessaire d’ajouter une tâche fictive dans l’arc (5,6). On trace les tâches par ordre de niveau croissant, ce graphe sera un graphe valué dont les arcs seront les tâches, les valeurs des arcs représentent les durées des tâches et les sommets représentent les états d’avancement du projet, numérotés de 1 à n.