Théorie des graphes et ordonnancement

Les listes d'adjacence sont des listes où pour chaque sommet sont notés ses voisins. Une matrice d'adjacence est une matrice où la case (i,j) vaut 1 si et seulement s'il y a un arc de i vers j. Dans les graphes non orientés, avoir (i,j) égal à un implique d'avoir (j,i) égal à un.

Un chemin est une suite d'arcs tels que la destination d'un arc soit le départ du suivant. Un chemin avec n sommets est de longueur n-1. La fermeture transitive d'un graphe G est le graphe G' où il y a un arc de i et j si et seulement il y avait un chemin de i à j dans G. Un circuit est un chemin qui termine sur son point de départ. Le chemin le plus court de A à B est celui qui compte le moins d'arcs, ou dans le cas des graphes pondérés celui qui minimise la somme des poids sur ses arcs.

Le niveau d'un sommet est la longueur du plus long chemin finissant en ce sommet si le graphe n'a pas de circuits (sinon le niveau n'est pas défini).

On appelle cela une exploration du graphe partant de A, et si on découvre un point qu'on a déjà vu à une étape précédente cela signifie que le graphe a un circuit.

On peut aussi calculer les chemins de longueur k en utilisant la matrice d'adjacence :

Si on multiplie de manière booléenne (donc 1+1=1) la matrice d'adjacence à elle-même k fois (donc si on l'élève à la puissance k), on se retrouve avec une matrice où on a un "1" en (i,j) s'il y a un chemin de longueur au plus k entre i et j.

Si on fait maintenant la multiplication entière (1+1=2), et qu'on élève la matrice d'adjacence à la puissance k, la case (i,j) contient le nombre de chemins de i à j.

Si la tâche i termine au temps $t_i$, alors la date au plus tôt de j est $max_i t_i +d(i,j)$ où on ne considère en i que les antécédents de j, et où $d(i,j)$ est le poids de l'arc (i,j).

La marge libre de j est le temps dont peut être retardé une tâche sans affecter le processus. Elle est égale à $min_i t_i - d(j,i)$, où on prend dans i seulement les successeurs de j, et où t_i est la date au plus tôt de ceux-ci. Si retarder j retarde le processus alors cette marge vaut 0.

Le chemin critique est le chemin tel qu'aucune des tâches n'ait de marge. C'est le temps minimum nécessaire pour accomplir le processus si tout se passe normalement.