2.7 Les problèmes de planification
La planification consiste en la recherche d'une
séquence d'opérations permettant de passer d'un état
initial à un état final souhaité. Un problème
d'ordonnancement consiste à organiser dans le temps un ensemble
d'activités, de façon à satisfaire un ensemble de
contraintes et optimiser une ou plusieurs fonctions objectives. En d'autres
termes, la planification consiste à déterminer les tâches
à exécuter et l'ordonnancement consiste à
déterminer quand exécuter ces tâches. Le contrôle
d'exécution de plans est un problème particulièrement
35
difficile lorsqu'il doit être effectuéà
bord de systèmes autonomes tels que des robots. Un tel système
doit disposer d'un processus pour engendrer des plans qui réalisent les
buts de la mission tout en respectant des délais et des contraintes de
précédence. Plusieurs formalismes et algorithmes ont
étédéveloppés pour traiter des problèmes de
planification tenant compte des contraintes temporelles. De tels
problèmes de planification existent dans de nombreuses applications
réelles telles que le transport, la robotique, le domaine
médical, les services d'urgences, etc. . .[12]
2.7.1 Contraintes de pr'ec'edence
Dans le monde réel, la
possibilitéd'exécuter une tâche peut dépendre de
plusieurs conditions, comme le temps et les ressources disponibles ou
l'exécution d'autres tâches. On considère que les
contraintes de précédence [12] auparavant sont de la forme d'une
relation d'ordre partiel sur un ensemble de tâches T. Dans ce cas, entre
deux tâches quelconques il existe une relation de
précédence ou il n'existe pas de relation qui les relie. On
établit une distinction entre deux sortes de contraintes de
précédence :
- Contraintes de Pr'ec'edence Conjonctives:
Le cas oùun groupe de tâches indépendantes
doit être exécutépour permettre l'exécution de
certaines autres tâches. Si les tâches
t1,t2,...., tk doivent toutes être
exécutées avant l'exécution d'une tâche t,
on écrit symboliquement : [t1, t2,...,
tk]-+t.
- Contraintes de Pr'ec'edence Disjonctives :
Le cas oùune seule tâche parmi un groupe de
tâches doit être exécutée avant que la tâche en
question ne puisse être exécutée. S'il suffit qu'une
tâche parmi les tâches t1, t2,..., tk
s'exécute pour que la tâche t puisse
s'exécuter, on écrit symboliquement : t1|t2|. ..
.|tk-+t.
A noter que parfois on doit attendre un peu de temps
après la fin de l'exécution d'une tâche et avant le
début de l'exécution de la tâche suivante.
| 
