Cet exposé tentera de faire un synthèse des résultats sur trois modèles de problèmes d'ordonnancement développés ces dernières années pour répondre à une demande de domaines applicatifs : les modèles cycliques, les modèles avec délais de communication et les modèles avec coûts d'avance et de retard.

Les problèmes d'ordonnancement cycliques où très généralement un système de tâches doit être exécuté de manière répétitive, ont été introduits pour modéliser des problèmes d'optimisation de code en compilation, déterminer des conditions d'ordonnançabilité de certains systèmes de tâches temps-réel et améliorer la gestion de certains systèmes de production en série.

Les problèmes d'ordonnancement avec délais de communication ont été étudiés en tant que modèles d'exécution de systèmes de tâches sur réseaux de processeurs. Leur caractéristique essentielle est d'imposer, pour chaque couple de tâches communiquantes, la prise en compte du temps de transmission des données entre ces tâches.

Les problèmes d'ordonnancement avec coûts d'avance et de retard se posent tout particulièrement dans le cadre de la production juste à temps où tout écart par rapport à une date attendue de fin de tâche entraîne une pénalité.

L'objectif de l'exposé est pour chacun des trois modèles de présenter le problème de base ainsi que certaines variantes, de montrer les différences fondamentales par rapport aux problèmes classiques, d'en étudier l'impact sur la complexité, de situer quelques points d'achoppement de la recherche actuelle et enfin de présenter quelques directions possibles de recherches futures.

Sur une plate-forme hétérogène, la minimisation du makespan de l'ordonnancement d'un ensemble de tâches identiques et indépendantes est un problème dont la complexité est intimement liée à l'architecture de la plate-forme (étoile, chaîne, pieuvre, arbre). Après avoir rapidement présenté quelques résultats récents à ce sujet, nous montrons que le problème de la maximisation du débit en régime permanent d'une telle plate-forme est en revanche polynomial et ce, quelque soit l'architecture de
la plate-forme. Nous expliquons ensuite comment en déduire un ordonnancement asymptotiquement optimal quand le nombre de tâches à traiter devient grand.
Enfin, nous montrons comment étendre partiellement ce résultat au cas d'un ensemble de graphes de tâches identiques et indépendants.

La littérature en ordonnancement contient de très nombreux travaux liés à l'ordonnancement en Juste-à-Temps (JaT). Typiquement on définit un problème d'ordonnancement de type JaT comme étant un problème d'ordonnancement dans lequel on cherche à faire terminer chaque travail (commande) aussi proche que possible de sa date de fin souhaitée. Du moins, cette définition simple conduit à une variété importante de problèmes abordés dans la littérature : on trouve ainsi les problèmes où l'objectif est de minimiser une somme de l' avance pondérée et du retard pondéré, d'autres où il faut minimiser la variance des dates de fin par rapport aux dates de fin souhaitées, etc. En tout cas, le plus souvent, c'est une fonction agrégée qui est minimisée (par exemple, la somme pondérée des avances et des retards). Par ailleurs, cette fonction ne constitue pas nécessairement un critère régulier d'où la nécessité de prendre en compte deux problèmes : celui du séquencement et de l'affectation des opérations sur les ressources et celui de l'insertion volontaire de temps morts sur les ressources de sorte à minimiser la fonction objectif (« optimal timing problem »).

En partant de ces problèmes « classiques » de la littérature en ordonnancement en JaT, on peut faire plusieurs remarques. Tout d'abord, on peut noter que l'avance totale, par exemple, est une mesure en soit qui s'oppose au retard total. Ainsi, minimiser l'avance d'un travail va impliquer qu'un autre travail doit être mis en retard (le premier « poussant » le second). Ainsi, on peut considérer les problèmes d'ordonnancement en JaT comme étant des problèmes multicritères (du moins, bicritères) qui s'ignorent. Dans la littérature, sont apparus récemment différentes approches multicritères pour l'ordonnancement en JaT. Le but de cette présentation sera d'en aborder certaines comme alternatives aux approches classiques où on minimise une fonction d'agrégation. La seconde remarque que l'on peut faire est liée à la façon dont on mesure l'aspect JaT : est-il pertinent de considérer une mesure de l'avance et une mesure du retard ? Ordonnancer JaT veut-il dire minimiser ces deux mesures ? Pour répondre à ces questions nous nous intéresserons aux notions de base de la production en JaT et en extrairons les éléments clefs pour l'ordonnancement. Cela nous amènera à considérer différents problèmes et pistes possibles.

L'ordonnancement des tâches reste une composante fondamentale dans le processus de traitement d'une application parallèle. Nous avons étendu le modèle à communication homogènes en prenant en compte la notion de communications hiérarchiques. Cette extension a été motivée par l'apparition des nouvelles architectures parallèles, comme par exemple les bi-processeurs connectés par des switches myrinet, des architectures point-à-point où chaque sommet de la topologie est un module de processeurs, ou des architectures à bus hiérarchiques, où les communications entre les processeurs du même module s'effectuent par l'intermédiaire des bus secondaires, tandis que les communications entre deux processeurs de modules différents se font par le bus principal.

Dans cet exposé, nous verrons quelques résultats obtenus avec l'introduction des communications hiérarchiques sur la complexité et l'approximation des problèmes d'ordonnancement.