Qu’ont en commun la planification de la construction d’un bâtiment, la production industrielle, la gestion de commandes en limitant les retards ou même la préparation d’un sac à dos par une randonneuse, voire le partage équitable de quelques pièces de monnaie par des enfants ? Chacune de ces tâches demande la résolution d’un problème d’ordonnancement. Il faut décider quand chaque tâche doit être faite afin que tout se passe au mieux.
Construire un bâtiment : que faire quand ?
Prenons l’exemple de la construction d’un bâtiment. Une cheffe de chantier doit organiser la venue de chaque corps de métier selon l’avancée des travaux. Elle connaît les tâches à faire, leurs durées respectives, ainsi que leurs précédences, c’est-à-dire quelles tâches doivent être terminées avant de pouvoir en commencer une autre (voir le tableau). Par exemple, la maçonnerie doit être terminée avant de commencer la plomberie.
On peut représenter cela par un graphe de précédences, comme ci-après, où les nombres sur les arcs indiquent les durées.
