Ordonnancement avec contraintes de ressources

Ordonnancement avec contraintes de ressources

Ordonnancer ?

Définition

Le problème d’ordonnancement consiste 'a organiser dans le temps la réalisation d’un ensemble de tˆaches, compte tenu de contraintes temporelles (délais, contraintes d’enchaînements,

...) et de contraintes portant sur l’utilisation et la disponibilité des ressources requises.

Un ensemble de tˆaches

Un environnement de ressources pour effectuer les tˆaches

Des contraintes sur les tˆaches et les ressources

Un critère d’optimisation

=) Déterminer

V=) Déterminer les dates d’exécution des tˆaches

Domaines concernes

Contraintes rencontrées en ordonnancement

Différentes contraintes

• technologiques : une tache ne peut débuter que lorsque d’autres sont achevées

• commerciales : certaines dates doivent ˆêtre achevées pour une date fixée

• matérielles : une machine ne peut traiter qu’une machine a la fois

• de main d’oeuvre : effectif limite

• financières : budget limite

En d’autre terme :

 Contraintes de précédence

 Contraintes de disponibilité des ressources

 Contraintes disjonctives : deux tâches utilisant la même ressource ne peuvent s’exécuter simultanément

 Contraintes cumulatives : deux processeurs sont disponibles pour l’exécution de trois tâches. Si on ne sait pas laquelle de ces tâches sera différée, quelles tâches choisir pour exécutions simultanées ?

Un problème d’ordonnancement est dit statique si tout est connu à l’avance. (nombre de tâches et caractéristiques des tâches) ; sinon il est dit dynamique.

Les ressources sont dites parallèles si elles ont toutes les mêmes fonctionnalités ; sinon elles sont dédiées.

Exemple

Contexte du problème

...