Ordonnancement avec réjections limitées

Mots clés

ordonnancement, réjection, algorithmes d'ordonnancement, intelligence artificielle, apprentissage automatique

Détail de l'offre

I/ Contexte et enjeux :
L'ordonnancement est une thématique importante de l'optimisation combinatoire. Elle vise à allouer, dans le temps, un ensemble limité de ressources pour un ensemble de tâches à réaliser. L'objectif étant d'optimiser un ou plusieurs critères à la fois (temps, argent, pourcentage d'occupation des machines, etc.). L'ordonnancement avec la possibilité de renoncer à la réalisation d'un sous-ensemble de tâches est une généralisation du problème d'ordonnancement standard, qui nous intéresse tout particulièrement dans ce projet compte tenu du peu de travaux existants dans ce domaine. Les quelques références disponibles dans la littérature montrent l'intérêt pratique et théorique du sujet. En effet, ce type de configuration est bien adapté pour modéliser plusieurs situations réelles (nécessité de rejeter une partie de commandes par saturation du système de production ou pénurie des matières premières, intérêt de réduire la production pour optimiser d'autres critères, etc.). À titre d'illustration, on peut faire référence aux travaux suivants : [1 – 4].

II/ Objectifs et positionnement :
Nous considérons le problème d'ordonnancement de tâches sur des machines parallèles avec rejection. Notre objectif est de présenter des algorithmes pseudo-polynomiaux ou exacts dans des cas particuliers pour des critères standards (date de livraison maximale, somme des dates de fin, etc.) et de proposer ensuite des méthodes efficaces pour résoudre le problème général avec un nombre arbitraire de machines (méthodes exactes, algorithmes ou schémas d'approximation et heuristiques). Dans ce cadre, notre objectif est de concevoir des algorithmes efficaces dédiés à la résolution de ces problèmes d'ordonnancement. Ces algorithmes pourront être exacts ou approchés, selon le type et la difficulté de l'instance à résoudre. Dans tous les cas, nous visons des techniques algorithmiques permettant de « garantir la performance » des solutions données. Par la suite, une approche basée sur l'apprentissage automatique [5] sera utilisée pour analyser les résultats récoltés après l'application des algorithmes conçus (programmation dynamique [6], recherche
arborescente [7], heuristiques, algorithmes/schémas d'approximation [8 – 9], etc.) en fonction de certains paramètres des instances testées. Cela permettrait ensuite de prédire comment on peut résoudre efficacement chaque catégorie d'instance. De nombreux défis scientifiques sont rencontrés dans de nombreux problèmes de décision complexes liés à la conception d'algorithmes d'optimisation à performance garantie et d'algorithmes d'analyse basés sur l'apprentissage automatique et à l'Informatique Décisionnelle au sens large.