next up previous
suivant: Les contraintes temporelles monter: Le problème de l'ordonnancement précédent: Introduction

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.

\begin{defi}[Date de fin au plus tôt]
On appelle \emph{date de fin au plus tôt}...
...male
d'exécution du projet permettant de respecter les contraintes.
\end{defi}


Sous-sections

Bruno Garcia 2000-12-17