Offre de thèse
Algorithmes d'approximation robuste pour l'ordonnancement dans les plateformes HPC
Date limite de candidature
05-05-2024
Date de début de contrat
01-10-2024
Directeur de thèse
KACEM Imed
Encadrement
L'encadrement impliquera : - Imed KACEM, Giorgio LUCARELLI et Camille DIOU
Type de contrat
école doctorale
équipe
AXE IFLORSYScontexte
Travaux à réaliser au laboratoire LCOMS de l'Université de Lorraine dans le cadre d'un contrat doctoral (sous réserve que la candidature soit acceptée par le LCOMS et l'ED IAEM).spécialité
Informatiquelaboratoire
LCOMS - Laboratoire de Conception, Optimisation et Modélisation des Systèmes
Mots clés
Ordonnancement, Calcul de Haute Performance, NP-complétude, algorithme, Robustesse, approximation
Détail de l'offre
Ce projet propose d'étudier les performances garanties pour des algorithmes d'approximation robustes dédiés à la résolution de problèmes d'ordonnancement NP-durs sur les plateformes HPC. La robustesse est considérée dans notre étude comme la capacité d'un algorithme à garantir des solutions satisfaisantes et moins sensibles aux aléas et aux adversités, dans des contextes de données incertaines et/ou changeantes (valeurs a priori inconnues, mais fixées ou contrôlées aléatoirement par adversaires/concurrents après la phase de décision, valeurs divulguées lors de l'exécution du processus de décision). Nous nous concentrerons sur les problèmes d'ordonnancement durs de la classe NP-dur, couvrant en particulier certaines applications dans les plateformes HPC, sous hypothèse d'hétérogénéité (c'est-à-dire avec différents types de ressources de différentes vitesses/performances et/ou diverses capacités).
De plus, nous souhaitons étudier un cadre général où les données sont imprécises et où seules une borne inférieure et une borne supérieure sont connues à l'avance. Deux critères seront étudiés : la minimisation du regret maximum et l'approximation différentielle. Nous examinerons ensuite d'autres mesures d'évaluation et/ou concevrons de nouveaux critères pour compléter l'analyse standard du pire cas. Nos conclusions seront complétées par des analyses issues de l'apprentissage automatique permettant de prédire les performances des algorithmes conçus (programmation dynamique, recherche arborescente, heuristiques, algorithmes d'approximation, etc.) et d'identifier les meilleures alternatives, notamment en présence d'incertitudes. et la modification des données, en fonction de certains paramètres des instances testées.
Keywords
Scheduling, High Performance Computing, NP-completeness, algorithms, Robustness, approximation
Subject details
This project proposes to study the guaranteed performance for robust approximation algorithms dedicated to solving NP-hard scheduling problems on HPC platforms. Robustness is considered in our study as the ability of an algorithm to ensure satisfactory solutions that are less sensitive to hazards and adversities, in contexts of uncertain and/or changing data (values which are a priori unknown, but which are randomly fixed or controlled by opponents/competitors after the decision stage, values disclosed during the execution of the decision process). We will focus on hard scheduling problems of the NP-hard class, covering in particular some applications in HPC platforms, under heterogeneity assumption (i.e., with different types of resources of different speeds/performances and/or various capacities). Moreover, we would like to study a general framework where the data are imprecise and only a lower and an upper bound are known in advance. Two criteria will be studied: the minimization of maximum regret and the differential approximation. We will then examine other evaluation measures and/or design new criteria to complement the standard worst-case analysis. Our conclusions will be supplemented by analyses from machine learning, making it possible to predict the performance of the designed algorithms (dynamic programming, tree search, heuristics, approximation algorithms, etc.) and to identify the best alternatives, particularly in the presence of uncertain and changing data, depending on certain parameters of the tested instances.
Profil du candidat
Le candidat doit avoir de bonnes aptitudes théoriques en Informatique Décisionnelle et Algorithmique. Le potentiel du candidat est très important pour le succès des travaux envisagés. Les notions spécifiques en lien avec ce sujet peuvent être découvertes en début de la thèse. Une expérience dans l'un des domaines comme la complexité, l'ordonnancement ou l'approximation sera un grand atout.
Candidate profile
Good skill in Decision Science, Scheduling and Approximation.
Complexity, approximation, or scheduling will be welcome.
Complementary notions can be discovered at the beginning of the thesis.
Référence biblio
1. G. Lucarelli, B. Moseley, K. Th. Nguyen, A. Srivastav, and D. Trystram. Online non-preemptive scheduling on unrelated machines with rejections. ACM Transactions on Parallel Computing, 8(2) : article No. 9, 2021.
2. E. Bampis, K. Dogeas, A. V. Kononov, G. Lucarelli, and F. Pascual: Scheduling with Untrusted Predictions. IJCAI 2022: 4581-4587
3. I. Assayakh, I. Kacem, and G. Lucarelli: Min-Max Relative Regret for Scheduling to Minimize Maximum Lateness. IWOCA 2023: 49-61
4. V. Fagnon, I. Kacem, G. Lucarelli, B. Simon. Scheduling on Hybrid Platforms: Improved Approximability Window. LATIN 2020: 38-49
5. F. Abdallah, C. Tanougast, I. Kacem, C. Diou, D. Singer. Genetic algorithms for scheduling in a CPU/FPGA architecture with heterogeneous communication delays. Computers & Industrial Engineering 137 (2019)
6. I. Kacem, H. Kellerer. Complexity results for common due date scheduling problems with interval data and minmax regret criterion. Discrete Applied Mathematics ELSEVIER 264: 76-89 (2019)
7. I. Kacem, H. Kellerer. Semi-online scheduling on a single machine with unexpected breakdown. Theoretical Computer Science 646: 40-48 (2016)
8. M. Ben-Akka, C. Tanougast, C. Diou, A. Chaddad. An Efficient Hardware Implementation of the Double Q-Learning Algorithm. 3rd IEEE International Conference on Electrical Computer Communications and Mechatronics Engineering, July 2023, Spain.
9. I. Kacem, G. Lucarelli, and Th. Naz ́e. Exact algorithms for scheduling programs with shared tasks. Journal of Combinatorial Optimization, SPRINGER 2021. https://doi.org/10.1007/s10878- 021-00702-8
10. E. Bampis, A. Kononov, D. Letsios, G. Lucarelli, and M. Sviridenko. Energy efficient scheduling and routing via randomized rounding. Journal of Scheduling, SPRINGER 21 :35–51, 2018.
11. E. Bampis, D. Letsios, and G. Lucarelli. Green scheduling, flows and matchings. Theoretical Computer Science, ELSEVIER 579 :126–136, 2015.
12. I. Kacem, V. Th. Paschos. Weighted completion time minimization on a single-machine with a fixed non-availability interval: differential approximability. Discrete Optimization ELSEVIER 10, 61-68, 2013.