VFVincent Fagnon

Vincent Fagnon

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Vincent Fagnon has a total of 9 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Prédiction et augmentation de ressources à la rescousse de l'algorithmique

    by Vincent Fagnon

    Actuellement, la tendance est à la mutualisation des ressources informatiques. Cette centralisation offre plusieurs avantages, notamment une meilleure gestion des variations de charge de travail, l'évitement de pics d'utilisation extrêmes et une optimisation simplifiée des calculs avec les données déjà en place. Cependant, l'avènement de l'Internet des objets (IoT) a créé une augmentation des besoins de traitement et d'analyse de données à des endroits éloignés des data-centers. Pour un traitement plus rapide et efficace, il est important de limiter les transferts de données et de les traiter près de leur lieu de production. Ainsi, il est essentiel de trouver un équilibre entre l'utilisation de plateformes centralisées pour mutualiser les ressources de calcul et les modèles décentralisés pour traiter les données localement.Cette thèse porte sur la mise en œuvre de plusieurs mécanismes visant à concevoir des algorithmes d'ordonnancement pour plusieurs agents ayant des objectifs distincts sur une plateforme composée de ressources de calcul.Tout d'abord, nous nous interrogeons sur l'utilisation d'un mécanisme externe (oracle) pour révéler les incertitudes relatives aux durées d'exécution de tâches séquentielles à exécuter sur une ressource de calcul. Nous proposons des algorithmes qui garantissent des performances moyennes optimales sur l'objectif classique du "sum flowtime" et étudions, via une campagne de simulations, leurs performances, leurs robustesses et la pertinence du modèle d'oracle en moyenne. Nous nous interrogeons également sur l'efficacité d'un tel modèle si l'on souhaite garantir de bonnes performances au pire des cas.Ensuite, nous étudions un problème bi-agent dans lequel chaque agent est soumis à des contraintes et des objectifs différents. Nous proposons un algorithme mettant en œuvre de l'augmentation de ressources (vitesse et rejet) et prouvons, grâce à la technique du dual fitting, un rapport de compétitivité dépendant, entre autres, de ces paramètres d'augmentation.Enfin, nous abordons un problème plus classique d'ordonnancement d'une application de tâches séquentielles pour laquelle nous souhaitons minimiser le "makespan" sur une plateforme hybride multicœurs (CPU/GPU). Nous proposons un algorithme basé sur l'étude de "l'intégrality gap" de la relaxation d'une programmation linéaire, algorithme pour lequel nous donnons une preuve de garantie de performances sous la forme d'un rapport d'approximation constant.

  • Two-Agent Scheduling with Resource Augmentation on Multiple Machines

    by Vincent Fagnon, Giorgio Lucarelli, Clément Mommessin, Denis Trystram

  • Scheduling on Hybrid Platforms: Improved Approximability Window

    by Vincent Fagnon, Imed Kacem, Giorgio Lucarelli, Bertrand Simon


  • Open Access

    Scheduling on Hybrid Platforms: Improved Approximability Window

    by Vincent Fagnon, Imed Kacem, Giorgio Lucarelli, Bertrand Simon

    Modern platforms are using accelerators in conjunction with standard processing units in order to reduce the running time of specific operations, such as matrix operations, and improve their performance. Scheduling on such hybrid platforms is a challenging problem since the algorithms used for the case of homogeneous resources do not adapt well. In this paper we consider the problem of scheduling a set of tasks subject to precedence constraints on hybrid platforms, composed of two types of processing units. We propose a $(3+2\sqrt{2})$-approximation algorithm and a conditional lower bound of 3 on the approximation ratio. These results improve upon the 6-approximation algorithm proposed by Kedad-Sidhoum et al. as well as the lower bound of 2 due to Svensson for identical machines. Our algorithm is inspired by the former one and distinguishes the allocation and the scheduling phases. However, we propose a different allocation procedure which, although is less efficient for the allocation sub-problem, leads to an improved approximation ratio for the whole scheduling problem. This approximation ratio actually decreases when the number of processing units of each type is close and matches the conditional lower bound when they are equal.