Pour ce séminaire MaMuX j’ai choisi de parler d’un travail qui exhibe un lien entre le comportement d’un algorithme d’ordonnancement et la discrétisation d’une droite de pente rationnelle. Le modèle est le suivant. Nous disposons d’un ensemble de tâches de taille unitaire à exécuter sur un processeur. Chaque tâche a une contribution de température h donnée. Si la température du processeur est t et qu’il exécute cette tâche, elle est (t+h)/2 après l’exécution. Si le processeur ne fait rien par contre la température chute à t/2. La température du processeur ne dois jamais dépasser la valeur 1 (normalisé). Le but est d’ordonnancer un plus grand nombre de tâches avant une date limite commune D. Ce problème est NP-complet. Dans ce travail nous analysons le rapport d’approximation d’une politique d’ordonnancement très simple, qui exécute à tout moment la tâche de la plus petite contribution de température, si c’est possible.

Ce travail est en commun avec Ioannis Milis, Julien Robert and Georgios Zois.

Recherche opérationnelle – Optimisation combinatoire

Avec la participation de Christoph Dürr (LIP6, CNRS/Université Pierre et Marie Curie), Philippe Esling (Department of Genetics and Evolution, Université de Genève, Suisse), Daniel Schell et Ola Rinta-Koski.