CHAPITRE I
Problème
d'ordonnancement
17
I.1 Introduction
La théorie de l'ordonnancement est une branche de
la recherche opérationnelle qui s'intéresse
au calcul de dates d'exécution optimales de
tâches [web 1]. Pour cela, il est très souvent nécessaire
d'affecter en même temps les ressources nécessaires à
l'exécution de ces tâches. Un problème d'ordonnancement
peut être considéré comme un sous-problème de
planification dans lequel il s'agit de décider de l'exécution
opérationnelle des tâches planifiées.
I.2 Définition générale de
l'ordonnancement
L'ordonnancement consiste à organiser dans le
temps l'exécution d'un ensemble de tâches au moyen d'un ensemble
de ressources. Ce problème se trouve au coeur de nombreuses
problématiques industrielles. En gestion de projet, ordonnancer, c'est
déterminer les dates d'exécution des activités constituant
le projet.
En informatique, ordonnancer revient à
décider de l'ordre d'exécution des processus et de leur
attribution à des processeurs parallèles. En gestion de
production, l'ordonnancement consiste à déterminer les
séquences d'opérations à réaliser sur les
différentes machines de l'atelier. Chacun de ces contextes pratiques
définit ainsi les caractéristiques propres des tâches et
des ressources, le type des décisions à prendre, les
modalités d'exécution des tâches par les ressources qui
déterminent des contraintes sur les décisions et aussi les
différents critères qui mesurent la qualité d'une
solution. Un contexte particulier définit en fait un problème
d'optimisation combinatoire en termes de variables de décision, de
contraintes et de fonction objectif. Nous appelons ainsi problème
d'ordonnancement un problème d'optimisation combinatoire dont la
solution donne des indications sur les dates de début d'un ensemble de
tâches à ordonnancer ou sur des relations d'ordre total ou partiel
à respecter dans l'exécution de ces tâches afin de
respecter un ensemble de contraintes et/ou d'optimiser une fonction
objectif.
I.3 Eléments fondamentaux
I.3.1 Définition du problème
d'ordonnancement
Le problème de l'ordonnancement est un
problème de séquencement particulier dans lequel, en plus de
choisir et d'ordonner un ensemble d'opérations ou tâches tout en
satisfaisant un ensemble de contraintes, on doit allouer les opérations
aux ressources et leur fixer des dates de début, en d'autre termes le
problème d'ordonnancement englobe les deux problèmes de
séquencement et d'affectation. Du point de vue complexité il a
été démontré que ces deux problèmes
sont
18
fortement combinatoires et ils appartiennent à
la classe des problèmes NP-difficiles. Plusieurs définitions du
problème d'ordonnancement ont été
données.
Eric Pinson [Pinson 88] le définit comme
étant « l'organisation dans le temps de l'exécution d'un
projet » pour Norman Sadeh [Sade, 91], c'est « l'allocation dans le
temps de ressource permettant l'exécution d'un ensemble de tâches
». Pour Gotha [Goth, 93], c'est « programmer l'exécution des
tâches en leur allouant les ressources requises et en fixant leur date de
début».
Ordonnancer c'est programmer l'exécution d'une
réalisation en attribuant des ressources aux tâches et en fixant
leurs dates d'exécution [web 4].
Un ordonnancement fourni l'ordre de traitement des
différents produits au cours du temps. Les problèmes
d'ordonnancement apparaissent dans tout les domaines de l'économie,
l'informatique
(taches=jobs, produit, pièces .et
ressource=processeurs, mémoire, machine, .), la
construction (suivi
de projet), l'industrie (problème d'atelier , gestion de production),
l'administration (emploie du temps) les tâches sont le
dénominateur commun des problèmes d'ordonnancement , leur
définition n'est ni toujours immédiate, ni toujours triviale,
enfin il faut programmer les tâches de façon a optimiser un
certain objectif qui sera, suivant le cas la minimisation de la durée
totale (c'est le critère le plus fréquemment employé) ou
le respect de date de commande ou le lissage de courbe de main d'oeuvres ou
encore la minimisation d'un coût, d'une manière
générale, trois types d'objectifs sont essentiels dans la
résolution des problème d'ordonnancement : l'utilisation
efficaces des ressources, un délais d'exécution des tâches
aussi faible que possible, le respect de dates d'achèvement prescrites a
l'avance. Bien entendue il sera souvent plus réaliste, dans la pratique,
de considérer plusieurs critères.
| 
