Algorithmes D Optimisation Sous Contraintes Etudies Dans Un Cadre Temps Reel

Algorithmes d'optimisation sous contraintes etudies dans un cadre temps reel

Algorithmes d'optimisation sous contraintes étudiés dans un cadre temps réel

Les systèmes temps réels intelligents, c'est-à-dire capables de prendre des décisions en temps contraint, constituent un nouveau défi. La nouveauté provient de la nature des tâches à ordonnancer sur le processeur : une prise de décision n'est pas vue comme un résultat complet, optimum, obtenu en temps borné ; elle correspond plutôt à un résultat approché, de qualité croissante en fonction du temps alloué. Le système ne vise plus seulement à garantir les échéances temporelles d'un ensemble de tâches ; il essaie aussi de maximiser la qualité en sortie du système. Nous avons choisi comme problèmes de décision la classe des problèmes de minimisation de la violation de contraintes. Un formalisme novateur, appelé problèmes de satisfaction de contraintes valuées, permet de modéliser ces problèmes d'optimisation. Pour un problème donné, il est difficile de prédire l'évolution de la qualité, afin de l'ordonnancer au mieux vis-à-vis des autres tâches gérées par le système. Notre approche pragmatique consiste à encadrer progressivement l'optimum lors de la résolution d'un problème. Cet encadrement est une information exacte de l'état d'avancement d'une tâche et un critère important pour répartir les efforts de calcul pour un ensemble de tâches d'optimisation. Concrétement, pour des problèmes de minimisation, l'encadrement est obtenu par coopération de méthodes incomplètes permettant de produire des majorants et de méthodes complètes permettant de produire des minorants. Nos travaux portent sur la production de minorants. Nous décrivons plusieurs méthodes originales et génériques pour simplifier soit la structure d'un problème, soit l'objectif, soit la procédure de recherche. Ces techniques sont expérimentées sur des problèmes générés aléatoirement, ainsi que sur des problèmes réels : planification des prises de vue du satellite Spot5, allocation de fréquences à des liens radio (CELAR).

European Control Conference 1991

Proceedings of the European Control Conference 1991, July 2-5, 1991, Grenoble, France