A l'occasion de sa conférence inaugurale du mardi 18 juin 2019, Hans Kellerer, Professor@Lorraine nous explique la nature de ses travaux avec le prof. Kacem de l'Université de Lorraine au sein de l’équipe Décision et OPtimisation du laboratoire LCOMS autour de l'analyse des algorithmes d’ordonnancement et l'évaluation de leur efficacité à travers plusieurs critères lors de sa conférence inaugurale dans le grand amphithéâtre de l'UFR MIM du campus de Metz. Interview...
Où travaillez-vous quand vous n’êtes pas en Lorraine et pouvez-vous expliquer la nature de vos travaux à un public de non spécialistes ?
Je suis professeur à l’Université de Graz en Autriche. Lorsque je n’y travaille pas je suis à l’Université de Lorraine ou à d’autres universités avec lesquelles j’ai des collaborations, telles qu’en Hongrie, en Italie, au Royaume Uni, aux USA et à Hong Kong.
J’ai étudié les mathématiques mais depuis que je travaille au Département de Recherche Opérationnelle de la Faculté d’économie et gestion, ma recherche est devenue interdisciplinaire entre l’informatique théorique, les mathématiques et l’économie. Dans mon travail j’essaie de développer des algorithmes efficaces applicables à des problèmes concrets, tels l’ordonnancement de la production, le chargement de cargo, la découpe guillotine ou encore l’ordonnancement des départs d’avions dans un aéroport. Je n’implémente pas les algorithmes dans la réalité, je me focalise sur l’analyse théorique d’algorithmes avec des applications réelles potentielles.
Comment êtes vous entré en contact avec les chercheurs lorrains et que signifie devenir Professor@Lorraine pour vous ?
J’ai rencontré le Prof. Imed Kacem pour la première fois en 2007 à l’Université de Warwick à Coventry. A l’époque il était encore professeur à l’Université de Troyes. Puisque nous avons immédiatement trouvé des centres d’intérêt communs, il m’a invité à Troyes pendant deux mois fin 2008. Depuis, je lui ai rendu visite chaque année pendant au moins un mois. En 2010 et 2011, le Prof. Kacem et moi-même avons pu devenir coordinateurs d’un projet franco-autrichien sur l’ordonnancement qui nous a permis d’échanger régulièrement les visites de coopération scientifique à Metz et à Graz. J’ai également été invité plusieurs fois en tant que chercheur d’excellence à l’Université de Lorraine.
Devenir Professor@Lorraine signifie avant tout un grand honneur, mais c’est également une reconnaissance de notre recherche commune. Le plus important c’est que pour les quatre prochaines années, nous sommes certains que notre coopération, avec tous les sujets scientifiques qui nous passionnent, continue plus intensément grâce au soutien précieux de l’Université de Lorraine et de l’ISITE LUE.
Quels ont été les fruits/ sont les résultats espérés de votre collaboration avec le Prof. Kacem ?
Notre principal intérêt était de développer et analyser des algorithmes destinés à résoudre des problèmes d’ordonnancement. Par exemple, nous étions intéressés par des problèmes avec le but de réduire le délai maximum de production, ou de réduire le nombre total de tâches qui ne peuvent pas être planifiées à temps. De plus, nous analysons les algorithmes pour les problèmes où des machines ne sont pas disponibles ou sont sujettes à des pannes soudaines. Pour juger de la qualité d’un algorithme, nous prenons généralement le pire comportement de celui-ci, mais des critères exotiques comme minimiser le regret maximal ont également été examinés.
Quels sont vos projets pour la suite ?
Dans les prochaines années, nous continuerons de travailler sur les algorithmes d’ordonnancement, mais nous nous concentrerons sur d’autres critères que l’analyse des pires conditions pour évaluer la qualité d’un algorithme. Une voie envisagée serait de modéliser les problèmes d’ordonnancement comme des problèmes de la théorie algorithmique des jeux et d’utiliser le « prix de l’anarchie (1)» comme critère.
1 Le prix de l'anarchie est une situation où chaque partie individuelle travaillant de façon optimale peut nuire à l'efficacité d'un tout. Il faut donc les artificiellement les brider pour améliorer une production ou des délais. L'exemple le plus concret étant la circulation routière : si chaque véhicule cherche à emprunter le chemin le plus court, il arrive de se retrouver avec des embouteillages. Contre-intuitivement, en fermant des routes on peut parvenir à fluidifier la circulation.