Le problème

On suppose le projet composé de $n$ tâches numérotées de $1$ à $n$ chacune dotée d'une durée $d_i$ supposée connue (la terminologie Anglo-Saxonne est processing time, laquelle est souvent notée $p_i$). Le problème de l'ordonnancement consiste à affecter à chaque tâche $i$ une date de début $t_i$. On suppose que le projet commence à $t_0=0$. Divers types de contraintes peuvent se greffer sur le noyau dur du problème :

Les contraintes temporelles

portent sur les dates de début et de fin des tâches

Les contraintes d'allocation de ressources

spécifient qu'une ressource critique (e.g., la grue dans un chantier de BTP) ne peut être utilisée par plus d'un certain nombre de tâches à la fois

L'objectif

est de minimiser la durée totale du projet (makespan en Anglais), c'est-à-dire, calculer la date de fin au plus tôt du projet.